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

Hurink, Johann and Knust, Sigrid (2002) A tabu search algorithm for scheduling a single robot in a job-shop environment. Discrete Applied Mathematics, 119 (1-2). pp. 181-203. ISSN 0166-218X

PDF
Restricted to UT campus only: Request a copy
192Kb

Abstract:	We consider a single-machine scheduling problem which 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 travelling-salesman 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 problem-specific 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 job-shop instances with a single transport robot.
Item Type:	Article
Copyright:	© 2002 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/63576
Official URL:	http://dx.doi.org/10.1016/S0166-218X(01)00273-6
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 208555