Parallel flow shop schedulİng wİth common workstatİons

Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Faculty of Engineering, Department of Industrial Engineering, Turkey

Approval Date: 2019

Student: Muhammet Kemal Çakıcı



In this thesis, we address the parallel flow shop scheduling problem with common workstations to minimize the makespan, considering the flow shop design defined solely by the number of operators at the workstations. We are motivated by the production environment of a compressor manufacturing company located in Konya, Turkey. Different from the similar studies in the literature, we use common workstations at some of the stages, prefer to place limited buffer areas between the stages, and do not allow for job crossing between the flow shops. We develop two different Mixed Integer Linear Programming (MILP) models for this scheduling problem. These MILPs barely provide the optimal solution in almost one-hour time which is the time restriction in this study; hence, we propose several heuristic approaches that are based on the well-known NEH Algorithm. Moreover, two dispatching rules, SPT and LPT, are utilized to evaluate the results of the MILPs and the proposed heuristics better. We perform extensive computational experiments using several problem instances that are differentiated by the number of operators and jobs, and compare the solution approaches. The results indicate that the proposed heuristic approaches are superior to the dispatching rules providing very close results to the MILP results in a short time and even better results as the number of jobs increases. In the experiments carried out for the compressor company’s case, the proposed heuristic methods provide promising solutions that make it possible for the decision maker to select the most productive shop design doubling the production volume.