Background
In steel mills, coil products emerge from the steel making, the hot rolling, and the cold rolling processes, in that order. The steel making process produces slabs, the hot rolling process produces hot coils, and the cold rolling process produces cold coils. Optimized scheduling is necessary and required for these steps to operate efficiently, but it is too complicated to create schedules for all of these processes at once. A common approach is to handle each process independently, but the operational efficiency of downstream processes needs to be considered while scheduling upstream processes, and the scheduling results of the upstream processes are required as input to the downstream processes. This involves a chicken and egg problem. The following method is used to resolve this difficulty:
- First, schedule each process starting from downstream moving upstream and set for each coil the process timings that realizes efficient operations for each of its processing steps.
- Next, schedule the upstream processes while considering the process timing, and
- Finally readjust the schedule of the downstream processes again using the upstream schedules as input.
We call such multiple process scheduling end-to-end scheduling.
Fig.1 - end-to-end scheduling
The above figure shows the process flow in the end-to-end scheduling with the horizontal axis as time. In steel mills, a group of coils with the same properties is processed at one time. Such properties include the grades of the steel, the types of galvanizing, the surface treatment types, and so on. The groups of coils, shown as rectangles in the above figure, are called production campaigns. Because the types of production campaigns are different from process to process, the waiting times of the coils at each processing step varies. Therefore, the production campaigns related to each other are planned with longer durations at the downstream processes than at the upstream processes, as shown in the figure.
The End-To-End Scheduling for the Cold Mill Processes
The customers for coil products include customers with strict requirements for due dates, such as car manufacturers. In order to satisfy the requests from such customers, long-term scheduling with low overdue is required. When the steel making processes are being scheduled for a week, most of the downstream processes should be scheduled over a period of about a month, considering the effects of the steel making schedules on the downstream processes.
For the cold mill processes, an efficient ordering of production campaigns needs to be considered at each of the continuous processes where the ends of adjacent coils are welded together to form a single steel sheet. Apart from the continuous processes, there are batch processes that do not involve the campaign ordering problem and that do not affect the operational efficiency of upstream or downstream processes. Therefore, the following four continuous processes among the cold mill process stages are considered in the end-to-end scheduling:
- Cold Mill (CM) -- pickling and rolling
- Continuous Galvanizing Line (CGL) -- hot dip zinc galvanizing and annealing
- Continuous Annealing Line (CAL)
- Electro-Galvanizing Line (EGL)
The end-to-end scheduling for the cold mill processes is called the Finishing Line Scheduling (FLS).
The Characteristics of the FLS Problem
The cold mill processes involves the four continuous processes for which end-to-end scheduling is required. In other words, the scheduling at each process must consider the operational efficiency of upstream and downstream processes, and also the process timing of coils at adjacent processes cannot be reversed in time. (This property is called vertical consistency, which insures the process timing is never reversed.) In continuous processes, some production campaigns require setup and involve setup costs and times. Therefore, campaign transitions minimizing setup costs and times are preferred. The coils assigned to each production campaign need to be sequenced with consideration of the efficiency of the continuous processing and the quality of the products. The amount of input data for a one month scheduling horizon is very large, amounting to 5,000 coils for each process step. The output schedule:
- Needs to consider operational efficiency at adjacent processes and the vertical consistency.
- Needs to consider efficient orderings of production campaigns.
- Needs to consider coil ordering within production campaigns.
- Needs to handle large problem size.
Here are some of the reasons that the coil ordering within a production campaign affects the operational efficiency and the product quality: The width differences of adjacent coils must be within an allowable limit because the coils are welded together and big gaps tend to cause breaks at the welded junctures. Large width gaps also causes excessive trim losses, as shown in the figure below. The smaller the width gaps, the better. The thickness difference of adjacent coils must also be as small as possible. The same preferences are involved at the CAL process as regards temperatures. Also, in continuous processes, the rollers are worn by processing coils. Therefore, processing narrower and wider coils in that order creates scars, called edge marks, to appear on both sides of the wider coils. Therefore, the ordering of coils within campaigns has a large influence on product quality.
Fig.2 - Edge marks and trim loss at continuous processes
The Algorithms
We developed the following algorithms for the end-to-end scheduling for the cold mill processes:
- Clustering
For each process, near-neighbor coils are patched together to make clusters while considering the connectivity between coils. This reduces the problem size and also guarantees connectivity of coils within each production campaign.
- Production campaign creation
Distance is associated for each pair of clusters with respect to the setup costs and times between production campaigns and the clusters are sequenced such that the total distance between clusters is minimized. The time windows are considered for clusters to schedule them in feasible periods of time. Production campaigns are then created for the consecutive clusters with the same campaign types. This type of problem can be regarded as a form of the traveling salesperson problem (TSP), and various algorithmic techniques are known for solving it, such as neighborhood search. We call this particular form the TSP with colors, based on considering the production campaign types of clusters as colors. (When there are multiple production lines for a process, the problem also involves multiple routes.)
Fig.3 - The Traveling Salesperson Problem with Colors
- Coil sequencing within campaigns
Clusters assigned to a campaign are un-clustered into original coils, and distance is associated for each pair of coils with respect to differences of widths, thickness, and so on. The coils are then sequenced so that the total distance between coils is minimized. Because the distance is based on geometry of coils, this problem has properties similar to the Euclidean TSP. We implemented the algorithm with various speed-up techniques, for example, for geometric near-neighbor search.
- Vertical consistency between upstream and downstream processes
After creating production campaigns for each process, the time windows of the coils (clusters) are propagated to upstream and downstream processes. With the time window propagation, the end-to-end scheduling is realized by creating production campaigns for each process one after another.
Fig.4 - Sample result
Benefits of the FLS System
The FLS system allows users to realize Available-To-Promise with high accuracy based on the production schedule over one month. As a result of considering operational efficiency at the upstream and downstream processes, the lead times between processes are shortened and inventory is reduced. Unplanned downtimes due to lack of materials arriving from upstream processes are reduced. Reductions of setup costs and improvements of coil quality are also achieved.