In the known Interval Scheduling Problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specific time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We extend ISMA by introducing machine capacities to model parallel processing of multiple jobs per machine: the Multi-thread Interval Scheduling with Machine Availabilities (MISMA). In machine scheduling, maintenance plays a crucial role in guaranteeing an efficient operation. The time slots for maintenance at the end of a processing period are often predetermined by staff schedules before the slots are assigned to specific machines. This motivates a variant of MISMA where the end times of the machines’ availability intervals can be permuted, the Flexible Multithread ISMA (FlexMISMA). In this paper, we determine a tight classification of conditions that are required for obtaining a polynomial time algorithm for both MISMA and FlexMISMA. More specifically, we show that FlexMISMA is at least as hard as MISMA. For FlexMISMA, we present polynomial time algorithms for instances (i) with two machines, and (ii) with constantly many parallel jobs at each point in time which both also solve MISMA; and (iii) with arbitrarily many machines of capacity one each in which case MISMA is known to be NP-hard. However, we prove that increasing the capacity to two renders FlexMISMA also NP-hard for arbitrarily many machines. Furthermore, we complement result (i) by showing that both problems are NP-hard already for instances with three machines as a special case of the Vertex-Disjoint Paths problem.
Article
View Efficient Algorithms for Multi-Threaded Interval Scheduling with Machine Availabilities