Minimizing makespan in parallel flowshops
- PDF / 218,097 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 0 Downloads / 196 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
Minimizing makespan in parallel ¯owshops PS Sundararaghavan1, AS Kunnathur1 and I Viswanathan2 1
The University of Toledo, Ohio and 2 Alcoa Package Machinery, Inc, Colorado, USA
In this study, a new class of proportional parallel ¯ow shop problems with the objective of minimizing the makespan has been addressed. A special case for this problem in which jobs are processed on only one machine as opposed to two or more machines in a ¯ow shop, is the well-known multiple processor problem which is NP-complete. The parallel processor problem is a restricted version of the problems addressed in this paper and hence are NP-complete. We develop and test heuristic and simulation approaches to solve large scale problems, while using exact procedures for smaller problems. The performance of the heuristics relative to the LP lower bound as well as a comparison with the truncated integer programming solution are reported. The performance of the heuristics and the simulation results were encouraging. Keywords: scheduling; parallel ¯ow-shop; heuristics; sequencing
Introduction The two machine ¯owshop has received considerable attention in the scheduling literature ever since Johnson's1 seminal work published in the ®fties. The problem of scheduling jobs on parallel processors has also received a good deal of attention in the research literature. However, the problem of scheduling jobs on parallel processing systems where the systems are ¯owshops with two or more machines has received little attention. General problems dealing with parallel ¯owshops will be the focus of this paper. We address some special cases in depth and discuss the complexity of the general cases.
objective will be to minimize the makespan for completing all 10 projects. Problems such as the one described above can be formulated as a multi-processor multi-stage ¯ow shop problem. In our example there are two processors per stage for each 10 jobs. This can be cast into a parallel ¯ow shop problem by putting together one of the two employees for each stage into one ¯owshop and the remaining employees into the other ¯owshop. Figure 1 presents a schematic diagram of this scheduling situation with two stages. At each stage j, for a job, there are preferred machines and non-preferred machines. A preferred machine processes a job faster than a non-preferred machine. The objective is to minimize the makespan. An industrial
Multi-processor multi-stage ¯owshop; a practical example Consider an engineering consulting ®rm which provides expert advice on manufacturing projects. Assume that there are 10 projects available at the start of the month. A typical consulting project involves seven stages: fact ®nding, analysis, development of speci®cations, cost estimation, solution design, preparation of documentation, and presentation of project report. The completion of the project requires the performance of the seven activities in sequence. Two employees are available at each stage. The time t
Data Loading...
