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

Autor(en): Hurink, J
Knust, S 
Stichwörter: Mathematics; Mathematics, Applied; scheduling; tabu search; time-lags; TRAVELING SALESMAN PROBLEM; traveling salesman problem with time windows
Erscheinungsdatum: 2002
Herausgeber: ELSEVIER SCIENCE BV
Journal: DISCRETE APPLIED MATHEMATICS
Volumen: 119
Ausgabe: 1-2
Startseite: 181
Seitenende: 203
Zusammenfassung: 
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 traveling 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 traveling 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 neighborhood considerably. Computational results are presented for test data arising from job-shop instances with a single transport robot. (C) 2002 Elsevier Science B.V. All rights reserved.
ISSN: 0166218X
DOI: 10.1016/S0166-218X(01)00273-6

Show full item record

Page view(s)

2
Last Week
0
Last month
2
checked on Feb 29, 2024

Google ScholarTM

Check

Altmetric