A new heuristic for plant-wide schedule coordination problems: The intersection coordination heuristic

Abstract This work addresses the coordination heuristics of two large-scale flexible multi-stage batch (flow shop) scheduling problems, which are currently solved independently by tailored algorithms that consist of mixed-integer linear optimization and heuristics. The approach is motivated by an industrial-scale steel making process that consists of a melt shop as the first production section and a hot rolling mill as the second production section. The first section produces intermediate products, i.e. slabs, which are stored in an intermediate storage area and which are consumed by the second section. The coordination objective is to reduce the storage time of the slabs or, more generally, the storage time between two sections taking into account the objectives of the two distributed scheduling solutions. A generic model formulation for multi-stage batch schedule coordination problems is presented. Three different schedule coordination heuristics are discussed and compared for simplified case studies: the heuristic based on Lagrangean decomposition (LD), a derivative-free optimization algorithm – Multilevel Coordinate Search (MCS), the new intersection coordination heuristic (IC) and monolithic MILP model solved by CPLEX (MONO). The proposed bi-level intersection coordination heuristic uses the knowledge on the bottlenecks of the two processes to build a simplified model for the upper-level coordinator which coordinates the lower-level distributed MILP schedulers via coordination variables iteratively. The numerical comparisons show the advantage of the IC among these three coordination approaches in terms of solution quality and computational effort. The limitations of LD, MCS, MONO and IC for the plant-wide schedule coordination problem are discussed in view of the requirements of large-scale industrial schedule coordination problems.