Scheduling of a single crane in batch annealing process |
| |
Authors: | Lixin Tang Xie Xie Jiyin Liu |
| |
Affiliation: | 1. TLiaoning Key Laboratory of Manufacturing System and Logistics, The Logistics Institute, Northeastern University, Shenyang 110004, PR China;2. Business School, Loughborough University, Leicestershire LE11 3TU, UK |
| |
Abstract: | This paper studies a single crane scheduling problem motivated by batch annealing process in the iron and steel industry. Each coil stack placed on fixed base needs to go through two-stage processing: heating and cooling. During each stage, limited special machines (furnace and cooler) must be operated by crane, respectively. Our problem is to assign the shared machines and schedule a single crane for minimizing the last coil stack completion time (makespan). A mixed integer linear programming (MILP) model is formulated by considering both machine and crane positions. We show that the problem is NP-hard in the strong sense. Some optimal properties on the problem are derived. A two-phase algorithm is constructed for the problem. In the first phase, a fully polynomial time approximation scheme (FPTAS) is developed for the assignment subproblem. In the second phase, a heuristics is proposed for the scheduling subproblem. From an absolute performance point of view, we analyze the quality of the two-phase algorithm. We also consider special cases where some properties or algorithms are developed. In order to further verify the performance of the two-phase algorithm, we develop a lower bound on the optimal objective function. Computational experiments on the randomly generated problem instances show that the algorithm is close to the lower bound within a reasonable computation time. |
| |
Keywords: | Crane scheduling Batch annealing process Strongly NP-hard Heuristics Absolute performance analysis |
本文献已被 ScienceDirect 等数据库收录! |
|