zbMATH — the first resource for mathematics

The fixed job schedule problem with spread-time constraints. (English) Zbl 0638.90055
Summary: We consider a generalization of the fixed job schedule problem in which each processor is available only for a prefixed time interval from the release time of the earliest task assigned to it. The problem can arise in bus driver scheduling. We show that the problem is NP-hard, and introduce polynomial procedures to determine lower bounds, dominance criteria and reductions. We also develop a branch-and-bound algorithm for obtaining the optimal solution of the problem and analyze the algorithm’s average performance in a series of computational experiments. Finally, we investigate the preemptive case and other polynomial special cases.

90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI