Iterated greedy algorithm with constraint programming for scheduling steelmaking-continuous casting process

We solve a steelmaking-continuous casting (SCC) scheduling problem 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 operations at the last stage require jobs in the same batch to be processed on the same machine without intermediate idle times. Due to its complicated characteristics, we propose an iterated greedy constraint programming (IGC) algorithm that constructs a near-optimal initial solution by solving constraint programming (CP) subproblems and improving on it with a CP-based large neighborhood search (LNS) procedure. We experimentally show that the IGC algorithm outperforms a state-of-the-art MIP-based matheuristic. We also apply the proposed algorithm to 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 designed for such problems. These results demonstrate that IGC is effective for just-in-time SCC scheduling problems.