M. Schilde, K. Schneeberger, K. F. Doerner
We present a solution approach based on variable neighborhood search (VNS) for a real-world inspired rich production planning problem for dairy products. Our method can be used by practitioners to perform the detailed planning for daily production as well as to determine the consequences of possible future developments (e.g., increasing demand for existing products, introduction of new products, or installing additional equipment). Especially the latter is a task that currently is often based on rough estimates and gut instincts. Our approach covers the three main problem components (lot-sizing, sequencing, and scheduling) and all aggregate levels simultaneously and thus provides practically feasible solutions.
We study the multi-level production of several products on a set of heterogeneous aggregates. The process covers seven production levels: mixers, mixing tanks, heaters, fermentation tanks, coolers, filling tanks, and filling machines. Product can remain inside each of the tanks for a limited amount of time if needed. Some products do not require to be processed on every aggregate level and can thus skip one or more of them. The aggregates are connected via product pipes that are used for product transfers between them. Each pipe can be connected to several aggregates at both ends, but during a transfer a pipe is blocked for all other aggregates. After usage, pipes and aggregates need to be cleaned, which causes a certain amount of product loss. A cleaning in place (CIP) pipe and a sterilization in place (SIP) pipe are attached to each aggregate. Each CIP/SIP-pipe can also be connected to more than one aggregate, but only one of these aggregates can be serviced (cleaned or sterilized) at a time. Setup, cleaning, and sterilization requirements are sequence-dependent. Furthermore, the time between two cleaning procedures is limited for hygiene reasons. There are product-dependent limits on the time between finishing fermentation and starting to cool the product, and on the maximum time any product may spend inside a tank. The processing speed for each product varies by aggregate and each tank has a minimum and a maximum capacity.
Our solution approach consists of three parts: a lot-sizing and aggregate assignment algorithm, a scheduling algorithm, and a VNS based method for further optimization. The lot-sizing algorithm groups the final products by components (as several products may require the components) and determines the lot-sizes for all aggregate levels. Then, these lots are assigned to the respective aggregates based on a load balancing constraint. The scheduling algorithm also performs a bottom-up planning, starting at the filling machines. Within each group, the products are sorted using a 3-opt procedure to minimize the setup and CIP/SIP times. Then, the groups are sequenced to minimize setup and CIP/SIP times between groups. This sequence is then locally optimized using 3-opt to obtain a schedule that minimizes the makespan on all aggregates. Finally, the production lots for the remaining aggregate levels, transfer pipes, and CIP/SIP pipes are iteratively scheduled. The VNS then perturbs the found solution by changing aggregate assignments and re-optimizing the schedule locally. The used neighborhood operators move one or more lots between compatible aggregates to resolve resource conflicts.
The method obtains reasonable results for real-world test instances with 100 final products and 40 different aggregates.
Keywords: production planning, scheduling, real-world, dairy
Scheduled
W4 Combinatorial Optimization 1
September 30, 2015 5:00 PM
Salón de actos
