New heuristics for the no-wait flowshop with sequence-dependent setup times problem

Autor(es)

Nagano, Marcelo Seido ^[1] ; Araujo, Daniella Castro ^[1]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Sch Engn Sao Carlos, BR-13566590 Sao Carlos, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Journal of the Brazilian Society of Mechanical Sciences and Engineering; v. 36, n. 1, p. 139-151, JAN 2014.
• Citações Web of Science: 12

Resumo

In this paper, we address the problem of scheduling jobs in a no-wait flowshop with sequence-dependent setup times with the objective of minimizing the makespan and the total flowtime. As this problem is well known for being NP hard, we present two new constructive heuristics to obtain good approximate solutions for the problem in a short CPU time, named GAPH and QUARTS. GAPH is based on a structural property for minimizing makespan and QUARTS breaks the problem in quartets to minimize the total flowtime. Experimental results demonstrate the superiority of the proposed approaches over three of the best-known methods in the literature: BAH and BIH, from Bianco et al. (INFOR J 37(1):3-19, 1999) and TRIPS, by Brown et al. (J Oper Res Soc 55(6):614-621, 2004). (AU)

• Processo FAPESP: 09/06832-2 - Programação da produção em sistemas no-wait flow shop com tempos de setup dependentes da sequência
• Beneficiário: Daniella Castro Araujo
• Modalidade de apoio: Bolsas no Brasil - Mestrado