Monaldo Mastrolilli, IDSIA
Abstract. In this talk I consider two classical precedence constrained scheduling problems.
The first part of the seminar is devoted to the single machine scheduling problem to minimize the weighted sum of completion times. I start presenting the solution of a conjecture by Correa & Schulz that implies that the considered scheduling problem is a special case of the minimum weighted vertex cover. It turns out that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in dimension theory of partial orders. Exploiting this relationship allows us to present a framework for obtaining $(2-2/f)$-approximation algorithms provided that the set of precedence constraints has fractional dimension~$f$. This approach yields the best known approximation ratios for all previously considered classes of precedence constraints we are aware of.
The second part of the seminar is devoted to the job shop scheduling problem. Understanding the approximability of the job shop problem is considered one of the most prominent open problems in scheduling theory. Even though the best approximation algorithms have worse than logarithmic performance guarantee, the only known inapproximability result says that it is NP-hard to approximate acyclic job shops within a factor less than~$5/4$. We solve this open problem by presenting almost tight inapproximability results for acyclic job shops and for the generalized version of flow shop.