TY - JOUR
T1 - A Branch and Price Algorithm for Crane Assignment and Scheduling in Slab Yard
AU - Wang, Xu
AU - Zhou, Meng Chu
AU - Zhao, Qiuhong
AU - Liu, Shixin
AU - Guo, Xiwang
AU - Qi, Liang
N1 - Funding Information:
Manuscript received March 29, 2020; accepted May 16, 2020. Date of publication June 19, 2020; date of current version July 2, 2021. This article was recommended for publication by Associate Editor J. R. Morrison and Editor J. Li upon evaluation of the reviewers’ comments. This work was supported in part by NSFC under Grant 71601040, Grant 61573089, and Grant 61903229, in part by the 2019 Annual Social Science Foundation of Hebei Institutions of Higher Education under Grant SQ191015, in part by the Hebei Association Social Science and Technology Foundation under Grant 2019041201004, in part by the Dr. Research Foundation of Hebei University of Environmental Engineering under Grant 201806, in part by Liaoning Province Education Department Scientific Research Foundation under Grant L2019027, in part by the LiaoNing Revitalization Talents Program under Grant XLYC1907166, and in part by the Deanship of Scientific Research (DSR) at King Abdulaziz University under Grant RG-20-135-38. (Corresponding author: MengChu Zhou; Shixin Liu.) Xu Wang is with the School of Economics, Hebei University of Environmental Engineering, Qinhuangdao 066102, China (e-mail: wangxu@hebuee.edu.cn).
Publisher Copyright:
© 2004-2012 IEEE.
PY - 2021/7
Y1 - 2021/7
N2 - In a steel industry, a slab yard plays a role of a buffer between continuous casting stage and rolling mill. An effective assignment and scheduling of cranes can guarantee the operation efficiency in the slab yard. This work studies a multicrane scheduling problem with noncrossing constraints of slabs. A mixed-integer programming model is used to formulate the problem that minimizes the whole traveling distance of all the cranes and ensures the workload balance among cranes. As it is an NP-hard problem, classical programming mathematical methods are difficult to get an optimal solution for large-size instances. Thus, we develop a branch and price algorithm to solve this problem. First, we formulate the model as a generalized set covering problem and a set partition problem. Then, we solve them and combine the solutions to obtain the solution of the original problem. Finally, we conduct computational experiments based on real data from an iron-steel plant. The comparisons of proposed methods with an exact solution method show its effectiveness. Note to Practitioners - This work deals with a multicrane scheduling problem. Aiming to minimize the total traveling distance of all the cranes, it establishes a mixed-integer programming model with a workload balance constraint on cranes. It presents a branch and price algorithm to solve the problem whose solution complexity grows exponentially with problem size. The integration of crane assignment and scheduling enables the better utilization of cranes and faster service in iron-steel enterprises and, hence, improving customer satisfaction. The experimental results reveal the effectiveness of the proposed approach. It can readily be put into use in the steel industry.
AB - In a steel industry, a slab yard plays a role of a buffer between continuous casting stage and rolling mill. An effective assignment and scheduling of cranes can guarantee the operation efficiency in the slab yard. This work studies a multicrane scheduling problem with noncrossing constraints of slabs. A mixed-integer programming model is used to formulate the problem that minimizes the whole traveling distance of all the cranes and ensures the workload balance among cranes. As it is an NP-hard problem, classical programming mathematical methods are difficult to get an optimal solution for large-size instances. Thus, we develop a branch and price algorithm to solve this problem. First, we formulate the model as a generalized set covering problem and a set partition problem. Then, we solve them and combine the solutions to obtain the solution of the original problem. Finally, we conduct computational experiments based on real data from an iron-steel plant. The comparisons of proposed methods with an exact solution method show its effectiveness. Note to Practitioners - This work deals with a multicrane scheduling problem. Aiming to minimize the total traveling distance of all the cranes, it establishes a mixed-integer programming model with a workload balance constraint on cranes. It presents a branch and price algorithm to solve the problem whose solution complexity grows exponentially with problem size. The integration of crane assignment and scheduling enables the better utilization of cranes and faster service in iron-steel enterprises and, hence, improving customer satisfaction. The experimental results reveal the effectiveness of the proposed approach. It can readily be put into use in the steel industry.
KW - Branch and price (B and P) algorithm
KW - crane scheduling
KW - discrete-event and hybrid systems
KW - logistics
KW - optimization methods
KW - slab yard
KW - workload balancing
UR - http://www.scopus.com/inward/record.url?scp=85091007706&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85091007706&partnerID=8YFLogxK
U2 - 10.1109/TASE.2020.2996227
DO - 10.1109/TASE.2020.2996227
M3 - Article
AN - SCOPUS:85091007706
SN - 1545-5955
VL - 18
SP - 1122
EP - 1133
JO - IEEE Transactions on Automation Science and Engineering
JF - IEEE Transactions on Automation Science and Engineering
IS - 3
M1 - 9121703
ER -