A Branch and Price Algorithm for Crane Assignment and Scheduling in Slab Yard

Xu Wang, Meng Chu Zhou, Qiuhong Zhao, Shixin Liu, Xiwang Guo, Liang Qi

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number9121703
Pages (from-to)1122-1133
Number of pages12
JournalIEEE Transactions on Automation Science and Engineering
Volume18
Issue number3
DOIs
StatePublished - Jul 2021

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • Branch and price (B and P) algorithm
  • crane scheduling
  • discrete-event and hybrid systems
  • logistics
  • optimization methods
  • slab yard
  • workload balancing

Fingerprint

Dive into the research topics of 'A Branch and Price Algorithm for Crane Assignment and Scheduling in Slab Yard'. Together they form a unique fingerprint.

Cite this