TY - JOUR

T1 - A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times

AU - Sewell, Edward C.

AU - Sauppe, Jason J.

AU - Morrison, David R.

AU - Jacobson, Sheldon H.

AU - Kao, Gio K.

N1 - Funding Information:
Acknowledgments The authors would like to thank the anonymous referee for the helpful comments, and in particular the suggestions for the computational results section, which led to a significantly improved paper. This research has been supported in part by the Air Force Office of Scientific Research (FA9550-07-1-0232, FA9550-10-1-0387), as well as the Department of Defense (DoD) through the National Defense Science & Engineering Graduate Fellowship (NDSEG) Program. The views expressed in this paper are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, or the United States Government. The computational results reported were obtained with support from the Simulation and Optimization Laboratory at the University of Illinois.

PY - 2012/12

Y1 - 2012/12

N2 - This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the 1|STsd |∑Ti scheduling problem, a single machine scheduling problem with sequence dependent setup times where the objective is to find a schedule with minimum total tardiness. The BB&R algorithm incorporates memory-based dominance rules to reduce the solution search space. The algorithm creates schedules in the reverse direction for problems where fewer than half the jobs are expected to be tardy. In addition, a branch and bound algorithm is used to efficiently compute tighter lower bounds for the problem. This paper also presents a counterexample for a previously reported exact algorithm in Luo and Chu (Appl Math Comput 183(1):575-588, 2006) and Luo et al. (Int J Prod Res 44(17):3367-3378, 2006). Computational experiments demonstrate that the algorithm is two orders of magnitude faster than the fastest exact algorithm that has appeared in the literature. Computational experiments on two sets of benchmark problems demonstrate that the CBFS search exploration strategy can be used as an effective heuristic on problems that are too large to solve to optimality.

AB - This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the 1|STsd |∑Ti scheduling problem, a single machine scheduling problem with sequence dependent setup times where the objective is to find a schedule with minimum total tardiness. The BB&R algorithm incorporates memory-based dominance rules to reduce the solution search space. The algorithm creates schedules in the reverse direction for problems where fewer than half the jobs are expected to be tardy. In addition, a branch and bound algorithm is used to efficiently compute tighter lower bounds for the problem. This paper also presents a counterexample for a previously reported exact algorithm in Luo and Chu (Appl Math Comput 183(1):575-588, 2006) and Luo et al. (Int J Prod Res 44(17):3367-3378, 2006). Computational experiments demonstrate that the algorithm is two orders of magnitude faster than the fastest exact algorithm that has appeared in the literature. Computational experiments on two sets of benchmark problems demonstrate that the CBFS search exploration strategy can be used as an effective heuristic on problems that are too large to solve to optimality.

KW - Branch and bound algorithms

KW - Dominance rules

KW - Dynamic programming

KW - Scheduling theory and algorithms

UR - http://www.scopus.com/inward/record.url?scp=84869493632&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869493632&partnerID=8YFLogxK

U2 - 10.1007/s10898-011-9793-z

DO - 10.1007/s10898-011-9793-z

M3 - Article

AN - SCOPUS:84869493632

SN - 0925-5001

VL - 54

SP - 791

EP - 812

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 4

ER -