Three parallel machines scheduling with minimizing the maximum inter-completion time

This work studies the processing schedules of parallel machines with strong response abilities to unexpected and urgent jobs. We consider the job scheduling on three parallel machines, aiming to minimize the maximum difference between the completion times of any two consecutively completed jobs, in other words, to minimize the maximum inter-completion time. We first give two upper bounds of the workload of machines which is the sufficient condition of feasible solutions. Based on the sufficient condition, we first give several basic properties of the optimal solution. Secondly, we further prove a lower bound of the objective value and design an O(n2) time algorithm to calculate the lower bound. Finally, we develop an improved algorithm based on the RMST algorithm to solve the considered problem, in which the RMST algorithm considers the case that one may reserve as much spare time as possible on one of the machines. Through computational comparisons between the improved algorithm and RMST algorithm together with the genetic algorithm and the lower bound of objective value, it is shown that our algorithm outperforms the other two algorithms. Numerical experiments verify the effectiveness of the improved algorithm.