TY - JOUR
T1 - New dominance rules and exploration strategies for the 1|ri |ΣU i scheduling problem
AU - Kao, Gio K.
AU - Sewell, Edward C.
AU - Jacobson, Sheldon H.
AU - Hall, Shane N.
N1 - Funding Information:
Acknowledgements The authors wish to thank the editor and three anonymous referees for their insightful comments and suggestions, resulting in a significantly improved manuscript. The computational results reported were obtained using the Simulation and Optimization Laboratory. This research has been supported in part by the Air Force Office of Scientific Research (FA9550-07-1-0232, FA9550-10-1-0387). 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.
PY - 2012/4
Y1 - 2012/4
N2 - The paper proposes a new exact approach, based on a Branch, Bound, and Remember (BB&R) algorithm that uses the Cyclic Best First Search (CBFS) strategy, for the 1 |ri | σ U i scheduling problem, a single machine scheduling problem, where the objective is to find a schedule with the minimum number of tardy jobs. The search space is reduced using new and improved dominance properties and tighter upper bounds, based on a new dynamic programming algorithm. Computational results establish the effectiveness of the BB&R algorithm with CBFS for a broad spectrum of problem instances. In particular, this algorithm was able to solve all problems instances, up to 300 jobs, while existing best known algorithms only solve problems instances up to 200 jobs. Furthermore, the BB&R algorithm with CBFS runs one to two orders of magnitude faster than the current best known algorithm on comparable instances.
AB - The paper proposes a new exact approach, based on a Branch, Bound, and Remember (BB&R) algorithm that uses the Cyclic Best First Search (CBFS) strategy, for the 1 |ri | σ U i scheduling problem, a single machine scheduling problem, where the objective is to find a schedule with the minimum number of tardy jobs. The search space is reduced using new and improved dominance properties and tighter upper bounds, based on a new dynamic programming algorithm. Computational results establish the effectiveness of the BB&R algorithm with CBFS for a broad spectrum of problem instances. In particular, this algorithm was able to solve all problems instances, up to 300 jobs, while existing best known algorithms only solve problems instances up to 200 jobs. Furthermore, the BB&R algorithm with CBFS runs one to two orders of magnitude faster than the current best known algorithm on comparable instances.
KW - Branch and bound algorithms
KW - Dynamic programming
KW - Scheduling theory and algorithms
UR - http://www.scopus.com/inward/record.url?scp=84862020527&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862020527&partnerID=8YFLogxK
U2 - 10.1007/s10589-010-9378-7
DO - 10.1007/s10589-010-9378-7
M3 - Article
AN - SCOPUS:84862020527
SN - 0926-6003
VL - 51
SP - 1253
EP - 1274
JO - Computational Optimization and Applications
JF - Computational Optimization and Applications
IS - 3
ER -