A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint

This paper studies a two-machine open shop scheduling problem with an availability constraint, i.e. we assume that a machine is not always available and that the processing of the interrupted job can be resumed when the machine becomes available again. We consider the makespan minimization as criterion. This problem is NP-hard. We develop a pseudo-polynomial time dynamic programming algorithm to solve the problem optimally when the machine is not available at time s>0. Then, we propose a mixed integer linear programming formulation, that allows to solve instances with up to 500 jobs optimally in less than 5 min with CPLEX solver. Finally, we show that any heuristic algorithm has a worst-case error bound of 1.