Lower bounds for scheduling a single robot in a job-shop environment

Autor(en): Brucker, P
Knust, S 
Stichwörter: column generation; constraint propagation; lower bounds; Operations Research & Management Science; scheduling; time-lags; TRAVELING SALESMAN PROBLEM; traveling salesman problem with time windows
Erscheinungsdatum: 2002
Herausgeber: KLUWER ACADEMIC PUBL
Journal: ANNALS OF OPERATIONS RESEARCH
Volumen: 115
Ausgabe: 1-4
Startseite: 147
Seitenende: 172
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 (minimal time-lags) 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 calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.
Beschreibung: 
2nd International Workshop on the Integration of AI and OR Techniques on Constant Programming for Combinatorial Optimization Problems, PADERBORA, GERMANY, MAR, 2000
ISSN: 02545330
DOI: 10.1023/A:1021149204501

Show full item record

Page view(s)

2
Last Week
0
Last month
1
checked on Feb 23, 2024

Google ScholarTM

Check

Altmetric