An improved heuristic to minimize total flow time for scheduling in the m-machine no-wait flow shop

• We present a heuristic to minimize total flow time in no-wait flow shop scheduling.
• The proposed heuristic significantly outperforms the best-known heuristics.
• The complexity of the proposed method is comparable to the existing heuristics.
• Statistical tests of significance substantiate the superiority of the method.

In this paper, we present a constructive heuristic to minimize total flow time criterion for the well-known NP-hard no-wait flow shop scheduling problem. It is based on the assumption that the priority of a job in the initial sequence is given by the sum of its processing times on the bottleneck machines. The initial sequence of jobs thus generated is further improved using a new job insertion technique. We show, through computational experimentation, that the proposed method significantly outperforms the best-known heuristics while retaining its time complexity of O(n2). Statistical tests of significance are used to confirm the improvement in solution quality.