Minimizing makespan on identical parallel machines with one preemption and batch completion constraints.
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
We consider the parallel machine scheduling problem without preemption
adding a batch completion constraint that forces to process a certain percent age h% of each batch during a period of time. The objective is to minimize the
total cost that is compounded by a makespan cost and by the sequence dependent
setup cost of the schedule. This problem comes from a real logistics situation that
involves the application of a mobile health program.
A MILP model to solve the problem exactly is proposed. As the problem is
NP-Hard, a genetic algorithm structure based on the algorithm proposed in Prins
(2004) is developed, where the main features are a Splitting job heuristic and
the mutation process. From it, we obtain two variants of the algorithm. The
algorithm performance is compared with the MILP model and with an adapted
version of another algorithm from the literature. The efficiency of the proposed
algorithms is validated by the quality of the results, based on the GAP of them
mainly.
Description
Tesis presentada para optar al grado de Magíster en Ingeniería Industrial.
Keywords
Programación Lineal, Algoritmos Genéticos, Programación Heurística