A branch-and-bound algorithm with Lagrangian decomposition for parallel machine scheduling

Authors:	Tanaka Shunji, Kyoto University, Japan Araki Mituhiko, Kyoto University, Japan
Topic:	5.1 Manufacturing Plant Control
Session:	Advanced Manufacturing Applications
Keywords:	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.