A branch-and-bound algorithm for minimizing the sum of maximum earliness and tardiness with unequal release times

References

• Abdul-Razaq , T. S. and Potts , C. N. 1988 . Dynamic programming state-space relaxation for single-machine scheduling . Journal of the Operational Research Society , 39 ( 2 ) : 141 – 152 .
   Web of Science ®Google Scholar
• Almeida , M. T. and Centeno , M. 1998 . A composite heuristic for the single machine early/tardy job scheduling problem . Computers and Operations Research , 25 ( 7–8 ) : 625 – 635 .
   Web of Science ®Google Scholar
• Amin-Nayeri , M. and Moslehi , G. 2000 . An optimum algorithm for single machine with early/tardy cost . Esteghlal—Journal of Engineering , 19 ( 1 ) : 35 – 48 .
   Google Scholar
• Azizoglu , M. , Kondakci , S. and Kirca , O. 1991 . Bicriteria scheduling problem involving total tardiness and total earliness penalties . International Journal of Production Economics , 23 ( 1–3 ) : 17 – 24 .
   Web of Science ®Google Scholar
• Baker , K. R. 1974 . Introduction to sequencing and scheduling , New York : John Wiley .
   Google Scholar
• Baker , K. R. and Scudder , G. D. 1990 . Sequencing with earliness and tardiness penalties—A review . Operations Research , 38 ( 1 ) : 22 – 36 .
   Web of Science ®Google Scholar
• Baker , K. R. and Su , Z.-S. 1974 . Sequencing with due-dates and early start times to minimize maximum tardiness . Naval Research Logistics , 21 ( 1 ) : 171 – 176 .
   Web of Science ®Google Scholar
• Brucker , P. 1998 . Scheduling algorithms , Heidelberg : Springer .
   Google Scholar
• Carlier , J. 1982 . The one-machine sequencing problem . European Journal of Operational Research , 11 : 42 – 47 .
   Web of Science ®Google Scholar
• Cheng , T. C.E. , Chen , Z. L. and Shakhlevich , N. V. 2002 . Common due date assignment and scheduling with ready times . Computers & Operations Research , 29 ( 14 ) : 1957 – 1967 .
   Web of Science ®Google Scholar
• Fujii , S. and Wang , J. 1988 . Optimal single-machine scheduling for minimizing the sum of earliness and tardiness penalties . Journal of the Operational Research Society of Japan , 13 : 105 – 120 .
   Google Scholar
• Gordon , V. , Proth , J. M. and Chu , C. B. 2002 . A survey of the state-of-the-art of common due date assignment and scheduling research . European Journal of Operational Research , 139 ( 1 ) : 1 – 25 .
   Web of Science ®Google Scholar
• Graham , R. L. , Lawler , E. L. , Lenstra , J. K. and Rinnooy Kan , A. H.G. 1979 . Optimization and approximation in deterministic sequencing and scheduling: A survey . Annals of Discrete Mathematics , 5 : 287 – 326 .
   Google Scholar
• Held , M. and Karp , R. M. 1962 . A dynamic programming approach to sequencing problems . Journal of the Society for Industrial and Applied Mathematics , 10 : 196 – 210 .
   Google Scholar
• Lenstra , J. K. , Rinnoy Kan , A. H.J. and Brucker , P. 1977 . Complexity of machine scheduling problems . Annals of Discrete Mathematics , 1 : 343 – 362 .
   Google Scholar
• Li , C.-L. and Cheng , T. C.E. 1994 . Parallel machine min-max weighted absolute lateness scheduling problem . Naval Research Logistics , 41 ( 1 ) : 33 – 46 .
   Web of Science ®Google Scholar
• Li , G. 1997 . Single machine earliness and tardiness scheduling . European Journal of Operational Research , 96 ( 3 ) : 546 – 558 .
   Web of Science ®Google Scholar
• Liaw , C. F. 1999 . A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem . Computers & Operations Research , 26 ( 7 ) : 679 – 693 .
   Web of Science ®Google Scholar
• M'Hallah , R. 2007 . Minimizing total earliness and tardiness on a single machine using a hybrid heuristic . Computers & Operations Research , 34 ( 10 ) : 3126 – 3142 .
   Web of Science ®Google Scholar
