A penalty-shift-insertion-based algorithm to minimize total flow time in no-wait flow shops

This paper proposes a penalty‐shift‐insertion (PSI)‐based algorithm for the no‐wait flow shop scheduling problem to minimize total flow time. In the first phase, a penalty‐based heuristic, derived from Vogel’s approximation method used for the classic transportation problem is used to generate an initial schedule. In the second phase, a known solution is improved using a forward shift heuristic. Then the third phase improves this solution using a job‐pair and a single‐job insertion heuristic. Results of the computational experiments with a large number of randomly generated problem instances show that the proposed PSI algorithm is relatively more effective and efficient in minimizing total flow time in a no‐wait flow shop than the state‐of‐the‐art procedures. Statistical significance of better results obtained by the proposed algorithm is also reported.