제강-연주 공정 스케줄링을 위한 제약 프로그래밍 기반 반복 그리디 알고리즘

Abstract

We solve a steelmaking-continuous casting (SCC) scheduling problem in the steel industry with the objective to minimize a weighted sum of total earliness, tardiness, and waiting time. The SCC scheduling problem can be regarded as a variant of the hybrid flow shop scheduling problem; each job belongs to a batch, and the opera- tions at the last stage of all jobs in the same batch must be processed on the same machine without intermediate idle times. Due to its complicated characteristics, nei- ther a simple heuristic nor a commercial solver with a mathematical formulation can produce a good solution. In order to handle one of the most generic problems with unrelated parallel machines and maximum waiting time limits, we propose the iterated greedy constraint programming (IGC) algorithm that constructs a near-optimal initial solution by solving constraint programming (CP) subproblems and improves it with a CP-based large neighborhood search (LNS) procedure. We experimentally show that the IGC algorithm outperforms the state-of-the-art MIP-based matheuristic. We also apply the proposed algorithm for simpler but large-sized SCC scheduling problems in the literature. Computational experiments show that our IGC algorithm performs better than a metaheuristic and a Lagrangian heuristic for their dedicated problems. These results demonstrate that IGC is both extensible and effective for just-in-time SCC scheduling problems.