DEVELOPMENT OF A NEW HEURISTIC FOR SCHEDULING FLOW-SHOPS WITH PARALLEL MACHINES BY PRIORITIZING BOTTLENECK STAGES

The flow-shop scheduling problem has been extensively studied in literature. Many researchers have developed various flow-shop scheduling algorithms and heuristics for a variety of cases. The problem of scheduling flow-shops with three or more stages has been shown to be NP-Complete in strong sense. Complexity of the problem increases if one or more of the flow-shop stages have multiple identical (parallel) machines. Flow-shops with parallel machines are quite common in practice, yet comparatively limited amount of research has been performed in the area. In this research work a heuristic procedure, Progressive Bottleneck Improvement (PBI) procedure, is developed for scheduling flow-shops with parallel machines to minimize makespan. This heuristic schedules a set of jobs by identifying the bottleneck stages in the flow-shop, and schedules jobs to improve the overall bottleneck performance. One of the problems in achieving this is that there exists no algorithm that can exactly identify the bottleneck stage in a flow-shop with parallel machines. The PBI heuristic overcomes this difficulty by recalculating the bottleneck every time it sequences a job. The initial sequence thus developed is later improved using certain improvement rules. The heuristic is tested using random data and the datasets used by Wittrock (1988) and Cheng et al. (2001). This paper presents the heuristic and then posts the results obtained.