TY - JOUR
T1 - Enhanced Branch-and-Bound Framework for a Class of Sequencing Problems
AU - Zhang, Zizhen
AU - Teng, Luyao
AU - Zhou, Mengchu
AU - Wang, Jiahai
AU - Wang, Hua
N1 - Funding Information:
Manuscript received July 24, 2018; revised January 26, 2019; accepted May 4, 2019. Date of publication May 30, 2019; date of current version April 15, 2021. This work was supported in part by the National Science Foundation of China under Grant 71601191 and Grant 61673403, and in part by the Natural Science Foundation of Guangdong Province under Grant 2016A030313264. This paper was recommended by Associate Editor S. Song. (Corresponding author: Luyao Teng.) Z. Zhang and J. Wang are with the School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510275, China, and also with the Guangdong Key Laboratory of Big Data Analysis and Processing, Sun Yat-sen University, Guangzhou 510275, China (e-mail: zhangzzh7@mail.sysu.edu.edu).
Publisher Copyright:
© 2013 IEEE.
PY - 2021/5
Y1 - 2021/5
N2 - In this paper, we propose an enhanced branch-and-bound (BB) framework for a class of sequencing problems, which aim to find a permutation of all involved elements to minimize a given objective function. We require that the sequencing problems satisfy three conditions: 1) incrementally computable; 2) monotonic; and 3) overlapping subproblems. Our enhanced BB framework is built on the classical BB process by introducing two techniques, i.e., dominance rules and caching search states. Following the enhanced BB framework, we conduct empirical studies on three typical and challenging sequencing problems, i.e., quadratic traveling salesman problem, traveling repairman problem, and talent scheduling problem. The computational results demonstrate the effectiveness of our enhanced BB framework when compared to classical BB and some exact approaches, such as dynamic programming and constraint programming. Additional experiments are carried out to analyze different configurations of the algorithm.
AB - In this paper, we propose an enhanced branch-and-bound (BB) framework for a class of sequencing problems, which aim to find a permutation of all involved elements to minimize a given objective function. We require that the sequencing problems satisfy three conditions: 1) incrementally computable; 2) monotonic; and 3) overlapping subproblems. Our enhanced BB framework is built on the classical BB process by introducing two techniques, i.e., dominance rules and caching search states. Following the enhanced BB framework, we conduct empirical studies on three typical and challenging sequencing problems, i.e., quadratic traveling salesman problem, traveling repairman problem, and talent scheduling problem. The computational results demonstrate the effectiveness of our enhanced BB framework when compared to classical BB and some exact approaches, such as dynamic programming and constraint programming. Additional experiments are carried out to analyze different configurations of the algorithm.
KW - Branch-and-bound (B&B)
KW - caching states
KW - dominance rules
KW - dynamic programming (DP)
KW - talent scheduling problem
KW - traveling salesman/repairman problem
UR - http://www.scopus.com/inward/record.url?scp=85093968002&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85093968002&partnerID=8YFLogxK
U2 - 10.1109/TSMC.2019.2916202
DO - 10.1109/TSMC.2019.2916202
M3 - Article
AN - SCOPUS:85093968002
SN - 2168-2216
VL - 51
SP - 2726
EP - 2736
JO - IEEE Transactions on Systems, Man, and Cybernetics: Systems
JF - IEEE Transactions on Systems, Man, and Cybernetics: Systems
IS - 5
M1 - 8726096
ER -