A constructive heuristic for total flowtime minimization in a no-wait flowshop with sequence-dependent setup times

• The problem of scheduling jobs in a no-wait flow shop with sequence-dependent setup times with the objective of minimizing the total flow time.
• A new constructive heuristic, named QUARTS, in order to obtain good approximate solutions in a short CPU time.
• The computational results showed that IGLS obtained the best results and QUARTS presented the best performance regarding other constructive heuristics.

In this paper, we addressed the problem of scheduling jobs in a no-wait flow shop with sequence-dependent setup times with the objective of minimizing the total flow time. As this problem is well-known for being NP-hard, we present a new constructive heuristic, named QUARTS, in order to obtain good approximate solutions in a short CPU time. QUARTS breaks the problem in quartets in order to minimize the total flow time. The method was tested with other literature methods: BAH and BIH by Bianco et al. (1999) [6], TRIPS, by Brown et al. (2004) [7] and the metaheuristic Iterated Greedy with Local Search proposed by Ruiz and Stützle (2007) [25]. The computational results showed that IGLS obtained the best results and QUARTS presented the best performance regarding other constructive heuristics.