Research AG Kombinatorische Optimierung

	AG Kombinatorische Optimierung
	Complexity

While some problems are easy from the computational point of view, some others are very difficult and cannot be solved in reasonable time.
In complexity theory it is distinguished between

polynomially solvable (easy) problems,
NP-hard (difficult) problems, and
open problems (for which the status is unknown).

For different classes of scheduling problems we collected a lot of complexity results with the corresponding references:
Complexity results for scheduling problems

Publications:

Single-machine problems with time-lags
- P. Brucker, S. Knust [1999]: Complexity results for single-machine problems with positive finish-start time-lags, Computing 63, 299-316.
- P. Brucker, S. Knust, C. Oguz [2006]: Scheduling chains with identical jobs and constant delays on a single machine, Mathematical Methods of Operations Research 63, 63-75.
Parallel machine problems with outtree precedences
- P. Brucker, J. Hurink, S. Knust [2002]: A polynomial algorithm for P | p_j=1, r_j, outtree | sum C_j, Mathematical Methods of Operations Research 56, 407-412.
Parallel machine problems with setups and a single server
- P. Brucker, C. Dhaenens-Flipo, S. Knust, S.A. Kravchenko, F. Werner [2002]: Complexity results for parallel machine problems with a single server, Journal of Scheduling 5, 429-457.
List-scheduling for parallel machines with setups
- J. Hurink, S. Knust [2001]: Makespan minimization for flow-shop problems with transportation times and a single robot, Discrete Applied Mathematics 112, 199-216.
Parallel batch scheduling problems
- A. Condotta, S. Knust, N.V. Shakhlevich [2010]: Parallel batch scheduling of equal-length jobs with release and due dates, Journal of Scheduling 13, 463-477.
Scheduling problems with constant processing times
- P. Baptiste, P. Brucker, S. Knust, V.G. Timkovsky [2004]: Ten notes on equal-processing-time scheduling, Quarterly Journal of the Belgian, French and Italian Operations Research Societies (4OR) 2, 111-127.
Multi-processor-task problems with parallel processors
- P. Brucker, S. Knust, D. Roper, Y. Zinder [2000]: Scheduling UET task systems with concurrency on two parallel identical processors, Mathematical Methods of Operations Research 52, 369-387.
Shop-problems with transportation delays
- P. Brucker, T.C.E. Cheng, S. Knust, N.V. Shakhlevich [2004]: Complexity results for flow-shop and open-shop scheduling problems with transportation delays, Annals of Operations Research 129, 81-106.
- S. Knust [1999]: Shop-scheduling problems with transportation, Ph.D. thesis, Department of Mathematics and Computer Science, University of Osnabrück.
Flow-shop problems with a single transportation robot
- J. Hurink, S. Knust [2001]: Makespan minimization for flow-shop problems with transportation times and a single robot, Discrete Applied Mathematics 112, 199-216.
- S. Knust [1999]: Shop-scheduling problems with transportation, Ph.D. thesis, Department of Mathematics and Computer Science, University of Osnabrück.
Flow-shop problems with setups and a single server
- P. Brucker, S. Knust, G. Wang [2005]: Complexity results for flow-shop problems with a single server, European Journal of Operational Research 165, 398-407.