Bi-Weekly Talk: Mariia Anapolska: Multithread interval scheduling with machine availabilities

Mittwoch, 19.01.2022, 10.30 Uhr

Ort: Online Session

Vortragende: Mariia Anapolska



Initially inspired by a problem in hospital management, we introduce an extension of the known Interval Scheduling Problem with Machine Availabilities (ISMA). In ISMA, each machine has a continuous availability interval, and each job has a fixed time interval which has to be scheduled. We extend ISMA by enabling the machines to process multiple jobs in parallel and to swap the end times of their availability periods.

In this talk, after introducing the new problem variant, we will obtain an overview of its complexity. In process, we will discover the relation of FlexMISMA to several classical combinatorial problems and describe polynomially solvable and NP-hard cases depending on the number of machines and their capacity.