Planeacion agregada

European Journal of Operational Research 113 (1999) 113±122

Theory and Methodology

Heuristics for scheduling in a ¯ow shop with multiple processors
Shaukat A. Brah
a

a,*

, Luan Luan Loo

b

Department of Decision Sciences, Faculty of Business Administration, National University of Singapore, Singapore 119260, Singapore b Ministry of Education, Kay Siang Road, Singapore 248922,Singapore Received 1 November 1995; accepted 1 October 1997

Abstract This study investigates the performance of scheduling heuristics in a ¯ow shop with multiple processors. We investigated ®ve better performing ¯ow shop heuristics for their performances of makespan and mean ¯ow time criteria in a ¯ow shop with multiple processors. The study examined the e€ects of problem characteristics (numberof jobs, number of machine stages and number of parallel processors at each stage) and the performance of heuristics using regression analysis. We found that although structural characteristics explain most of the variation in performance, heuristics also had an e€ect. The experimental results showed that ¯ow shop heuristics developed by Nawaz, Enscore, and Ham and that of Ho were comparable inperformance in a ¯ow shop with multiple processors. However, the former was slightly more consistent in results for both criteria. Ó 1999 Elsevier Science B.V. All rights reserved. Keywords: Scheduling; Flow shop with multiple processors; Flexible ¯ow lines; Simulation; Heuristics

1. Introduction The ¯ow shop with multiple processors (FSMP), also called ¯exible ¯ow lines, is a generalization ofthe ¯ow shop problem. The FSMP scheduling involves sequencing of jobs in a ¯ow shop, where for at least one stage the processor has more than one identical machine. The machines are subject to capacity constraint, which denote that each machine can process at most one job at a time. While, the jobs are subject to precedence

Corresponding author. Tel.: 65 874 3013; fax: 65 779 2621; e-mail:fbabrahs@nus.edu.sg.

*

constraint that limits them to an identical processing order through all stages of operation. The FSMP scheduling involves sequencing of jobs with the objective of satisfying some regular measure of performance. Examples include minimizing the maximum ¯ow time commonly known as makespan, mean ¯ow time, mean tardiness and machine idle time. The research in the area hasbene®ted from growing interest of a number of researchers. The interest comes from many applications of this scheduling problem, enhanced computational capability, and limited available response time in an increasingly automated work environment. There is a limited amount of research on heuristics for the FSMP scheduling. Also, a review of

0377-2217/99/$ ± see front matter Ó 1999 Elsevier ScienceB.V. All rights reserved. PII: S 0 3 7 7 - 2 2 1 7 ( 9 7 ) 0 0 4 2 3 - 2

114

S.A. Brah, L.L. Loo / European Journal of Operational Research 113 (1999) 113±122

past research shows a lack of use of ¯ow shop heuristics in a FSMP scheduling studies. Therefore, this research aims to explore the feasibility of using various heuristics, which have shown prominence in reducing makespan and mean¯ow time, in a ¯ow shop and shall demonstrate their performance in a FSMP. In doing so, we expect to identify better performing heuristics for a FSMP. We investigated ®ve heuristics for two regular measures of performance, makespan and mean ¯ow time. We examined the e€ects of problem attributes, such as number of jobs, number of machine stages and number of parallel processors at each stage, and theheuristics with the help of regression analysis. Later, using analysis of variance, we studied the comparative performance of all heuristics. 2. Literature review 2.1. Flow shop The ¯ow shop scheduling problem is one of the classical quantitative combinatorial search problems. Johnson's rule is a classical optimization algorithm for minimizing makespan. In addition, there is an extensive...