A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness |
| |
Authors: | Xiaochuan Luo Chengbin Chu |
| |
Affiliation: | 1. Key Laboratory of Process Industry Automation (MOE), Northeastern University, P.O. Box 254, Shen Yang 110004, China;2. FRE CNRS 2732 ISTIT-OSI, Universite de Technologie de Troyes, 12 rue Marie Curie C BP 2060, 10010 Troyes Cedex, France;3. School of Management, Hefei University of Technology, 193 Tunxi Road, Hefei 230009, China |
| |
Abstract: | This paper addresses the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times and no preemption where the objective is to minimize the maximum tardiness. An algorithm based on branch-and-bound permutation schemes is developed including the implementation of lower and upper bounding procedures, and three dominance rules. Computational experiments demonstrate the effectiveness of the algorithm. In the experiments, the impacts of control parameters to generate test instances on algorithm performance (CPU times) are studied by statistics methods. |
| |
Keywords: | Combinatorial optimization Maximum tardiness Sequence-dependent setup Branch and bound Single machine schedule |
本文献已被 ScienceDirect 等数据库收录! |
|