A tabu search algorithm for scheduling a single robot in a job-shop environment (Q1602712)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A tabu search algorithm for scheduling a single robot in a job-shop environment |
scientific article |
Statements
A tabu search algorithm for scheduling a single robot in a job-shop environment (English)
0 references
24 June 2002
0 references
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.
0 references
tabu search
0 references
single-machine scheduling
0 references
robot scheduling
0 references
generalization of the traveling salesman problem
0 references
time windows
0 references
local search algorithm
0 references