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

International audienceA problem of scheduling 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(kn^k)$ and $O(kn^23^n)$ for the general case, where 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(kn^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\leq400$ and $k\leq50$, and that the quality of the lower and upper bounds is sufficiently good