zbMATH — the first resource for mathematics

Exact and approximation algorithms for the tactical fixed interval scheduling problem. (English) Zbl 0887.90089
Summary: 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.

90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI