A tabu search algorithm for scheduling a single robot in a jobshop environment
Hurink, Johann and Knust, Sigrid (2002) A tabu search algorithm for scheduling a single robot in a jobshop environment. Discrete Applied Mathematics, 119 (12). pp. 181203. ISSN 0166218X
PDF
Restricted to UT campus only : Request a copy 196kB 
Abstract:  We consider a singlemachine scheduling problem which arises as a subproblem in a jobshop 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 travellingsalesman problem with time windows, where additionally generalized precedence 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 travelling and waiting times is minimized. We present a local search algorithm for this problem where an appropriate neighborhood structure is defined using problemspecific properties. In order to make the search process more efficient, we apply some techniques which accelerate the evaluation of the solutions in the proposed neighbourhood considerably. Computational results are presented for test data arising from jobshop instances with a single transport robot.

Item Type:  Article 
Copyright:  © 2002 Elsevier 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/63576 
Official URL:  http://dx.doi.org/10.1016/S0166218X(01)002736 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 208555