FLOWMULT: Permutation sequences for flow shops with multiple processors

FLOWMULT: Permutation sequences for flow shops with multiple processors

0.00 Avg rating0 Votes
Article ID: iaor19961603
Country: India
Volume: 16
Issue: 2
Start Page Number: 351
End Page Number: 366
Publication Date: May 1995
Journal: Journal of Information & Optimization Sciences
Authors: , ,
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, the authors 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.

Reviews

Required fields are marked *. Your email address will not be published.