Complexity results for scheduling problems

http://www.informatik.uni-osnabrueck.de/knust/class/

previous address:

http://www.mathematik.uni-osnabrueck.de/research/OR/class/

Idea: Peter Brucker
Realization: Sigrid Knust

Introduction

• maximal polynomially solvable: the hardest problems which are polynomially solvable, i.e. problems which are known to be polynomially solvable, but any harder cases are not known to be polynomially solvable,
• maximal pseudopolynomially solvable: the hardest problems which are known to be pseudopolynomially (but not polynomially) solvable,
• minimal NP-hard: the easiest problems which are NP-hard, i.e. problems which are known to be NP-hard, but any easier cases are not known to be NP-hard,
• minimal open: problems for which the complexity status is not known, but all easier cases are known to be polynomially solvable,
• maximal open: problems for which the complexity status is not known, but all harder cases are known to be NP-hard.

The input for MSPCLASS are problems which are known to be polynomially solvable or NP-hard and elementary reductions for scheduling problems.

The objective of these pages is to

• update complexity results
• extend the classification to new classes of scheduling problems.

For this purpose we developed a new computer program CLASS (Plaggenborg (1994)) and applied it to several classes of scheduling problems which are listed below. The used reduction graphs and obtained results can be found on the following pages. A * before an NP-hard problem denotes that the problem is NP-hard in the strong sense. Note that an arc A --> B in a reduction graph means a polynomial reduction from A to B only if the size of B is polynomially bounded by the size of A.
For notation we refer to Graham et al. (1979) and to Brucker (1998). In this book also most of the polynomial time algorithms can be found. All data are assumed to be integer.


We want to keep these pages as up to date as possible. If you have further results or any suggestions please contact us. Unpublished results should be sent to us as Latex or postscript files or as hardcopy.

Supported by the Deutsche Forschungsgemeinschaft, Project "Komplexe Maschinen-Schedulingprobleme''.

References:

• P. Brucker (1998): Scheduling algorithms, 2nd edition, Springer, Heidelberg.
• R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan (1979): Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math. 4, 287-326.
• B.J. Lageweg, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan (1981): Computer aided complexity classification of deterministic scheduling problems, Report BM 138, Centre for Mathematics and Computer Science.
• B.J. Lageweg, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan (1982): Computer-aided complexity classification of combinatorial problems, Comm. ACM 25, 817-822.
• S. Plaggenborg (1994): Ein Algorithmus zur komplexitaetsmaessigen Klassifikation von Schedulingproblemen, Diplomarbeit Fachbereich Mathematik/Informatik, Universitaet Osnabrueck.

• Elementary reductions for the objective functions
• Complexity results for all classes [pdf]
• All references [pdf]
• Searching for problems (Webpage of Christoph Dürr, Paris)