No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines

A problem of scheduling n unit-time jobs with a small number of distinct release dates and deadlines, on identical parallel machines, to minimize the number of active machines is studied. The feature that makes this problem challenging is that no machine can stand idle between its start and completion times. A number of properties of this problem is established, and heuristic and optimal algorithms based on these properties are designed. They include optimal algorithms with running times O ( k n k ) and O ( k n 2 3 n ) for the general case, where k is the number of distinct release dates and deadlines, optimal O ( n log n ) algorithms for the cases of a common release date or a common deadline, and an optimal O ( k n 2 ) algorithm for the case of agreeable release dates and deadlines. Algorithms to find lower and upper bounds on the optimal (minimal) number of active machines are developed, and an integer linear programming (ILP) formulation with O ( k ) variables and O ( k 2 ) constraints is provided. Computer experiments demonstrated that the ILP problem is solved by CPLEX to optimality within a few hours for n ≤ 400 and k ≤ 50 , and that the quality of the lower and upper bounds is sufficiently good.