Optimality of Jackson's permutations with respect to limited machine availability

This article deals with the scheduling problem of minimizing the makespan in a two-machine job-shop with given w intervals of machine non-availability. It is known that this problem is binary (unary) NP-hard if there is at least one non-availability interval (if the number of non-availability intervals may be arbitarily large), and all the jobs have the same machine route. We find sufficient conditions when Jackson's pair of permutations remains optimal for the two-machine job-shop problem with w⩾1 non availability intervals. Extensive computational studies show the effectiveness (in the number of problems solved) and efficiently (in computational time) of these conditions for the randomly generated instances with up to 10,000 jobs and w⩾5000 non-availability intervals.