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

Lageweg et al. (1981), (1982) developed a computer program MSPCLASS for an automatic classification of scheduling problems. Based on the -classification scheme of Graham et al. (1979) it calculates problems which are


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

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:



 
Reduction Graph


Complexity results

Single machine problems [red. graph] [html] [pdf]
Parallel machine problems without preemption [red. graph] [html] [pdf]
Parallel machine problems with preemption [red. graph] [html] [pdf]
Open-shop problems without preemption [red. graph] [html] [pdf]
Open-shop problems with preemption [red. graph] [html] [pdf]
Flow-shop problems without preemption [red. graph] [html] [pdf]
Flow-shop problems with preemption [red. graph] [html] [pdf]
Job-shop problems without preemption [red. graph] [html] [pdf]
Job-shop problems with preemption [red. graph] [html] [pdf]
Open-shop problems with nowait [red. graph] [html] [pdf]
Flow-shop problems with nowait [red. graph] [html] [pdf]
Job-shop problems with nowait [red. graph] [html] [pdf]
Multiprocessor task problems with dedicated processors [red. graph] [html] [pdf]
Multiprocessor task problems with dedicated processors and preemption [red. graph] [html] [pdf]
Multiprocessor task problems with parallel processors [red. graph] [html] [pdf]
Multiprocessor task problems with parallel processors and preemption [red. graph] [html] [pdf]
Shop problems with multiprocessor tasks [red. graph] [html] [pdf]
Multipurpose machine problems [red. graph] [html] [pdf]
Shop problems with multipurpose machines [red. graph] [html] [pdf]
Serial batching problems [red. graph] [html] [pdf]
Parallel batching problems [red. graph] [html] [pdf]
Single machine problems with non-negative time-lags [red. graph] [html] [pdf]
Flow-shop problems with transportation delays [red. graph] [html] [pdf]
Open-shop problems with transportation delays [red. graph] [html] [pdf]
Flow-shop problems with transportation times and a single robot [red. graph] [html] [pdf]
Parallel machine problems with a single server [red. graph] [html] [pdf]
Flow-shop problems with a single server [red. graph] [html] [pdf]

Last update: 29.06.2009 (SK)