Approximation Algorithms for Fixed Job Schedule Problems

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, 1992, vol. 40, issue 1-supplement-1, S96-S108

Abstract: We consider two generalizations of the fixed job schedule problem, obtained by imposing a bound on the spread-time or on the working time of each processor. These NP-hard problems, studied by the authors in previous works, can arise in bus driver scheduling. We introduce several polynomial-time approximation algorithms, give efficient implementations for them, and analyze their complexity and worst case performance. The average behavior is also investigated through extensive computational experiments.

Keywords: production/scheduling: fixed job scheduling; programming; algorithms: approximation algorithms; worst case analysis (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S96 (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:40:y:1992:i:1-supplement-1:p:s96-s108

Access Statistics for this article

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