Lower bounds for scheduling a single robot in a job-shop environment
|column generation; constraint propagation; lower bounds; Operations Research & Management Science; scheduling; time-lags; TRAVELING SALESMAN PROBLEM; traveling salesman problem with time windows
|KLUWER ACADEMIC PUBL
|ANNALS OF OPERATIONS RESEARCH
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.
2nd International Workshop on the Integration of AI and OR Techniques on Constant Programming for Combinatorial Optimization Problems, PADERBORA, GERMANY, MAR, 2000
Show full item record
checked on Feb 23, 2024