Direct Hot Charge Steel Scheduling

Contents

Introduction

This is an overview of model steel steel facility

• We start with iron ore, limestone, and coal, then
  • iron ore is pelletized and sintered,
  • limestone is crushed,
  • and coal is made into coke in coke ovens.
• The blast furnace operates continuously and sends hot iron via torpedo cars to the basic oxygen furnace (BOF) or converter.
• Molten iron is converted into steel in the (BOF) by adding oxygen to burn off the carbon.
• Steel is further treated in the ladle metallurgical facility (LMF) or refinement facility.
• Steel is transfered via a ladle to a tundish.
• The tundish supplies a constant stream of steel to the continuous caster.
• Some slabs are cast to the slab inventory...
• ...while others go to a reheat furnace and into hot strip mill.
• Some coils remain in the coil inventory after being produced.

Definition of Terms

Some common terms

tundish

one or more heats

heat

the amount of molten iron that can be converted to molten steel in one batch

caster string

a sequence of tundishes; the batch on the caster between caster turnarounds

round

a sequence of heats; the batch on the hot strip mill between roll changes

order

the basic input to be scheduled; it typically has a specification of type, quantity, and due date

Standard Operating Modes

cold charge

let the slabs cool all the way down to ambient; they must be reheated to be rolled

hot charge

let the slabs cool just a little; less reheating is necessary

direct hot charge

we try to get the slabs to the HSM as quick as possible (less than 20 minutes); some slight reheating may be necessary

direct rolling

the cast slabs go directly to the HSM; only the edges need to be slightly reheated

The DHCR Facility

The facility has the following characteristics

• about 280 tons per hour of molten iron from blast furnace
• each heat contains a maximum of 220 tons
• around 40 minutes are required to process heat
• the caster is dual strand with width ranging from 23 to 63 inches
• there are six round types with gauge ranging from 0.051 to 0.675
• there are around 1000 cast grades
• the orderbook contains about 3000 orders
• there is a fixed maintenance schedule

A DHCR Order

Each order contains the following information

• identifier
• due date
• cast grade
• set of possible round types
• chemistry information
• roll width
• roll gauge
• customer name

Objectives

The objective is sequence the orders so that the constraints are not violated and find multiple solutions that span the space of objectives

• cost
• throughput
• on-time delivery
• direct hot charge proportion
• tundish utilization
• number of different grades in tundish
• roll usage in HSM
• stock slab inventory
• average priority
• turnarounds

It's most likely that you cannot simultaneously optimize all of them.

Spanning the space with a non-dominated set is the best approach because it allows the user to make the final decision among the best solutions.

Constraints

The following constraints must be satisfied:

• steel grades in a tundish must be compatible
• no more than 8 tundishes before a tundish reline is required
• width decrease between slabs can be no more than 2 inches
• there can be no width increase between slabs
• slabs produced on both strands must have the same width
• no more than 40 slabs can be cast within 3 inches of width
• the round type sequencing rules must be followed
• the maximum spread or squeeze is 2.5 percent
• precedence constraints
  • the special round types are sine wave, cold roll critical, light gauge mild, or light gauge high-strength low-alloy
  • these special round types must be preceded by a regular or general roll change round

So how to we solve this problem?

What about using an exhaustive search?

Given 5 coils to sequence, there are 5! = 120 permutations

Given 10 coils to sequence, there are 10! = 3.6 million permutations

Say we could do 1 evaluation per microsecond

Then we could do this problem in 3.63 seconds

Given 15 coils to sequence, there are 15! = 1.3 trillion permutations

At the same rate it would take 2.5 years to evaluate all the possible sequences.

Heuristic search is our only chance for this problem

Some people would tend to disagree. Other techniques include a variety of improvement algorithms (genetic algorithms, asynchronous teams) that start with a feasible or infeasible and improve it.

Variable-Labeling Search

This technique includes standard depth-first and breadth-first search.

Given n variables, { v₁ , v₂ , ... , v_n } , each of which can take on values in a finite domain D of size k, we generate a graph of the possible combinations of value and discover this graph in a depth-first or breadth-first fashion. Example: n = 3, k = 6, D = d₁, d₂, ... , d₆

There are a variety of enhancements to these algorithms (like forward checking and back jumping).

These algorithms are very well studied and fairly well understood.

Different Tools for Different Problems

Problem: Given n vertices, k colors, and and adjacency list (or matrix), assign a color value to each vertex v such that no two adjacent vertices have the same color. This is called graph coloring.

Approach: Use depth first search.

Question: Can we apply these approaches to steel mill scheduling which is a kind of grouping/sequencing problem?

Answer: Probably not...

See the notes after the next slide for why probably not.

Using Variable-Labeling to Solve Sequencing/Grouping Problems

Given a set of elements E = { e₁, e₂, ... e_n } generate a set S = { s₁, s₂, ... s_m } of m sequences, m <= n, so that

• taken together, the set of sequences contain all elements in E
• there are no constraint violations within any sequence and
• the number of sequences, m is minimized

We can formulate this as a variable-labeling problem if we mark each element as belonging to a particular sequence s.

