Two parallel identical machines scheduling to minimise the maximum inter-completion time

In many manufacturing and service systems, it is of great importance to generate processing schedules with strong response abilities to unexpected or urgent jobs. In this paper, we investigate the problem of scheduling jobs on two parallel identical machines. The objective is to minimise the maximum difference between any two consecutive completion times of jobs, i.e. to minimise the maximum inter-completion time. The processing of any job cannot be interrupted, and a smaller objective value of the processing schedule implies a faster response to an unexpected job that may arrive at any time point. The problem was introduced by Zheng, Pinedo, Lee, Liu, and Xu [2019. “Towards Robustness of Response Times: Minimising the Maximum Inter-completion Time on Parallel Machines.” International Journal of Production Research 57 (1): 182–199]. In this work, we first give a sufficient condition of feasible solutions with respect to the makespan constraint, and reveal several basic properties of any optimal solution. We then prove a theoretical lower bound of the objective value, and propose a $O(n^2) $O(n2) time algorithm to compute the lower bound. An efficient heuristic algorithm is further constructed to solve the considered problem. Experimental results show that the proposed algorithm outperforms all the three heuristics introduced in Zheng, Pinedo, Lee, Liu, and Xu 2019.