EXACT AND APPROXIMATION ALGORITHMS FOR THE TACTICAL FIXED-INTERVAL SCHEDULING PROBLEM

The Tactical Fixed Interval Scheduling Problem (TFISP) is the problem of determining the minimum number of parallel nonidentical machines, s uch 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 res trictions 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, a nd (3) preemption is not allowed. In this paper we discuss the occurre nce of TFISP in practice, we analyze the computational complexity of T FISP, and we present exact and approximation algorithms for solving TF ISP. The paper concludes with a computational study.