Background
Ever wondered how your pre-painted steel roofing and cladding material is made? Coiled strips of tempered steel of the required width and thickness are delivered to a colour coating mill for painting. The coil is unwound on the paintline and rollers paint each side of the strip with two layers of paint, first a primer and then a finisher. The steel strip is then rewound before being sent off to another facility to be shaped and cut into lengths in a process called rollforming.
Advitech was engaged by BlueScope to develop a paintline scheduling tool that optimises the sequence orders are processed on the paintline to minimise the total time it takes to fulfil all the orders. The tool has been integrated into BlueScope’s existing paintline schedule optimisation framework and is now used in production.
The Problem
The paintline is presented with a schedule of orders that must be processed. Each order in a schedule is specified by a quantity of coiled steel of a fixed width and thickness (gauge) to be painted on each side with two layers of paint, first a primer and then a finisher.
To provide greater flexibility in the painting process the coils that make up an order may be partitioned into sub-orders or jobs. Jobs need not be processed consecutively, a job from one order can be processed between jobs from other orders, however, once the processing of a job starts it cannot be interrupted.
Changing from a job of one order to a job of another order can require a line configuration change called a transition. Transitions can result from the need to change the width, the gauge, or a paint. The period of time during which painting is paused during a transition from one job to another is called the transition time.
A distinguishing feature of the BlueScope paintline scheduling problem that makes it particularly challenging is that transition times are not just dependent upon the job being transitioned from, and the job being transitioned to, but also the previous jobs that have been processed.
The total time to fulfil all the jobs in the schedule is known as the makespan. Reducing the makespan of a schedule provides the greatest opportunity to improve the productivity of the paintline. Thus, the problem is to determine a sequence of the jobs that minimises the makespan of the schedule subject to the resulting schedule satisfying certain requirements.
Since the time to paint a job is determined by the job quantity, minimising the makespan is equivalent to minimising the sum of the transition times between jobs. The requirements that the resulting schedule may need to satisfy include the relative order of select jobs, certain jobs requiring the use of a specific head of a dual-head coater, limits on the length of time successive jobs with the same width or requiring the same paint can run, and the paintline being shut down for maintenance.
The Challenge
Finding high quality solutions to such scheduling problems is non-trivial for many reasons, not least of all the rapid growth of the number of possible schedules as the number of jobs in a schedule increases.
This phenomenon is known as a combinatorial explosion, and it rules out the possibility of checking all schedules one by one. If a schedule has n jobs then there are n! (pronounced “n factorial”) ways in which those n jobs can be sequenced: there are n choices for the first job, n-1 choices for the second job, etc.
Even for relatively small values of n, the number n! grows very rapidly. For example, 5! = 5 x 4 x 3 x 2 x 1 = 120 and 10! = 3 628 800. The number 65! is already larger than the number of elementary particles in the visible universe which is estimated to be at most 1085—that’s a 1 followed by 85 zeros. Fortunately, there exist advanced analytical techniques that allow the set of possible schedules to be reduced and searched efficiently.
The Solution
Advitech drew upon its expertise in algorithmic intelligence and decision intelligence to develop a paintline scheduling tool that combines state-of-the-art techniques from mathematical graph theory and mathematical optimisation to effectively solve BlueScope’s paintline scheduling problem. The tool is implemented in Python and integrates into BlueScope’s paintline schedule optimisation framework. The tool is now used in production.
Benchmark tests on a suite of schedules provided by BlueScope demonstrate that the optimised schedules found by the Advitech scheduling tool substantially outperforms BlueScope’s previous scheduling tools in terms of both the transition time of an optimised schedule as well as the time taken to find this schedule. On a particularly difficult schedule, the Advitech scheduling tool computed an alternate schedule with 43% less transition time in 10% of the time taken by the previous tools.
Benefit for the client
The savings in transition time dramatically improve the productivity of the paintline and the financial benefit is both significant and immediate.
In the words of Lachlan O’Neil, BlueScope Steel’s Program Lead – Scheduling & Optimisation, Strategy & Transformation:
“Thanks, Advitech for your high-quality work. You were easy, professional, and motivational to work with. You were highly flexible to our requests, and highly attentive to the details of the problem. As a result, you’ve provided a tool which is performing much better than the previous tool that we had in use.”
