Skip to main content
SpringerLink
Log in

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Akturk, M. S., & Ozdemir, D. (2000). An exact approach to minimizing total weighted tardiness with release dates. IIE Transactions, 32, 10911101.

    Google Scholar 

  • Avella, P., Boccia, M., & DAuria, B. (2005). Near-optimal solutions of large-scale single-machine scheduling problems. INFORMS Journal on Computing, 17, 183–191.

    Article  Google Scholar 

  • Baker, K. R., & Scudder, G. (1990). Sequencing with earliness and tardiness penalties: a review. Operations Research, 38, 22–36.

    Google Scholar 

  • Belouadah, H., & Potts, C. N. (1994). Scheduling identical parallel machines to minimize total weighted completion time. Discrete Applied Mathematics, 48, 201–218.

    Article  Google Scholar 

  • Bülbül, K., Kaminsky, P., & Yano, C. (2007). Preemption in single machine earliness/tardiness scheduling. Journal of Scheduling 10, 271–292.

    Article  Google Scholar 

  • Chang, P.-C. (1999). A branch and bound approach for single machine scheduling with earliness and tardiness penalties. Computers & Mathematics with Applications, 37, 133–144.

    Article  Google Scholar 

  • Chen, J. Y., & Lin, S. F. (2004). Minimizing weighted earliness and tardiness penalties in single-machine scheduling with idle time permitted. Naval Research Logistics, 49, 760–780.

    Article  Google Scholar 

  • Chen, H., Chu, C., & Proth, J. M. (1998). An improvement of the Lagrangean relaxation approach for job shop scheduling: a dynamic programming method. IEEE Transactions on Robotics and Automation, 14, 786–795.

    Article  Google Scholar 

  • Christofides, N., Alvarez-Valdes, R., & Tamarit, J. M. (1987). Project scheduling with resource constraints: a branch and bound approach. European Journal of Operational Research, 29, 262–273.

    Article  Google Scholar 

  • Chu, C. (1992). A branch and bound algorithm to minimize total tardiness with different release dates. Naval Research Logistics, 39, 265–283.

    Article  Google Scholar 

  • De Sousa, J. P., & Wolsey, L. A. (1992). A time-indexed formulation of non-preemptive single-machine scheduling problems. Mathematical Programming, 54, 353–367.

    Article  Google Scholar 

  • Esteve, B., Aubijoux, C., Chartier, A., & Tkindt, V. (2006). A recovering beam search algorithm for the single machine just-in-time scheduling problem. European Journal of Operational Research, 172, 798–813.

    Article  Google Scholar 

  • Fisher, M. L. (1976). A dual algorithm for the one-machine scheduling problem. Mathematical Programming, 11, 229–251.

    Article  Google Scholar 

  • Fry, T. D., Leong, G., & Rakes, T. (1987). Single machine scheduling: a comparison of two solution procedures. Omega, 15, 277–282.

    Article  Google Scholar 

  • Fry, T. D., Armstrong, R. D., Darby-Dowman, K., & Philipoom, P. R. (1996). A branch and bound procedure to minimize mean absolute lateness on a single processor. Computers & Operations Research, 23, 171–182.

    Article  Google Scholar 

  • Garey, M. R., Tarjan, R. E., & Wilfong, G. T. (1988). One-processor scheduling with symmetric earliness and tardiness penalties. Mathematics of Operations Research, 13, 330–348.

    Google Scholar 

  • Gordon, V., Proth, J. M., & Chu, C. (2002). A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, 139, 1–25.

    Article  Google Scholar 

  • Hassin, R., & Shani, M. (2005). Machine scheduling with earliness, tardiness and non-execution penalties. Computers & Operations Research, 32, 683–705.

    Article  Google Scholar 

  • Hendel, Y., & Sourd, F. (2006). Efficient neighborhood search for just-in-time scheduling problems. European Journal of Operational Research, 173, 108–119.

    Article  Google Scholar 

  • Hoogeveen, J. A. (2005). Multicriteria scheduling. European Journal of Operational Research, 167, 592–623.

    Article  Google Scholar 

  • Hoogeveen, J. A., & van de Velde, S. L. (1996). A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time. INFORMS Journal on Computing, 8, 402–412.

    Google Scholar 

  • Jouglet, A., Baptiste, Ph., & Carlier, J. (2004). Branch-and-bound algorithms for total weighted tardiness. In J. Y. T. Leung (Ed.), Computer & information science series : vol. 13. Handbook of scheduling: algorithms, models and performance analysis. London: Chapman & Hall/CRC.

    Google Scholar 

  • Kaskavelis, C. A., & Caramanis, M. C. (1998). Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems. IIE Transactions, 30, 1085–1097.

    Google Scholar 

  • Kedad-Sidhoum, S., Rios-Solis, Y., & Sourd, F. (2007, in press). Lower bounds for the earliness-tardiness scheduling problem on single and parallel machines. European Journal of Operational Research. doi:10.1016/j.ejor.2006.05.052.

  • Kim, Y. D., & Yano, C. (1994). Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates. Naval Research Logistics, 41, 913–933.

    Article  Google Scholar 

  • Lasserre, J.-B., & Queyranne, M. (1992). Generic scheduling polyhedra and a new mixed-integer formulation for single-machine scheduling. In Proceedings of the 2nd IPCO conference.

  • Lauff, V., & Werner, F. (2004). Scheduling with common due date, earliness and tardiness penalties for multimachine problems: a survey. Mathematical and Computer Modelling, 40, 637–655.

    Article  Google Scholar 

  • Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.

    Article  Google Scholar 

  • Liaw, C. F. (1999). A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem. Computers & Operations Research, 26, 679–693.

    Article  Google Scholar 

  • Luh, P. B., Hoitomt, D. J., Max, E., & Pattipati, K. R. (1990). Schedule generation and reconfiguration for parallel machines. IEEE Transactions on Robotics and Automation, 6, 687–696.

    Article  Google Scholar 

  • Möhring, R. H., Schulz, A. S., Stork, F., & Uetz, M. (2003). Solving project scheduling problems by minimum cut computations. Management Science, 49, 330–350.

    Article  Google Scholar 

  • Péridy, L., Pinson, E., & Rivreau, D. (2003). Using short-term memory to minimize the weighted number of late jobs on a single machine. European Journal of Operational Research, 148, 591–603.

    Article  Google Scholar 

  • Potts, C. N. (1985). A Lagrangean based branch and bound algorithm for single machine sequencing with precedence constraints to minimize total weighted completion time. Management Science, 31, 1300–1311.

    Google Scholar 

  • Potts, C. N., & Van Wassenhove, L. N. (1983). An algorithm for single machine sequencing with deadlines to minimize total weighted completion time. European Journal of Operational Research, 12, 379–387.

    Article  Google Scholar 

  • Potts, C. N., & Van Wassenhove, L. N. (1985). A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 33, 363–377.

    Google Scholar 

  • Queyranne, M., & Schulz, A. S. (1994). Polyhedral approaches to machine scheduling (Technical Report 408-1994). Technische Universität Berlin.

  • Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics, 3, 59–66.

    Article  Google Scholar 

  • Sourd, F. (2004). The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions. INFORMS Journal on Computing, 16, 198–208.

    Article  Google Scholar 

  • Sourd, F. (2005). Optimal timing of a sequence of tasks with general completion costs. European Journal of Operational Research, 165, 82–96.

    Article  Google Scholar 

  • Sourd, F. (2006). Dynasearch neighborhood for the earliness-tardiness scheduling problem with release dates and setup constraints. Operations Research Letters, 34, 591–598.

    Article  Google Scholar 

  • Sourd, F., & Kedad-Sidhoum, S. (2003). The one machine problem with earliness and tardiness penalties. Journal of Scheduling, 6, 533–549.

    Article  Google Scholar 

  • Tanaka, S., Sasaki, T., & Araki, M. (2003). A branch-and-bound algorithm for the single-machine weighted earliness-tardiness scheduling problem with job independent weights. In IEEE international conference on systems, man and cybernetics (pp. 1571–1577).

  • Valente, J. M. S., & Alves, R. A. F. S. (2005). An exact approach to early/tardy scheduling with release dates. Computers & Operations Research, 32, 2905–2917.

    Article  Google Scholar 

  • Verma, S., & Dessouky, M. (1998). Single-machine scheduling of unit-time jobs with earliness and tardiness penalties. Mathematics of Operations Research, 23, 930–943.

    Article  Google Scholar 

  • Wan, G., & Yen, B. P. C. (2002). Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. European Journal of Operational Research, 142, 271–281.

    Article  Google Scholar 

  • Yau, H., Pan, Y., & Shi, L. (2006, to appear). New solution approaches to the general single machine earliness-tardiness problem. IEEE Transactions on Automation Science and Engineering.

Download references

Author information

Authors and Affiliations

  1. LIP6, CNRS, 4 place Jussieu, 75252, Paris, Cedex 05, France

    Francis Sourd

  2. LIP6, Université Pierre et Marie Curie, 4 place Jussieu, 75252, Paris, Cedex 05, France

    Safia Kedad-Sidhoum

Authors
  1. Francis Sourd
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Safia Kedad-Sidhoum
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francis Sourd.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sourd, F., Kedad-Sidhoum, S. A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem. J Sched 11, 49–58 (2008). https://doi.org/10.1007/s10951-007-0048-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-007-0048-2

Keywords

Search

Navigation