A branch-and-bound algorithm with Lagrangian decomposition for parallel machine scheduling
World Congress, Volume # 16 | Part# 1
Shunji Tanaka; Mituhiko Araki
Digital Object Identifier (DOI)
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.
 Azizoglu, M. and O. Kirca (1998). Tardiness minimization on parallel machines. International Journal of Production Economics 55, 163-168.  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.  Barnes, J.W. and J.J. Brennan (1977). An improved algorithm for scheduling jobs on identical machines. AIIE Transactions 9, 25-31.  Du, J. and J.Y.T. Leung (1990) . Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research 15, 483-495.  Elmaghraby, S.E. and S.H. Park (1974). Scheduling jobs on a number of identical machines. AIIE Transactions 6, 1-13.  Emmons, H. (1969). One-machine sequencing to minimize certain functions of job tardiness. Operations Research 17, 701-715.  Fisher, M.L. (1976). A dual algorithm for the one-machine scheduling problem. Mathematical Programming 11, 229-251.  Fisher, M.L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management Science 27, 1-18.  Gupta, J.N.D. and A.R. Maykut (1973). Scheduling jobs on parallel processors with dynamic programming. Decision Sciences 4, 447-457.  Ho, J.C. and Y.-L. Chang (1991). Heuristics for minimizing mean tardiness for m parallel machines. Naval Research Logistics 38, 367-381.  Koulamas, C. (1994). The total tardiness problem: Review and extensions. Operations Research 42, 1025-1041.  Koulamas, C. (1997). Polynomially solvable total tardiness problems: Review and extensions. Omega 25, 235-239.  Lawler, E.L. (1977). A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics 1, 331-342.  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.  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.  Root, J.G. (1965). Scheduling with deadlines and loss functions on k parallel machines. Management Science 11, 460-475.  Szwarc, W., F.D. Croce and A. Grosso (1999). Solution of the single machine total tardiness problem. Journal of Scheduling 2, 55-71.  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.  Wilkerson, L.J. and J.D. Irwin (1971). An improved method for scheduling independent tasks. AIIE Transactions 3, 239-245.