Online-Scheduling of a Fleet of Transportation Robots 

This master thesis deals with the problem of scheduling a fleet
consisting of multiple transportation robots in a well-defined
environment. These transportation robots are used to transport artefacts
between various working stations, of which each working station can
exist multiple times. The artefacts could, for example, be laboratory
samples in a life science research lab environment. The processing of
one such artefact can include the use of several different working
stations. Also, transfer stations may exist where the transportation
robots have to pick up the artefacts before the processing can start and
to which the artefacts are delivered after the processing has finished.
These transfer stations could, for example, be laboraties in which the
employees of a life science business prepare and study the laboratory
samples. Additionally, between the processing of an artefact on two
different working stations, perishability constraints may be given. That
is, only a certain amount of time may pass between the time at which the
artefact finishes processing on the first working station and the time
at which the artefact starts processing on the next working station.
Finally, the given problem is an online problem. As such, the tasks to
be processed will only be entered into the system as they become
available. This requires the scheduler to create plans based on only
partial information. Also, existing plans may have to be modified as new
tasks become available.

In order to solve the given scheduling problem described above, the
problem is modelled as a flexible job shop in which several working
stations of the same type as well as several transportation robots can
be available to process the same operation. Thus, unlike a job shop
problem, a flexible job shop also requires that every operation is
assigned a definite resource. Additional constraints for the given
problem are maximal and minimal distances between two operations as well
as blocking constraints if two operations of different jobs require the
same resource. As objective function, the weighted total tardiness as
well as the driven distance of the tramsportation robots have to be
minimised. Based on this model, an online scheduler is developed that
utilises a tabu search algorithm to create feasible schedules.