Minimizing makespan on identical parallel machines with one preemption and batch completion constraints.

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.