Scheduling A Steel Plant Using Constraint Programming


Alan W Smith

PhD Thesis, School of Computing, University of Leeds, 2000.

Abstract

This thesis describes the algorithms that are used within a scheduling system developed for the steelplant at British Steel's Teesside Works. The algorithms have been developed over a period lasting approximately four years and have also been used in the design of a similar system for the company's sister plant in Scunthorpe.

A description of steelmaking processes carried out at Teesside is given and work undertaken by, and on behalf of, other steelmaking companies is reviewed as is work carried out in similar problem domains.

The algorithms developed are based on the Constraint Satisfaction Problem 9CSP) paradigm. The algorithms are implemented using ILOG Solver and ILOG Scheduler, constraint programming tools for finding solutions to CSPs. The problem domain concerned is very complex and this has necessitated the development of three separate modules to tackle different parts of the overall problem. Two of the modules carry out sequencing operations and the third is a scheduling module.

All of the modules have gone through several generations of evolution to end up in the final state, this evolution is described. The modules all use domain knowledge and heuristics to control the search. All of the modules need to balance the desire to optimise with the practical requirement to generate a schedule in a reasonable time.