An Efficient Heuristic Algorithm for m- Machine No-Wait Flow Shops

摘要

We propose a constructive heuristic for the well known NP-hard problem of no-wait flow shop scheduling. It is based on the assumption that the priority of a job in the sequence is given by the sum of its processing times on the bottleneck machine(s) for selecting the initial sequence of jobs. The computational experimentations show that there is a significant improvement in solution quality over the existing heuristic; especially for large problem sizes while not affecting its time complexity. Statistical tests are used to substantiate the significance of the results by the proposed method.