• Mahnam , M. 2008 . Minimizing the summation of maximum earliness and tardiness in single machine scheduling problem with unequal release times , Iran : Isfahan University of Technology . Masters thesis
   Google Scholar
• Mazzini , R. and Armentano , V. A. 2001 . A heuristic for single machine scheduling with early and tardy costs . European Journal of Operational Research , 128 ( 1 ) : 129 – 146 .
   Web of Science ®Google Scholar
• Mosheiov , G. and Oron , D. 2007 . Minmax scheduling with job-classes and earliness–tardiness costs . European Journal of Operational Research , 177 ( 1 ) : 612 – 622 .
   Web of Science ®Google Scholar
• Ow , P. S. and Morton , T. E. 1989 . The single machine early/tardy problem . Management Science , 35 ( 2 ) : 177 – 191 .
   Web of Science ®Google Scholar
• Pinedo , M. L. 2005 . Planning and scheduling in manufacturing and services , New York : Springer .
   Google Scholar
• Sidney , J. B. 1977 . Optimal single-machine scheduling with earliness and tardiness penalties . Operations Research , 25 ( 1 ) : 62 – 69 .
   Web of Science ®Google Scholar
• Sridharan , V. and Zhou , Z. 1996 . A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems . European Journal of Operational Research , 94 ( 2 ) : 292 – 301 .
   Web of Science ®Google Scholar
• Tavakkoli-Moghaddam , R. , Moslehi , G. , Vasei , M. and Azaron , A. 2005 . Optimal scheduling for a single machine to minimize the sum of maximum earliness and tardiness considering idle insert . Applied Mathematics and Computation , 167 ( 2 ) : 1430 – 1450 .
   Web of Science ®Google Scholar
• Tavakkoli-Moghaddam , R. , Moslehi , G. , Vasei , M. and Azaron , A. 2006 . A branch-and-bound algorithm for a single machine sequencing to minimize the sum of maximum earliness and tardiness with idle insert . Applied Mathematics and Computation , 174 ( 1 ) : 388 – 408 .
   Web of Science ®Google Scholar
• Tsai , T. I. 2007 . A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due dates and ready times . International Journal of Advanced Manufacturing Technology , 31 ( 9–10 ) : 994 – 1000 .
   Web of Science ®Google Scholar
• Valente , J. M.S. 2005 . Improved lower bounds for the single machine earliness/tardiness scheduling problem with release dates . International Journal of Operations Research , 2 ( 2 ) : 9 – 16 .
   Google Scholar
• Valente , J. M.S. 2007 . Dispatching heuristics for the single machine early/tardy scheduling problem with job-independent penalties . Computers & Industrial Engineering , 52 ( 4 ) : 434 – 447 .
   Web of Science ®Google Scholar
• Valente , J. M.S. and Alves , R. 2005a . An exact approach to early/tardy scheduling with release dates . Computers & Operations Research , 32 ( 11 ) : 2905 – 2917 .
   Web of Science ®Google Scholar
• Valente , J. M.S. and Alves , R. 2005b . Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time . Computers & Industrial Engineering , 48 ( 2 ) : 363 – 375 .
   Web of Science ®Google Scholar
• Valente , J. M.S. and Alves , R. 2005c . Improved heuristics for the early/tardy scheduling problem with no idle time . Computers & Operations Research , 32 ( 3 ) : 557 – 569 .
   Web of Science ®Google Scholar
• Valente , J. M.S. and Alves , R. 2005d . Improved lower bounds for the early/tardy scheduling problem with no idle time . Journal of the Operational Research Society , 56 ( 5 ) : 604 – 612 .
   Web of Science ®Google Scholar
• Valente , J. M.S. and Alves , R. 2007 . Heuristics for the early/tardy scheduling problem with release dates . International Journal of Production Economics , 106 ( 1 ) : 261 – 274 .
   Web of Science ®Google Scholar
• Ventura , J. A. and Radhakrishnan , S. 2003 . Single machine scheduling with symmetric earliness and tardiness penalties . European Journal of Operational Research , 144 ( 3 ) : 598 – 612 .
   Web of Science ®Google Scholar