Combinatorial Optimization & Graph Algorithms group (COGA)Sequencing & Scheduling

# Integrated Sequencing & 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 above 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 tha

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 the corresponding publication. In 2-union graphs, vertices are 2-dimensional rectangles which are adjacent if they intersect in the projection of at least one dimension.

Correspondence of conflicting saving rectangles and adjacent nodes in the 2-union graph.

The MWIS problem is APX-hard for general 2-union graphs as shown by Bar-Yehuda et al. (SODA '02). 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.

### 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.

Tasks with characteristic C are shown in yellow, others in blue. A vertex is placed in between all consecutive C-tasks. A vertex is connected by an arc to all vertices to its right, as long as the C-tasks "below" the arc have weight at most W. The length

### 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.

## Publications

Höhn, Wiebke and König, Felix G. and Lübbecke, Marco E. and Möhring, Rolf H.
Integrated Sequencing and Scheduling in Coil Coating.
Management Science, Vol. 57, pp. 647–666, 2011.
Finalist for the EURO Excellence in Practice Award 2009.  [pdf]

Gellert, Torsten and Höhn, Wiebke and Möhring, Rolf H.
Sequencing and scheduling for filling lines in dairy production.
Optimization Letters, Vol. 5, pp. 491–504, 2011.
Special issue of SEA 2011.