A 3-Approximation Algorithm for Movement Minimization in Conveyor Flow Shop Processing

Abstract 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 for exactly one job. The worker has to cover a certain distance to move from one machine to the next or previous one. The objective is to minimize the total distance the worker has to cover for the processing of all jobs. We introduce the first polynomial time approximation algorithm for this problem with a performance bounded by some fixed factor.

Authors

• Wolfgang Espelage
• Egon Wanke

Keywords

No keywords are indexed for this paper.