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

Wednesday, January 19, 2022, 10:30am

Location: Online session

Speaker: Mariia Anapolska

 

Abstract: 

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.