New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling

References

• Avella P., Boccia M., D'Auria B. Near-optimal solutions of large-scale single-machine scheduling problems. INFORMS J. Comput. (2005) 17:183–191Link, Google Scholar
• Baker K. R., Scudder G. Sequencing with earliness and tardiness penalties: A review. Oper. Res. (1990) 38:22–36Link, Google Scholar
• Baptiste Ph., Le Pape C., Nuijten W.Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems (2001) (Kluwer Academic Publishers, Norwell, MA) Crossref, Google Scholar
• Beasley J. E. OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. (1990) 41:1069–1072 http://people. brunel.ac.uk/∼mastjjb/jeb/info.htmlCrossref, Google Scholar
• Biskup D., Feldmann M. Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Comput. Oper. Res. (2001) 28:787–801Crossref, Google Scholar
• Bülbül K., Kaminsky P., Yano C. Preemption in single machine earliness/tardiness scheduling. J. Scheduling (2007) 10:271–292Crossref, Google Scholar
• Carlier J., Pinson E. An algorithm for solving the job-shop problem. Management Sci. (1989) 35:164–176Link, Google Scholar
• Carlier J., Pinson E. Adjustment of heads and tails for the job-shop problem. Eur. J. Oper. Res. (1994) 78:146–161Crossref, Google Scholar
• Christofides N., Alvarez-Valdes R., Tamarit J. M. Project scheduling with resource constraints: A branch and bound approach. Eur. J. Oper. Res. (1987) 29:262–273Crossref, Google Scholar
• Dyer M. E., Wolsey L. A. Formulating the single machine sequencing problem with release dates as a mixed integer problem. Discrete Appl. Math. (1990) 26:255–270Crossref, Google Scholar
• Fisher M. L. A dual algorithm for the one-machine scheduling problem. Math. Programming (1976) 11:229–251Crossref, Google Scholar
• Fry T. D., Leong G., Rakes T. Single machine scheduling: A comparison of two solution procedures. Omega (1987) 15:277–282Crossref, Google Scholar
• Fry T. D., Armstrong R. D., Darby-Dowman K., Philipoom P. R. A branch and bound procedure to minimize mean absolute lateness on a single processor. Comput. Oper. Res. (1996) 23:171–182Crossref, Google Scholar
• Hall N. G., Posner M. E. Earliness-tardiness scheduling problems, I: Weighted deviation of completion times about a common due date. Oper. Res. (1991) 39:836–846Link, Google Scholar
• Hall N. G., Kubiak W., Sethi S. P. Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date. Oper. Res. (1991) 39:847–856Link, Google Scholar
• Hoogeveen J. A., van de Velde S. L. A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time. INFORMS J. Comput. (1996) 8:402–412Link, Google Scholar
• Kappel F., Kuntsevich A. V. An implementation of Shor's r-algorithm. Computational Optim. Appl. (2000) 15:193–205Crossref, Google Scholar
• Kedad-Sidhoum S., Rios-Solis Y., Sourd F. Lower bounds for the earliness-tardiness scheduling problem on single and parallel machines. Eur. J. Oper. Res. (2008) 189:1305–1316Crossref, Google Scholar
• Kim Y. D., Yano C. Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates. Naval Res. Logist. (1994) 41:913–933Crossref, Google Scholar
• Kovalyov M. Y., Kubiak W. A fully polynomial approximation scheme for the weighted earliness-tardiness problem. Oper. Res. (1999) 47:757–761Link, Google Scholar
• Martin P. D., Shmoys D. B., McCormick S. T., Curnigham W. H., Queyranne M. A new approach to computing optimal schedules for the job shop scheduling problem. Integer Programming and Combinatorial Optimization: Proc. Fifth Internat. IPCO Conf. (1996) 1084Vancouver, BC, Canada(Springer, Berlin) 389–403Lecture Notes in Computer ScienceCrossref, Google Scholar
• Péridy L., Pinson E., Rivreau D. Using short-term memory to minimize the weighted number of late jobs on a single machine. Eur. J. Oper. Res. (2003) 148:591–603Crossref, Google Scholar
• Sourd F. The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions. INFORMS J. Comput. (2004) 16:198–208Link, Google Scholar
• Sourd F. Scheduling with periodic availability constraints and irregular cost functions. RAIRO Oper. Res. (2007) 41:141–154Crossref, Google Scholar
• Sourd F., Kedad-Sidhoum S. The one machine problem with earliness and tardiness penalties. J. Scheduling (2003) 6:533–549Crossref, Google Scholar
• Sourd F., Kedad-Sidhoum S. A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem. J. Scheduling (2008) 11:49–58Crossref, Google Scholar
• Sousa J. P. De, Wolsey L. A. A time-indexed formulation of non-preemptive single-machine scheduling problems. Math. Programming (1992) 54:353–367Crossref, Google Scholar
• Tanaka S., Baptiste P., Kendall G., Munier-Kordon A., Sourd F. An exact algorithm for single-machine scheduling without idle time. Proc. 3rd Multidisciplinary Internat. Conf. Scheduling: Theory and Appl. (MISTA) (2007) Paris:314–317Google Scholar
• van den Akker M., Hoogeveen H., van de Velde S. Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem. INFORMS J. Comput. (2002) 14:35–51Link, Google Scholar
• van den Akker M., Hurkens C. A. J., Savelsbergh M. W. P. Time-indexed formulations for machine scheduling problems: Column generation. INFORMS J. Comput. (2000) 12:111–124Link, Google Scholar
• Yau H., Pan Y., Shi L. New solution approaches to the general single machine earliness-tardiness problem. IEEE Trans. Automation Sci. Engrg. (2008) 5(2):349–360Crossref, Google Scholar