|
|
Moritz Buchem (Maastricht University) - Scheduling with Machine Conflicts Supervisors: Tjark Vredeveld and Tim Oosterwijk Recorded full presentation Abstract We study a scheduling problem in which machine conflicts are taken into account. Machine conflicts arise in various settings, e.g., shared resources for pre- and post-processing of tasks or spatial restrictions. In this context, each job has a blocking time before and after its processing time, i.e., three parameters. Given a set of jobs, a set of machines, and a graph representing machine conflicts, the problem Scheduling with Machine Conflicts (SMC), asks for a conflict-free schedule in which the blocking times of no two jobs intersect on conflicting machines. The goal is to minimize the makespan, i.e. the schedule of the length. We show that, unless P = NP, SMC on m machines does not allow for any constant factor approximation, even in the case of identical jobs and every choice of fixed positive parameters, including the unit case. For special graph classes we provide exact and/or approximation algorithms. Most prominently, we introduce a polynomial time algorithm for bipartite graphs and unit jobs by using structural insights on optimal schedules for conflict graphs of star forests. This is joint work with Linda Kleist and Daniel Schmidt genannt Waldschmidt. |
