Ola Svensson

Precedence Constrained Scheduling: progress on some classical open problems


 Abstract: We consider the approximability of the classical
 precedence-constrained scheduling problem with weighted sum of
 completion times objective and the notorious job and flow
 shop scheduling problems.

 In the first part of the talk, we combine techniques from vertex cover
 and dimension theory of partial orders to obtain the best known
 approximation ratios for all considered classes of precedence
 constraints for the precedence-constrained scheduling problem.

 In the second part, we close a major open problem in scheduling theory
 by providing stronger inapproximability results for job and flow
 shops. We show that it is NP-hard to approximate job shops within any
 constant factor. Moreover, under a stronger assumption, we obtain a
 hardness result that essentially matches the best known approximation
 algorithm for the general version of flow shops, where jobs are not
 required to be processed on each machine. This construction also
 resolves an open question raised by Feige & Scheideler by showing that
 the current approximation algorithm for flow shops is tight with
 respect to the used lower bound on the optimal makespan.