FLOWMULT: Permutation Sequences for Flow Shops with Multiple Processors

Abstract

This paper is concerned with minimum makespan study in the flow shop with multiple processors (FSMP) scheduling environment. The FSMP, also known as the hybrid flow shop, is characterized as a flow shop environment where, at any stage, there may exist multiple processors. In this study, we consider the case for which the multiple processors at any given stage are identical. This paper presents a methodology, known as FLOWMULT, which is used to develop list schedules based upon permutations of job order. Given that n jobs are to be processed at m stages in the FSMP, FLOWMULT generates n! schedules-each stemming from a permutation of the n jobs. Each permutation is used at the first stage and the jobs proceed through the system in a FIFO manner. A comparison of FLOWMULT’s results over a set of 653 problems with known optimal solutions shows that FLOWMULT finds the optimal makespan in approximately 90% of the cases and, overall, is within 5% of the optimal makespan in approximately 98% of the cases. There does exist a drawback in computation time since FLOWMULT’s order of computation is factorial in nature. On the other hand, since the optimal makespan resides in a set of more than n! ^m schedules for this problem, this study indicates that searching only n!, or less, nondelay schedules will produce a makespan which is not appreciably worse than the optimal schedule.