CONTRIBUTIONS TOWARDS SOLVING THE PARALLEL MACHINE SCHEDULING PROBLEM WITH NON-AVAILABILITY PERIODS

Abstract

An abundance of research exists studying parallel machine scheduling, but only a portion of this research has focused on the case with non-availability periods and job resumability factors. Research considering this case has mostly focused on limited cases such as a small, fixed number of machines or fixed number of non-availability periods. In this research, we improve the runtime of the model by Beaton et al. (2016) who proposed a mixed-integer linear programming (MILP) model allowing an arbitrary number of machines, non-availability periods, and resumability factor for small instances of the makespan minimization case. We propose a new MILP model for the Total Weighted Completion Time (TWC) case and two constraint programming (CP) models for both the makespan and TWC cases and find that the CP models outperform the MILP for the TWC case. We confirm that the well-known Weighted Shortest Processing Time heuristic works well for large TWC instances.