» Download Article

Authors
Shunji Tanaka; Mituhiko Araki

Digital Object Identifier (DOI)
10.3182/20050703-6-CZ-1902.01465

Page Numbers:
1464-1464

Index Terms
manufacturing,scheduling algorithms,optimization,relaxation,decomposition

Abstract
The purpose of this study is to propose a new branch-and-bound algorithm for a class of scheduling problems to minimize total tardiness on identical parallel machines. In this algorithm, Lagrangian decomposition is applied to obtain better lower bounds. In addition, the job dominance conditions for the single machine tardiness problem are utilized for both restricting branches and improving the lower bounds. As will be shown by computational experiments, instances with up to 25 jobs and any number of machines are optimally solved within acceptable computational times.

References

[1] Azizoglu, M. and O. Kirca (1998). Tardiness minimization
     on parallel machines. International
    Journal of Production Economics 55, 163-168.
[2] Babu, P., L. Peridy and E. Pinson (2004). A branch
    and bound algorithm to minimize total weighted
    tardiness on a single processor. Annals of Operations
     Research 129, 33-46.
[3] Barnes, J.W. and J.J. Brennan (1977). An improved
    algorithm for scheduling jobs on identical machines.
     AIIE Transactions 9, 25-31.
[4] Du, J. and J.Y.T. Leung (1990) . Minimizing total tardiness
     on one machine is NP-hard. Mathematics
    of Operations Research 15, 483-495.
[5] Elmaghraby, S.E. and S.H. Park (1974). Scheduling
    jobs on a number of identical machines. AIIE
    Transactions 6, 1-13.
[6] Emmons, H. (1969). One-machine sequencing to minimize
     certain functions of job tardiness. Operations
     Research 17, 701-715.
[7] Fisher, M.L. (1976). A dual algorithm for the one-machine
     scheduling problem. Mathematical Programming
     11, 229-251.
[8] Fisher, M.L. (1981). The Lagrangian relaxation
    method for solving integer programming problems.
     Management Science 27, 1-18.
[9] Gupta, J.N.D. and A.R. Maykut (1973). Scheduling
    jobs on parallel processors with dynamic programming.
     Decision Sciences 4, 447-457.
[10] Ho, J.C. and Y.-L. Chang (1991). Heuristics for minimizing
      mean tardiness for m parallel machines.
     Naval Research Logistics 38, 367-381.
[11] Koulamas, C. (1994). The total tardiness problem:
     Review and extensions. Operations Research
     42, 1025-1041.
[12] Koulamas, C. (1997). Polynomially solvable total tardiness
      problems: Review and extensions. Omega
     25, 235-239.
[13] Lawler, E.L. (1977). A "pseudopolynomial" algorithm
     for sequencing jobs to minimize total tardiness.
     Annals of Discrete Mathematics 1, 331-342.
[14] Liaw, C.-F., Y.-K. Lin, C.-Y. Cheng and M. Chen
     (2003) Scheduling unrelated parallel machines to
     minimize total weighted tardiness. Computers &
     Operations Research 30, 1777-1789.
[15] Luh, P.B., D.J. Hoitomt, E. Max and K.R. Pattipati
      (1990). Schedule generation and reconfiguration
       for parallel machines. IEEE Transactions
     on Robotics and Automation 6, 687-696.
[16] Root, J.G. (1965). Scheduling with deadlines and loss
     functions on k parallel machines. Management
     Science 11, 460-475.
[17] Szwarc, W., F.D. Croce and A. Grosso (1999). Solution
      of the single machine total tardiness problem.
     Journal of Scheduling 2, 55-71.
[18] Tanaka, S. and M. Araki (2004). Two types of branch-and-bound
      algorithms for the scheduling problem
     to minimize total tardiness on identical parallel
     machines. International Symposium on Scheduling
      2004 pp. 90-93.
[19] Wilkerson, L.J. and J.D. Irwin (1971). An improved
     method for scheduling independent tasks. AIIE
     Transactions 3, 239-245.