A MIP formulation and a heuristic solution approach for the bottling scheduling problem in the wine industry

- The bottling problem in the wine industry is identified and formulated as a MIP.
- Due to the high computational times of the MIP approach we provide a greedy heuristic.
- For real size industrial instances our heuristic finds solutions in seconds.
- This technique is a promising alternative for experience based scheduling methods.

In this work, we address the bottling scheduling problem that arises in the wine industry when the packing requests from clients need to be allocated to the production lines. This problem also appears in a large variety of industries, but especially in packaged food companies. Based on the operations of a large Chilean winery we worked with, we developed a MIP model that exhibits industry-specific features such as different types of wine resources and oenological process constraints. This model can be reduced to an n job, m parallel machine scheduling problem, which is known to be NP-hard, so we developed a greedy heuristic algorithm in order to find a feasible bottling schedule in a reduced computing time. We show that the proposed solution approach is a very promising alternative to efficient MIP solvers like CPLEX. Particularly, the greedy heuristic is able to schedule all the jobs in 98% of the test instances and the computational times are very reasonable even for large industrial cases.