Scheduling Time-Critical Flowshops: An Example from the Steel Industry

Production in metals and chemicals industry imposes tight maximal time lag constraints between some process stages, leading to time-critical flowshop problems that are characterized by constraints restricting the work-in-progress inventory at some stations to be effectively zero. We study a complex industrial scheduling problem arising from steel manufacturing with time-critical flowshop structure. Our core problem has a flowshop structure with multiple modes and recipes, sequence dependent setup times, strict precedence constraints between certain jobs, and inventory considerations.

We present a novel approach to solve this class of problems by decomposing it into stages and integrating integer programming (IP) with constraint programming (CP) through logic-based Benders decomposition. We enhance our technique with a special class of aggregate resource use inequalities, obtained through a detailed constraint programming based schedule for each job. We further strengthen our formulation through the polyhedral study of an important common substructure, single machine scheduling with sequence-dependent setup times problem. Our solution method has been successfully deployed in the daily operations of a large integrated steelmaker with improvements in ontime delivery from 75% to over 90%.

By: Fatima Kilinç-Karzan, Jayant R. Kalagnanam, Andrew J. Davenport, Stuart Siegel, Chandra Reddy

Published in: RC25065 in 2010


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .