A constructive heuristic for total flowtime minimization in a no-wait flowshop with sequence-dependent setup times. (July 2015) - Nagano, Marcelo Seido; Miyata, Hugo Hissashi; Araújo, Daniella Castro
Highlights: 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. Abstract: 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.