Movement minimization for unit distances in conveyor flow shop processing

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. Copyright Springer-Verlag Berlin Heidelberg 2003