Abstract
A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn 2 and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
K.R. Baker and J.B. Martin, “An experimental comparison of solution algorithms for the single-machine tardiness problem”,Naval Research Logistics Quarterly 21 (1) (1974) 187–199.
K.R. Baker,Introduction to sequencing and scheduling (Wiley, New York, 1974).
D.C. Carroll, “Heuristic sequencing of single and multi-component orders”, Ph.D. dissertation, Massachusetts Institute of Technology (June 1965).
S.E. Elmaghraby, “The one machine sequencing problem with delay costs”,Journal of Industrial Engineering 17 (2) (1968).
H. Emmons, “One machine sequencing to minimize certain functions of job tardiness”,Operations Research 17 (4) (1969).
M.L. Fisher, “Optimal solution of scheduling problems using Lagrange multipliers: Part I”Operations Research 21 (5) (1973) 1114–1127.
M.L. Fisher, W. Northup and J.F. Shapiro, “Constructive duality in discrete optimization”,Mathematical Programming, to appear.
M.L. Fisher and J.F. Shapiro, “Constructive duality in integer programming”,SIAM Journal on Applied Mathematics 27 (1) (1974).
R.S. Garfinkel and G.L. Nemhauser,Integer programming (Wiley, New York, 1972).
L. Gelders and P.R. Kleindorfer, “Coordinating aggregate and detailed scheduling decisions in the one-machine job shop: Part I, theory”,Operations Research 22 (1974) 46–60.
A.M. Geoffrion, “Lagrangian relaxation for integer programming”,Mathematical Programming Study 2 (1974) 82–114.
P.C. Gilmore and R.E. Gomory, “A linear programming approach to the cutting-stock problem”,Operations Research 19 (1961) 849–859.
G.A. Gorry, J.F. Shapiro and L.A. Wolsey, “Relaxation methods for pure and mixed integer programming problems”,Management Science 18 (1972) 229–239.
M. Held and R.M. Karp, “A dynamic programming approach to sequencing problems”,SIAM Journal 10 (2) (1962).
M. Held and R.M. Karp, “The travelling-salesman problem and minimum spanning trees: Part II”,Mathematical Programming, 1 (1) (1971) 6–25.
M. Held, P. Wolfe and H.P. Crowder, “Validation of subgradient optimization”,Mathematical Programming 6 (1) (1974) 62–88.
W.W. Hogan, R.E. Marsten and J.W. Blankenship, “The BOXSTEP method for large scale optimization”,Operations Research 23 (3) (1975) 389–405.
E.L. Lawler, “On scheduling problems with deferral costs”,Management Science 9 (4) (1963).
T.L. Morin and R.E. Marsten, “Branch and bound strategies for dynamic programming”,Operations Research 24 (4) (1976) 611–627.
G.L. Nemhauser,Introduction to dynamic programming (Wiley, New York, 1966).
A.H.G. Rinnooy Kan, B.J. Lageweg and J.K. Lenstra, “Minimizing total cost in one-machine scheduling”,Operations Research 23 (5) (1975) 908–927.
A.H.G. Rinnooy Kan, B.J. Lageweg and J.K. Lenstra, private communication (September 1975).
J. Shwimer, “On then-job, one machine, sequence-independent scheduling problem with tardiness penalties: a branch-bound solution”,Management Science 18 (6) (1972) 301–313.
V. Srinivasan, “A hybrid algorithm for the one machine sequencing problem to minimize total tardiness”,Naval Research Logistics Quarterly 18 (3) (1971) 317–327.
Author information
Authors and Affiliations
Additional information
This work was supported in part by National Science Foundation Grant SOC-7402516.
Rights and permissions
About this article
Cite this article
Fisher, M.L. A dual algorithm for the one-machine scheduling problem. Mathematical Programming 11, 229–251 (1976). https://doi.org/10.1007/BF01580393
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580393