Project Overview
We developed a hot strip mill scheduling system.
We adopted a coarse-to-fine approach for the problem: solving
global hard constraints first, and improving the solution quality
later. Finally the system automatically generates a better schedule than
human scheduling experts, who need more than ten years training, do.
Hot Mill Scheduling Problem
Hot strip mill process is the first rolling process for producing thin
coils after steel making, where a slab, a thick (250~270mm) rectangle
plate of steel, is rolled into a thin (1.2~8mm) coil under very high
temperature and pressure. Because of the wear of roller surface the
rollers are replaced periodically and a sequence of slabs between the
roller changes are called a round. The scheduling problem for the hot
strip mill is to determine several rounds from a given slab pool (a set of
available slabs to schedule) at a time. Most of the constraints considered
in sequencing slabs come from the rolling condition of a roller. Higher
temperature and pressure required to produce thinner coil gradually damage
the rolling condition, so we need to avoid too long consecutive rolling of
thin coils and insert thicker coils for recovering the rolling condition.
Hot strip mill process in coil production process flow
We can regard hot strip mill problem as a mixture of a knapsack problem,
a constraint satisfaction problem, and a traveling salesperson problem.
- Knapsack problem (slab selection): we need to select appropriate subsets
of slabs for rounds from a slab pool in order to balance the quality of
rounds and maximize the usage of rollers.
-
Constraint satisfaction problem (global constraints): constraints on slabs
apart in a round such as mixture and precedence between subsequences of
thin coils, earlier positioning of high surface quality slabs, and minimum
requirement of recovery slabs between thin coils must be satisfied.
-
Traveling salesperson problem (local constraints): constraints between a
pair of adjacent slabs must be satisfied and transition of attribute
values such as band width, band gauge, temperature, and tensile should be
as smooth as possible.
Historically in the literature the aspects of knapsack problem and
traveling salesperson problem are emphasized in the scheduling
algorithm. However, if the ratio of thin coils,
which must satisfy strong global constraints, in a slab pool is relatively
high, it makes the scheduling problem more difficult.
An algorithm for HSM problem
The challenge of the project is to find a feasible and near optimal
schedule within a practical time (less than half an hour). The quality of
a round depends mostly on the selection of thin coils. Therefore we focus
on the selection of thin coils and have taken coarse-to-fine approach to
build two or three rounds in four steps.
-
Clustering: as a preprocessing, we make greedily a small subsequence
(cluster) of slabs satisfying some local constraints. Within a
subsequence, mixture and precedence relation of thin coils are also
satisfied.
-
Rough sequencing: we determine a block pattern of slab clusters, which
reflects typical pattern of a round; special surface quality coils and
three iterations of thin coils and thick coils. We formulated an
assignment problem of slab clusters to a block pattern as integer
programming. Slab selection and some of global constraints are solved in
this phase.
-
Detail sequencing: we complete initial feasible solution by inserting
slabs between slab clusters selected in rough sequencing. Both global and
local constraints are solved in this phase.
-
Local improvement: we applied local search operations (insert, delete, and
exchange slabs) in order to improve the length of rounds and the smooth
transition of slab attributes involved in local constraints.
By solving key global constraints in rough sequencing phase, we could
obtain a promising skeleton of a round leading to a better schedule, and
restrict the search space in an effective way. As a result, in shorter
time and without any post manual editing, the scheduling system generates,
in most cases, feasible and longer rounds competitive to ones generated by
a human scheduling expert.
Coarse to fine approach to hot strip mill scheduling
|
|