The main problem with this approach is that once a constraint violation is discovered, we can no longer extend a sequence without backtracking.

For a problem with n elements, there are n+1 possible arrangements of the sequences in the set. For example, for 4 elements, the set could contain 4 sequences of 1 element, 1 sequence with 3 elements and 1 with 1 element, two sequences of two elements, two sequences of 1 element and 1 sequence of two elements, or four sequences of 1 element. Since we are doing variable labeling and hence we define our variables in advance, we have to treat each one of these cases individually.

Non-Dominated Sets

A non-dominated set is a set in which the attributes of no element are either dominated by or dominate the attributes of another element.

For an element to dominate another element, at least one of its attributes must be better than the corresponding attribute of the other attribute, and none of its attributes can be worse than the corresponding attribute of the other element. Thus, an element can have some set of attributes that are better than the corresponding attributes of another element, but if one attribute is worse, than neither element dominates the other.

Non-dominated sets are useful for multi-objective optimization.

Given a non-dominated set that spans the objective space, the decision of which element to choose is left to a human.

Example: A set of three attributes [ slabInventory tardiness tundishChanges ] representing the goodness of a particular schedule.

We generate three schedules that form a non-dominated set

   A = [ -10000  -100 -25 ]
   B = [  -3000 -2500 -23 ]
   C = [  -5000 -3800 -17 ]

Depending on the needs of the business, a human may choose A, B, or C.

The EBB Search Algorithm

EBB is an edge-labeling search algorithm, not a variable-labeling algorithm.

The EBB search is better for sequencing and grouping applications.

An outline of the algorithm is

1. Build set of initial links from initial solution
2. Build the initial node from initial solution and call it the parent node
3. Place the parent node on the best node stack
4. Choose the best links of the parent based on topology and merit (a maximum of beamWidth) and push them on to the best links stack of the parent
5. If there are more links on the stack of the parent, pop the next best link from the stack, otherwise attempt add the parent to the non-dominated set of best nodes, pop the next node off the node stack as the new parent and goto step 4
6. Create a new node, the child, by cloning the parent, and committing best link
7. If the parent has more links on the best links stack, put the parent on the node stack
8. Make the child the new parent and go to step 4

This algorithm is currently a trade secret!!!

Scope of the DHCR Scheduling Prototype

The DHCR scheduling prototype does cover

The DHCR scheduling prototype does not cover

• inventory application
• pacing
• multiple hot strip mills
• mulitple continuous casters
• dual strand casters with different widths on strands

Using EBB Search for DHCR Scheduling

Form a matrix of cast grade and round type and sort the current and past due orders into the cells:

Note that some orders can be rolled in more than one round type.

The table is visited by rows in order of increasing row weight.

The cells within a row are visited in order of increasing cell weight.

Build segments from orders

• For a particular cast grade and round type (within a particular cell) use EBB search to form set of simple segments that do not violate width and gauge constraints, using spread and squeeze to make longer segments. Whereas several solutions are generated we choose one.
• Pull in future due orders to make longer segments.

Build heats from segments

• Split segments into heat sequences with each heat as close to the maximum heat size as possible.
• The minimum heat size is 180 tons, so if a heat is just under the weight, try to cast a stock slab.
• If heat sequence violates 40x3 constraints, split into separate heat sequences.

Build rounds from heat sequences

• For a particular round type (a row), concatenate heat sequences so that width, gauge, and 40x3 constraints are not violated.
• Try to minimize grade changes.
• Use spread and squeeze to make longer rounds.

Build round sequences from rounds

• From the set of rounds, make sequences of rounds so that width, gauge, and 40x3 constraints are not violated.

Build caster strings from round sequences

• Determine tundish and caster string boundaries from the round sequences.
• Use information about caster and HSM throughput to assign durations to heats, tundishes, and rounds.
• Assign a merit to each round sequence.

Build schedules from round sequences

• Use the monte carlo method to include scheduled maintenance periods and the round sequences so that the maintenance is in the right place and the overall merit of the solution is maximized.

All the things like ``try to do this'' are implemented via heuristics in canLink and doLink.

Spread and squeeze is a technique whereby we can cast a slab slightly wider or narrower than would be required by the specified width and gauge, assuming that the difference will be made up by either spreading or squeezing in the HSM.

This is a random procedure, analogous to putting all of the round sequences in a hat, and choosing them at random to build the HSM schedule.

The round sequences that we choose have to fit around the fixed maintenance schedule.

We do this repeatedly, throwing out the bad solutions and keeping the good solutions.

This algorithm is currently a trade secret!!!

Future Work

• cooperative scheduling
• experiments with various topology heuristics
• mixed charging
• multiple casters
• parallel implementation
• variable rate continuous casters
• performance enhancements

The Traveling Salesperson Problem

We are given a cost matrix m_i,j giving cost of sequencing e_j after e_i. All values m_i,j are finite

If m_i,j = m_j,i this is called a symmetric TSP, otherwise it is called asymmetric

The objective is find the lowest cost tour.

A reference on the TSP: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization by E. Lawler, J. Lenstra, A. Rinnooy, and D. Shmoys. (John Wiley and Sons, 1985).