Towards an effective column generation technique for solving large batch scheduling problems

MENDEZ CARLOS ALBERTO; DONDO RODOLFO; COCCOLA MARIANA EVANGELINA

Valencia

Conferencia; 29th European Conference on Operational Research; 2018

Universidad Politécnica de Valencia - Inoversidad de Valencia

Column generation (CG) is a decomposition technique widely used toeciently solve a wide range of integer and integer-linear problem involvingset-partitioning constraints such as vehicle-routing problemsand crew-scheduling problems. Although CG became the leading optimizationtechnique for solving many routing problems, just a fewapplications have been focused on short-term scheduling problems inthe literature. Most algorithms were designed to only consider a singlemachine or multiple identical parallel lines and are poorly adaptedto other configurations. Some of them are limited to solve identicalparallel-machine scheduling problems by a CG approach. This paperincreases the challenge by developing a novel MILP-based CG algorithmthat is able to handle with single-stage short-term schedulingproblem with non-identical parallel machines. Each generated columnrepresents a feasible schedule on one machine and each feasible scheduleis generated by solving a single machine sub-problem, which isbased on a continuous time precedence-based MILP formulation. Thebest jobs allocation is chosen by the master problem. In order to generatethe maximum number of feasible and profitable columns per iteration,the solver-options of the branch-and-cut package used for solvingthe slave problem are properly tuned. The iterative CG algorithm wasdeveloped by using the GAMS software and the computational resultsdemonstrate the eciency of this decomposition method.