MINIMIZING MAKESPAN IN PARALLEL FLOWSHOPS

In this study, a new class elf proportional parallel flow shop problem s 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 flow shop, is the well -known multiple processor problem which is NP-complete. The parallel p rocessor problem is a restricted version of the problems addressed in this paper and hence are NP-complete. We develop and test heuristic an d simulation approaches to solve large scale problems, while using exa ct procedures for smaller problems. The performance of the heuristics relative to the LP lower bound as well as a comparison with the trunca ted integer programming solution are reported, The performance of the heuristics and the simulation results were encouraging.