Everyone is welcome to attend the N&O lecture of Marten Maack with the title 'New PTAS Results for Machine Scheduling'
Abstract: In the classical problem of makespan minimization on identical parallel machines (or machine scheduling for short), a set of jobs has to be assigned to a set of machines. Each job has a processing time and the goal is to minimize the maximum machine load.
It is well known that this problem is NP-hard, but admits a polynomial time approximation scheme (PTAS).
For many natural variants of the problem, however, the approximability status is less clear, and we present new results in this context:
(1) In the restricted assignment variant of the problem, each job maybe processed only by a subset of the machines.
In general this problem does not allow an approximation with rate better than 1.5 (unless P=NP), but various special cases admitting a PTAS have been studied. We introduce a graph based framework for the problem, and design approximation schemes for instances with bounded structural parameters like tree- and clique-width. Thereby, we greatly generalize and unify many of the known PTAS results.
(2) Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems. For instance, they can be used to obtain a PTAS for machine scheduling. Herein a configuration describes a possible placement on one of the target machines, and the IP is used to chose suitable configurations covering the jobs. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework of n-fold integer programming and therefore be solved efficiently.
As an application, we consider variants of machine scheduling with setup times. For instance, we investigate the case that jobs can be split and scheduled on multiple machines. However, before a part of a job can be processed an uninterrupted setup depending on the job has to be paid.
For both of the variants that jobs can be executed in parallel or not, we obtain PTAS results. Previously, only constant factor approximations of 5/3 and 4/3 + ε respectively were known.
