TY - JOUR
T1 - A MIP formulation and a heuristic solution approach for the bottling scheduling problem in the wine industry
AU - Basso, Franco
AU - Varas, Mauricio
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2017/3/1
Y1 - 2017/3/1
N2 - 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.
AB - 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.
KW - Greedy algorithm
KW - MIP
KW - Scheduling
KW - Wine industry
UR - http://www.scopus.com/inward/record.url?scp=85009483736&partnerID=8YFLogxK
U2 - 10.1016/j.cie.2016.12.029
DO - 10.1016/j.cie.2016.12.029
M3 - Article
AN - SCOPUS:85009483736
VL - 105
SP - 136
EP - 145
JO - Computers and Industrial Engineering
JF - Computers and Industrial Engineering
SN - 0360-8352
ER -