Article ID: | iaor200681 |
Country: | Netherlands |
Volume: | 162 |
Issue: | 1 |
Start Page Number: | 99 |
End Page Number: | 111 |
Publication Date: | Apr 2005 |
Journal: | European Journal of Operational Research |
Authors: | Knust Sigrid, Hurink Johann |
Keywords: | heuristics |
We consider a generalized job-shop problem where the jobs additionally have to be transported between the machines by a single transport robot. Besides transportation times for the jobs, empty moving times for the robot are taken into account. The objective is to determine a schedule with minimal makespan. We present local search algorithms for this problem where appropriate neighborhood structures are defined using problem-specific properties. A one-stage procedure is compared with a two-stage approach and a combination of both. Computational results are presented for test data arising from job-shop benchmark instances enlarged by transportation and empty moving times.