A new hybridization of adaptive large neighborhood search with constraint programming for open shop scheduling with sequence-dependent setup times

Autor(es)

Abreu, Levi R. ; Nagano, Marcelo S.

• Tipo de documento: Artigo Científico
• Fonte: COMPUTERS & INDUSTRIAL ENGINEERING; v. 168, p. 20-pg., 2022-06-01.

Resumo

In recent years, researchers have been paying special attention to scheduling problems with setup times and costs, aiming to adopt more realistic assumptions. This paper aims at presenting a new hybridization of an adaptive large neighborhood search (ALNS) with constraint programming (CP) as a local search phase for open shop scheduling with non-anticipatory sequence-dependent setup time. An integer linear programming model is presented based on the classic open shop model, and a new CP model is proposed with non-anticipatory setup times. The proposed CP model has not been addressed in the revised literature and outperforms all other exact methods. The objective function adopted is makespan minimization, and we use the relative deviation as performance criteria. Since the problem under study is NP-hard, we test many approximations and exact algorithms to obtain high-quality solutions in acceptable computational times. The extensive computational experience shows that the proposed hybridization of metaheuristic and constraint programming is promising for solving large-sized instances. (AU)

• Processo FAPESP: 20/16341-5 - Métodos exatos e bioinspirados para a solução do problema de programação da produção em sistemas Open Shop com tempos de preparação explícitos
• Beneficiário: Levi Ribeiro de Abreu
• Modalidade de apoio: Bolsas no Brasil - Mestrado