The Fixed Job Schedule Problem with Spread-Time Constraints

Matteo Fischetti, Silvano Martello and Paolo Toth
Additional contact information
Matteo Fischetti: University of Bologna, Bologna, Italy
Silvano Martello: University of Bologna, Bologna, Italy
Paolo Toth: University of Bologna, Bologna, Italy

Operations Research, 1987, vol. 35, issue 6, 849-858

Abstract: 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.

Keywords: 011 worst-case analysis; 581 fixed job scheduling; 630 branch-and-bound (search for similar items in EconPapers)
Date: 1987
References: Add references at CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.35.6.849 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:35:y:1987:i:6:p:849-858

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().