Lecture Notes in Computer Science, 2001, Volume 2136/2001, 363-374, DOI: 10.1007/3-540-44683-4_32

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

Wolfgang Espelage and Egon Wanke

View Related Documents

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.
The work of the first author was supported by the German Research Association (DFG) grant WA 674/8-2.

Fulltext Preview

Image of the first page of the fulltext document