Minimizing Total Weighted Completion Time in a Proportionate Flow Shop

摘要

The authors study the special case of the m machine flow shop problem in whichthe processing time of each operation of job j is equal to pj; this variant of the flow shop problem is known as the proportionate flow shop problem. The authors show that for any number of machines and for any regular performance criterion the authors can restrict their search for an optimal schedule to permutation schedules. Moreover, the authors show that the problem of minimizing total weighted completion time is solvable in O(n squared) time. (Copyright (c) 1996 Eindhoven University of Technology.)