Published Online:https://doi.org/10.1287/opre.35.6.849

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.

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.