Project "Algorithms for Complex Scheduling Problems" within DFG Priority Programme 1307 "Algorithm Engineering" |
Integrated Sequencing and Scheduling
In production planning, it is an everyday task to find low-cost processing orders for given sets of goods. The cost of these orders, or sequences, often highly depends on scheduling decisions taken for a sequence; e.g. the scheduling of setup work. Most of such problems are characterized by complex side constraints and contain NP-hard special cases of the asymmetric Traveling Salesman Problem as subproblem. Moreover, even for fixed sequences the scheduling problem is usually not trivial or even NP-hard itself. To satisfy the quality and runtime requirements of practitioners, we aim for efficient heuristics which produce provably good solutions. We investigate the following two-step approach:
- design of scheduling heuristics for fixed-sequences
- genetic algorithm for sequencing using a heuristic from 1. to evaluate sequences
While in the second step, we use a rather standard genetic algorithm, the first step requires elaborate investigations of the problem's structure. Within the proposed framework, we consider two problems, one from steel manufacturing and another from dairy industry.
Coil Coating - Concurrent Setup Scheduling
We consider a problem from steel manufacturing which deals with the production planning of coil coating lines. As is typical for paint jobs, the coil coating process may be subject to long setup times, mainly for the cleaning of equipment, and thus very high setup cost. In order to reduce this cost, so-called shuttle coaters have been introduced. They possess two separate tanks which allow to hold two different coatings at the same time. In our application, four coaters apply layers of coating one after the other, three of them being shuttle coaters. The advantage of shuttle coaters is twofold: The shuttle can be used to switch between two different coatings on the same coater at (essentially) no setup cost; or alternatively, the unused tank can be set up already while coating is performed from the other tank in the meantime.
| ||
Coils of different widths as they are processed in the coating line (from left to right), with and without shuttle coater. Setup work (such as color or roller changes) has to be performed whenever a coil has to be coated with another color or is wider than its predecessor on that tank. |
Given a set of coils, a production plan for the coil coating process contains the following components:
- a sequence of the coils, i.e. their production order,
- a concurrent setup schedule, deciding for each shuttle coater on which tank to run a coil, and assigning setup work to the only work resource concurrently to production or during non-productive time.
Depending on the sequence and the schedule, additional scrap coils in between the original coils may be required, increasing the makespan, which we aim to minimize.
Tank Assignment Model.
Given a sequence of coils, the concurrent setup scheduling problem can be modeled as a Maximum Weight Independent Set (MWIS) Problem in a special class of 2-union graphs. For the relation to the actual problem, we refer to the website of the cooperation with PSI Business Technology and Salzgitter Flachstahl GmbH, or to [P6]. In 2-union graphs, vertices are 2-dimensional rectangles which are adjacent if they intersect in the projection of at least one dimension.
The MWIS problem is APX-hard for general 2-union graphs[1]. We show that it remains strongly NP-hard for the special class of two union graphs arising from concurrent setup scheduling. Still, will describe a dynamic programming approach with runtime polynomial in the number of coaters. Clearly, his algorithm is far too slow for use in practice. However, it yields a good basis for the design of efficient heuristics for the concurrent setup problem. In our heuristic approach, one dimension of the vertices is partly ignored in order to deal only with classical interval graphs for which MWIS can be computed efficiently.
Algorithm and Evaluation.
Because of the enormous complexity of the coil coating planning, an optimal solution is currently out of reach. This is why intelligent heuristics are our design of choice: We use a classic genetic algorithm for generating sequences, exploiting the special cost structure for choosing the initial population. We repeatedly solve the concurrent setup scheduling problem for the evaluation of sequences by a the fast heuristic stated above. As a final result, our algorithm produces high quality, fully detailed production plans for the entire coil coating problem.
In order to assess the quality of our heuristic solutions, we have devised a mixed integer program (MIP) formulation of a special combinatorial relaxation of the problem. See again the website of our industrial cooperation for further details and computational results.
Filling of Dairy Products - Multi Batch Scheduling
We consider the final step in dairy industry, the filling of products like yoghurt, cream, etc. into cups. A production plan for a filling line comprises a sequence of the products to be filled, and a corresponding schedule: One component of this schedule are classic setup tasks in between the products, uniquely determined by consecutive products. Additionally, setup work or non-productive time necessitates from a set of technical restrictions. Each of these restrictions corresponds to a scheduling subproblem of the following type:
Given: | Fixed sequence of tasks (normal products and setups), |
a task characteristic C (e.g. a task being a setup or a certain product), | |
a weight of each C-task (e.g. the task's duration or volume), | |
non-negative cost after any group of consecutive tasks, and | |
a maximum total weight W of the C-tasks in each group. | |
Task: | Partition the tasks into disjoint groups of size at most W to minimize the total cost. |
However, the cost after a C-group does not only depend on the group itself, but also on groups chosen with respect to other characteristics. Consequently, the subproblems for the different characteristics cannot be considered separately when aiming for a minimum total non-productive time.
For a more practical background, we refer to the problem description on the website of the cooperation with Sachsenmilch AG.
Shortest Path Model.
Considering all task characteristics together, the scheduling problem can be solved via dynamic programming. Similar to the coil coating problem, this approach is far to slow to be integrated in a genetic algorithm for sequencing. Hence, to construct efficient heuristics, we investigate the scheduling problem for only one characteristic. In this case, the problem reduces to a shortest path problem. The basic idea is given in the following figure.
For some of the subproblems, the characteristics even allow linear time algorithms.
Algorithm and Evaluation.
Following our general approach, we use a genetic algorithm for sequencing with an integrated scheduling heuristic. Based on the shortest path model, the heuristic satisfies the technical side constraints separately, one after the other, in an intelligent order. As a final result, our algorithm produces high quality, fully detailed production plans for the filling line. Currently, the quality of our solutions is assessed by comparison with the Traveling Salesman lower bound; i.e., the cost of an optimal solution to the simplified problem considering setup work but ignoring all other side constraints.
Benchmark data and an interface between sequencing and scheduling are available in our download section.
Publication.
[P1] |
Torsten Gellert, Wiebke Höhn,
and Rolf H. Möhring. Sequencing and Scheduling for Filling Lines in Dairy Production. Optimization Letters (Special Issue of SEA 2011), to appear. |
[P6] |
Wiebke Höhn, Felix G. König,
Marco E. Lübbecke
and Rolf H. Möhring. Integrated Sequencing and Scheduling in Coil Coating. Management Science 57(4), pp. 647-666, 2011. (Available as Tech-Report 001-2009) |
Reference.
[1] |
R. Bar-Yehuda, M.M. Hallorsson, J. Naor, H. Shachnai, and I. Shapira Scheduling Split Intervals, In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '02), 32-741, 2002 |