×

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.

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