Exact and approximation algorithms for the operational fixed interval scheduling problem

The Operational Fixed Interval Scheduling Problem (OFISP) is characterized 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 class. The objective is to find an assignment of jobs to machines with maximal total priority. The problem is complicated by the restrictions that: (i) each machine can handle only one job at a time, (ii) each machine can handle only jobs from a prespecified subset of all possible job classes, and (iii) preemption is not allowed. It follows from the above 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 computational results are shown.