Slot-Based ContinuousTime Formulations for Scheduling Multiple Parallel Machines

In this paper, a continuoustime modeling method based on timeslots is applied to the scheduling of uniform parallel machines in order to obtain optimal solutions of this problem. Based on 3-index and 2-index assignment variables and different positions of empty timeslots on time axes, a series of continuoustime formulations are presented. To improve the efficiency further, a heuristic algorithm is proposed to reduce the number of timeslots. Finally, both the superiority and disadvantage of all the formulations presented in this paper are analyzed by some experiments. The experiment results show that 3-index models are faster than 2-index ones, and the arbitrary placing of the empty timeslots on time axes can speed up the solving process of models. Moreover, the proposed heuristic algorithm can improve the solving efficiency of models to some extent.