A linear time approximation algorithm for movement minimization 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 worker has to cover a certain distance to move from one machine to the other. The distance between two machines Pp and Pq is |p?q|. The objective is to minimize the total distance the worker has to cover for the processing of all jobs. We introduce a linear time approximation algorithm for the conveyor flow shop problem with performance 3. Such minimization problems usually appear in conveyor controlled manufacturing systems.
approximation algorithms problem complexity movement optimization control