EXACT AND APPROXIMATION ALGORITHMS FOR THE OPERATIONAL FIXED-INTERVALSCHEDULING PROBLEM

The Operational Fixed Interval Scheduling Problem (OFISP) is character ized as the problem of scheduling a number of jobs, each with a fixed starting time, a fixed finishing time, a priority index, and a job cla ss. The objective is to find an assignment of jobs to machines with ma ximal total priority. The problem is complicated by the restrictions t hat: (i) each machine can handle only one job at a time, (ii) each mac hine can handle only jobs from a prespecified subset of all possible j ob classes, and (iii) preemption is not allowed. It follows from the a bove that OFISP has both the character of a job scheduling problem and the character of an assignment problem. In this paper we discuss the occurrence of the problem in practice, and we present newly developed exact and approximation algorithms for solving OFISP. Finally, some co mputational results are shown.