Article ID: | iaor2004978 |
Country: | Germany |
Volume: | 57 |
Issue: | 2 |
Start Page Number: | 173 |
End Page Number: | 206 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Methods of Operations Research (Heidelberg) |
Authors: | Wanke E., Espelage W. |
Keywords: | scheduling |
We consider the movement minimization problem in a conveyor flow shop processing controlled by one worker for all machines. A machine can only execute tasks if the worker is present. Each machine can serve as a buffer. The objective is to minimize the total number of movements of the worker for the processing of all jobs. Such minimization problems usually appear in conveyor controlled manufacturing systems. We show the NP-completeness of the problem and introduce an approximation algorithm with error ratio 2.