Production scheduling across multi-machine packaging lines for the prescheduling level

Scheduling packaging lines in the process industry is a well known hard problem. The problem becomes even more complicated when each line consists of several machines and an order has to be manufactured on different lines. In this paper we consider the case where a number of orders has to switch from one line to another. This means that an order-run is sometimes manufactured first on the first part of a line and then has to switch to the second part of another packaging line. In this situation the second part of the first line and the first part of the second line cannot be used simultaneously for another run. This situation is studied for the case of the tobacco company Royal Kabat BV. In order to solve the complicated planning problem, the process is partitioned into a Prescheduling Level (PSL) and a Scheduling Level (SL). At the PSL an aggregated plan for a number of successive weeks is made that takes care of the purchasing of packaging materials and the balancing of the capacities. The PSL plan for the current week is the input for the SL at which the actual packaging schedule for that week is made, including the allocation of orders to lines. In this paper we concentrate on the PSL, and our main purpose is to describe the complicated model building process. The model is solved by means of an improvement heuristic on the solution of an LP-relaxation of the model. The computational results show that our partitioning of the problem into a PSL and an SL yields a practically solvable mathematical model; its solutions (i.e. PL plans) are usable for the SL planning and result in practically useful schedules