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
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.