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

Franco Basso, Mauricio Varas

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)136-145
Number of pages10
JournalComputers and Industrial Engineering
Volume105
DOIs
StatePublished - 1 Mar 2017
Externally publishedYes

Keywords

  • Greedy algorithm
  • MIP
  • Scheduling
  • Wine industry

Fingerprint

Dive into the research topics of 'A MIP formulation and a heuristic solution approach for the bottling scheduling problem in the wine industry'. Together they form a unique fingerprint.

Cite this