Back
Texte intégral
Doctoral thesis

Approximability of precedence constrained and robust scheduling problems

    17.03.2010

107 p

Thèse de doctorat: Università della Svizzera italiana, 2010

Combinatorial optimization
Approximation algorithms
Single machine scheduling
Dimension theory
Robust optimization
English We study the approximability of scheduling problems in different contexts. We first give a short introduction to the field of scheduling theory and present a simple single machine scheduling problem that will form the base for all variants considered in the remainder of this thesis. We point out that this scheduling problem, though long known to be efficiently solvable in its original form, becomes very interesting when additional restrictions are imposed. The restrictions in the focus of this thesis are precedence constraints among the jobs that need to be fulfilled by any feasible solution, or incomplete knowledge about the instance at hand. We first study the precedence constraint version of the above mentioned single machine scheduling problem. This problem was first studied in the seventies, and still poses perplexing questions to researchers, concerning its approximability. Throughout the years several 2-approximation algorithms have been developed for it, with some special cases of precedence constraints allowing for better than 2 approximations. It was recently shown that this scheduling problem is strongly related to the Vertex Cover problem of an appropriately defined graph. We establish a connection between this graph and a well-known graph in Dimension Theory of partial orders. We also extend a technique developed by Dorit Hochbaum that yields "good" approximation algorithms for the Independent Set problem in graphs to the case that the so-called fractional chromatic number of the graph is bounded. Using the connections to dimension theory, we devise an algorithmic framework that unifies and often improves on the best known approximation algorithms for all previously considered special cases of partial orders. Besides its success in devising approximation algorithms for special cases of precedence constraints, the above sketched connection is also interesting in its own right. As an example, the polynomial solvability of 2-dimensional precedence constraints can be explained by the fact that the resulting graph becomes bipartite and vertex cover is known to be polynomially solvable for bipartite graphs. We then study the above scheduling problems in the presence of uncertainty. We show that this problem cannot be approximated within a logarithmic factor whenever the number of different scenarios, i.e. different configurations of the numerical parameters is unbounded. This result contrasts the difficulty in proving inapproximability results for the classical, non-robust problem and hints at the increase in complexity caused by the uncertain environment. We find it therefore surprising that we were able to develop a polynomial time 2-approximation algorithm for the case when only one of the two parameters is affected by uncertainty. The fact that our result holds in the presence of precedence constraints implies that it cannot be improved without improving upon the 2-approximation algorithm for the classical precedence constrained scheduling problem, a long standing open problem in scheduling theory. We further prove inapproximability results for the unweighted case and give a polynomial time algorithm for the case when both the number of scenarios and processing times / weights are bounded by some constant.
Language
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1318287
Statistics
Document views: 76 File downloads:
  • 2010INFO003.pdf: 42