A tabu search algorithm for scheduling a single robot in a job-shop environment (Q1602712)

A single-machine scheduling problem is considered, that arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized prcedence constraints have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized. The authors present a local search algorithm for this problem where an appropriate neighborhood structure is defined using problem-specific properties.