Skip to main content
SpringerLink
Log in

A dynamic programming algorithm for single machine scheduling with ready times

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We propose a dynamic programming algorithm for the single machine scheduling problem with ready times and deadlines to minimize total weighted completion time. Weights may be positive or negative and the cost function may be non-regular. This problem appears as a subproblem in the Dantzig-Wolfe decomposition of the job-shop scheduling problem. We show that the algorithm is polynomial if time window length is bounded by a constant and times are integer-valued. We present computational results for problems with up to 200 jobs.

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

  1. T.S. Abdul-Razaq and C.N. Potts, Dynamic programming state-space relaxation for single-machine scheduling, Journal of the Operational Research Society 39(1988)141–152.

    Google Scholar 

  2. T.S. Abdul-Razaq, C.N. Potts and L.N. Van Wassenhove, A survey of algorithms for the single machine total weighted tardiness scheduling problem, Discrete Applied Mathematics 26(1990)235–253.

    Google Scholar 

  3. U. Bagchi and R.H. Ahmadi, An improved lower bound for minimizing weighted completion times with deadlines, Operations Research 35(1987)311–313.

    Google Scholar 

  4. K.R. Baker and L.E. Schrage, Finding an optimal sequence by dynamic programming: An extension to precedence-related tasks, Operations Research 26(1978)111–121.

    Google Scholar 

  5. S.P. Bansal, Single machine scheduling to minimize weighted sum of completion times with secondary criterion — A branch and bound approach, European Journal of Operational Research 5(1980)177–181.

    Google Scholar 

  6. H. Belouadah, M.E. Posner and C.N. Potts, Scheduling with release dates on a single machine to minimize total weighted completion time, Discrete Applied Mathematics 36(1992)213–231.

    Google Scholar 

  7. L. Bianco and S. Ricciardelli, Scheduling of a single machine to minimize total weighted completion time subject to release dates, Naval Research Logistics Quarterly 29(1982)151–167.

    Google Scholar 

  8. T.C.E. Cheng, Dynamic programming approach to the single-machine sequencing problem with different due dates, Computers and Mathematics with Applications 19(1990)1–7.

    Google Scholar 

  9. M.E. Dyer and L.A. Wolsey, Formulating the single-machine sequencing problem with release dates as a mixed integer program, Discrete Applied Mathematics 26(1990)255–270.

    Google Scholar 

  10. J. Erschler, G. Fontan, C. Merce and F. Roubellat, A new dominance concept in scheduling n jobs on a single machine with ready times and due dates, Operations Research 31(1983)114–127.

    Google Scholar 

  11. M.L. Fisher, B.J. Lageweg, J.K. Lenstra and A.H.G. Rinnooy Kan, Surrogate duality relaxation for job shop scheduling, Discrete Applied Mathematics 5(1983)65–75.

    Google Scholar 

  12. S. French, Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, Wiley, New York, 1982.

    Google Scholar 

  13. A.M.A. Hariri and C.N. Potts, An algorithm for single machine sequencing with release dates to minimize total weigthed completion time, Discrete Applied Mathematics 5(1983)99–109.

    Google Scholar 

  14. I. Ioachim, S. Gélinas, J. Desrosiers and F. Soumis, Shortest path problem with linear inconvenience costs on the time windows, Cahiers du Gérad G–92–42, École des Hautes Études Commerciales, Montréal, Canada, H3T 1V6, 1994.

    Google Scholar 

  15. E.P.C. Kao and M. Queyranne, On dynamic programming methods for assembly line balancing, Operations Research 30(1982)375–390.

    Google Scholar 

  16. E.L. Lawler, Efficient implementation of dynamic programming algorithms for sequencing problems, Report BW 106, Mathematisch Centrum, Amsterdam, 1979.

    Google Scholar 

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

    Google Scholar 

  18. M.E. Posner, Minimizing weighted completion times with deadlines, Operations Research 33(1985) 562–574.

    Google Scholar 

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

    Google Scholar 

  20. C.N. Potts and L.N. Van Wassenhove, Dynamic programming and decomposition approaches for the single machine total tardiness problem, European Journal of Operational Research 32(1987) 405–414.

    Google Scholar 

  21. L.E. Schrage and K.R. Baker, Dynamic programming solution of sequencing problems with precedence constraints, Operations Research 26(1978)444–449.

    Google Scholar 

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

    Google Scholar 

Download references

Authors
  1. Sylvie Gélinas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Francois Soumis
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gélinas, S., Soumis, F. A dynamic programming algorithm for single machine scheduling with ready times. Annals of Operations Research 69, 135–156 (1997). https://doi.org/10.1023/A:1018972726534

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018972726534

Keywords

Search

Navigation