Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment |
| |
Authors: | Peter Brucker Sigrid Knust |
| |
Institution: | (1) Fachbereich Mathematik/Informatik, Universität Osnabrück, D-49069 Osnabrück, Germany |
| |
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. |
| |
Keywords: | scheduling traveling salesman problem with time windows time-lags lower bounds constraint propagation column generation |
本文献已被 SpringerLink 等数据库收录! |