No-idle Parallel Machine Scheduling of Unit-time Jobs

摘要

We study a problem of scheduling unit-time jobs with given release dates and deadlines on identical parallel machines. No machine can stand idle between its start and completion times. The objective is to minimize the number of machines in use. A number of properties of this problem is established, and heuristic and optimal algorithms based on these properties are developed. They include optimal exponential algorithms for the general case and optimal polynomial algorithms for special cases. Lower and upper bounds are determined and an integer linear programming formulation is provided.