Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem

Leo G. Kroon, Marc Salomon and Luk N. Van Wassenhove
Additional contact information
Leo G. Kroon: Erasmus University, Rotterdam, The Netherlands
Marc Salomon: Tilburg University, Tilburg, The Netherlands
Luk N. Van Wassenhove: INSEAD, Boulevard de Constance, France

Operations Research, 1997, vol. 45, issue 4, 624-638

Abstract: The Tactical Fixed Interval Scheduling Problem (TFISP) is the problem of determining the minimum number of parallel nonidentical machines, such that a feasible schedule exists for a given set of jobs. In TFISP, each job must belong to a specific job class and must be carried out in a prespecified time interval. The problem is complicated by the restrictions that (1) each machine can handle only one job at a time, (2) each machine can handle only jobs from a subset of the job classes, and (3) preemption is not allowed. In this paper we discuss the occurrence of TFISP in practice, we analyze the computational complexity of TFISP, and we present exact and approximation algorithms for solving TFISP. The paper concludes with a computational study.

Keywords: programming; integer; production/scheduling; approximations; heuristics; analysis of algorithms; computational complexity (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.4.624 (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:45:y:1997:i:4:p:624-638

Access Statistics for this article

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