Geometrical Heuristics for Multiprocessor Flowshop Scheduling with Uniform Machines at Each Stage

S.V. Sevastianov (sevamath.nsc.ru)

Abstract: We consider the multi-stage multiprocessor flowshop scheduling problem with uniform machines at each stage and the minimum makespan objective. Using a vector summation technique, three polynomial-time heuristics are developed with absolute worst-case performance guarantees. As a direct corollary, in the special case of the ordinary flowshop problem we come to the best approximation algorithms (both in absolute performance guarantee and in running time) known for this problem.

Keywords: Multiprocessor Flowshop Scheduling, Uniform Parallel Machines, Approximation, Worst-case analysis

Category 1: Applications -- OR and Management Sciences (Scheduling )

Citation: J. Scheduling, to appear

Download: [Postscript]

Entry Submitted: 02/15/2001
Entry Accepted: 02/15/2001
Entry Last Modified: 02/16/2001

Modify/Update this entry