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

Johann L. Hurink, Sigrid Knust

Research output: Book/ReportReportProfessional

75 Downloads (Pure)


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.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages26
Publication statusPublished - 1999

Publication series

PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • MSC-90B35


Dive into the research topics of 'A tabu search algorithm for scheduling a single robot in a job-shop environment'. Together they form a unique fingerprint.

Cite this