FLOWMULT: Permutation Sequences for Flow Shops with Multiple Processors
Authors:
- 1 May 1995
- journal article
- research article
- Published by Taylor & Francis in Journal of Information and Optimization Sciences
- Vol. 16 (2) , 351-366
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.Keywords
This publication has 11 references indexed in Scilit:
- Comparative performance analysis of priority rules in a constrained flow shop with multiple processors environmentEuropean Journal of Operational Research, 1994
- Performance of priority rules in a due date flow shopOmega, 1992
- The Two-Stage Flowshop Scheduling Problem with M Machines at each StageJournal of Information and Optimization Sciences, 1991
- Schedules for a two-stage hybrid flowshop with parallel machines at the second stageInternational Journal of Production Research, 1991
- Branch and bound algorithm for the flow shop with multiple processorsEuropean Journal of Operational Research, 1991
- An Adaptable Scheduling Algorithm for Flexible Flow LinesOperations Research, 1988
- A heuristic algorithm for the m-machine, n-job flow-shop sequencing problemOmega, 1983
- An Evaluation of Flow Shop Sequencing HeuristicsManagement Science, 1977
- A Heuristic Algorithm for the n Job, m Machine Sequencing ProblemManagement Science, 1970
- Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time—A Quick Method of Obtaining a Near OptimumJournal of the Operational Research Society, 1965