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

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

0.00 Avg rating0 Votes
Article ID: iaor20031635
Country: Netherlands
Volume: 115
Issue: 1
Start Page Number: 147
End Page Number: 172
Publication Date: Sep 2002
Journal: Annals of Operations Research
Authors: ,
Keywords: job shop, robots
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 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.

Reviews

Required fields are marked *. Your email address will not be published.