In machine scheduling models jobs consisting of different operations have
to be scheduled on a set of machines such that a given objective function
is minimized. If additionally the jobs have to be transported between the
machines by some robots, we get the following situation:
Besides deriving new complexity results for different scheduling scenarios
combined with transportation aspects we developed algorithms which deal with
job-shop problems with a single robot.
The used techniques are local search algorithms, constraint propagation,
linear programming, column generation and dynamic programming.
Publications:
General topics
P. Brucker, S. Knust [2006]:
Complex Scheduling, Springer.
P. Brucker, S. Knust [2012]:
Complex Scheduling, 2nd edition, Springer.
S. Knust [1999]:
Shop-scheduling problems with transportation,
Ph.D. thesis, Department of Mathematics and Computer Science,
University of Osnabrück.
Complexity results
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.
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.
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.
Heuristic algorithms
J. Hurink, S. Knust [2002]:
A tabu search algorithm for scheduling a single robot in a job-shop
environment, Discrete Applied Mathematics 119, 181-203.
J. Hurink, S. Knust [2005]:
Tabu search algorithms for job-shop problems with a single transport robot,
European Journal of Operational Research 162, 99-111.
S. Knust [1999]:
Shop-scheduling problems with transportation,
Ph.D. thesis, Department of Mathematics and Computer Science,
University of Osnabrück.
J. Poppenborg, S. Knust, J. Hertzberg [2012]:
Online scheduling of flexible job-shops with blocking and transportation,
European Journal of Industrial Engineering 6, 497-518.
A. Condotta, S. Knust, D. Meier, N.V. Shakhlevich [2013]:
Tabu search and lower bounds for a combined production-transportation problem,
Computers and Operations Research 40, 886-900.
C. Viergutz, S. Knust [2014]:
Integrated production and distribution scheduling with lifespan constraints,
Annals of Operations Research 213, 293-318.
Lower bounds
P. Brucker, S. Knust [2002]:
Lower bounds for scheduling a single robot in a job-shop environment,
Annals of Operations Research 115, 147-172.
A. Condotta, S. Knust, D. Meier, N.V. Shakhlevich [2012]:
Tabu search and lower bounds for a combined production-transportation problem,
to appear in Computers and Operations Research
Railway Scheduling
An example for a railway scheduling problem is the
rescheduling of trains when one track of a railway section is closed
due to construction activities. We developed an algorithm which
tries to find a good new schedule minimizing the lateness of the trains:
Publications:
P. Brucker, S. Heitmann, S. Knust [2002]:
Scheduling railway traffic at a construction site, OR Spectrum 24, 19-30.
Projects:
Resource-constrained project scheduling: Models, methods and
applications; Complex machine-scheduling problems DFG (1996-2001)
Involved:
Prof. Dr. Peter Brucker (Osnabrück);
Prof. Dr. Andreas Drexl (Kiel);
Prof. Dr. Rolf Möhring (Berlin);
Prof. Dr. Klaus Neumann (Karlsruhe);
Prof. Dr. Erwin Pesch (Bonn)
Complex Job-Shop Scheduling Problems DAAD (2000-2001)
Involved:
Prof. Dr. Peter Brucker (Osnabrück);
Prof. Dr. T.C.E. Cheng (Polytechnical University Hongkong)
Scheduling Problems with Blocking and Flexible Routings DAAD (2005-2006)
Involved:
Prof. Dr. Peter Brucker (Osnabrück);
Prof. Dr. Philippe Baptiste (Ecole Polytechnique, Paliseau, France);
Juniorprof. Dr. Sigrid Knust (Osnabrück)
