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.
Similar content being viewed by others
References
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.
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.
U. Bagchi and R.H. Ahmadi, An improved lower bound for minimizing weighted completion times with deadlines, Operations Research 35(1987)311–313.
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.
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.
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.
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.
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.
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.
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.
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.
S. French, Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, Wiley, New York, 1982.
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.
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.
E.P.C. Kao and M. Queyranne, On dynamic programming methods for assembly line balancing, Operations Research 30(1982)375–390.
E.L. Lawler, Efficient implementation of dynamic programming algorithms for sequencing problems, Report BW 106, Mathematisch Centrum, Amsterdam, 1979.
J.K. Lenstra, A.H.G. Rinnooy Kan and P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics 1(1977)343–362.
M.E. Posner, Minimizing weighted completion times with deadlines, Operations Research 33(1985) 562–574.
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.
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.
L.E. Schrage and K.R. Baker, Dynamic programming solution of sequencing problems with precedence constraints, Operations Research 26(1978)444–449.
J.P. Sousa and L.A. Wolsey, A time indexed formulation of non preemptive single machine scheduling problems, Mathematical Programming 54(1992)353–367.
Rights 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
Issue Date:
DOI: https://doi.org/10.1023/A:1018972726534