Sequencing and Scheduling for Filling Lines in Dairy Production

Project director: Prof. Dr. Rolf H. Möhring
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 24594
e-mail: rolf.moehring[at]math.tu-berlin.de
Researchers: Torsten Gellert
Wiebke Höhn
emails: {gellert, hoehn}[at]math.tu-berlin.de
for address, see above
Cooperation partner:
Support of
theorectical
work:
DFG DFG within Priority Prog. 1307 "Algorithm Engineering"

Problem Description

As final step in classic dairy industry, products pass through filling lines that fill the yoghurt, cream, etc., into cups. One filling line is used to fill many different products, necessitating setup work in between. Each of these setups depends only on the characteristics of two products filled consecutively. However, due to additional technical restrictions, the flavor of the problem changes from a classic Traveling Salesman Problem to a more complex sequencing problem.

Exemplary for the technical restrictions, we consider regular cleanings. Due to hygiene requirements, filling lines have to be cleaned and sterilized after a certain period of time at the latest. Such a cleaning can either be scheduled by preempting the production, or alternatively, by performing it in between the filling of two products, making the actual setup unnecessary. Hence, when minimizing the total non-productive time, this yields a tradeoff between keeping the total number of regular cleanings small on the one hand, while saving as much setup as possible by replacing setups with cleanings on the other hand.

Similar tradeoff scenarios also result from other restrictions. Due to their interdependency, the scheduling for the different conditions cannot be considered separately when aiming for an optimal solution. Moreover, a filling order of products can only be evaluated in a reasonable way, if the scheduling decisions are taken.

Scheduling Model

Given a filling sequence of products, we can solve the combined scheduling problem for all restrictions via dynamic programming. However, this approach is far to slow for usage in practice. Especially, since the scheduling method needs to be called for every evaluation of a sequence.

If focusing only on one of the restrictions, the scheduling problem can be modeled as a shortest path problem, yielding an algorithm with runtime quadratic in the number of products. Some special cases even allow linear time algorithms.

Shortest path modeling for scheduling of regular cleanings. The distance between two regular cleanings must not be larger than dclean. In the Gantt Chart, products are shown in blue while setups are gray.

Algorithm

Due to the complexity of the problem, an optimal solution seems out of reach within reasonable runtime. This is why an intelligent heuristic is our design of choice: We propose a classical genetic algorithm for generating sequences, using a scheduling heuristic for the evaluation of sequences. 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.


Publication

[1] 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.