A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions

Autor(es)

de Abreu, Levi Ribeiro ^[1] ; Guimaraes Araujo, Kennedy Anderson ^[2] ; Prata, Bruno de Athayde ^[3] ; Nagano, Marcelo Seido ^[1] ; Moccellin, Joao Vitor ^[3]

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

^[1] Univ Sao Paulo, Dept Prod Engn, Sao Carlos - Brazil

^[2] Univ Sao Paulo, Dept Appl Math, Sao Paulo - Brazil

^[3] Univ Fed Ceara, Dept Ind Engn, Fortaleza, Ceara - Brazil

• Tipo de documento: Artigo Científico
• Fonte: ENGINEERING OPTIMIZATION; AUG 2021.
• Citações Web of Science: 0

Resumo

This article presents a new variant for the open shop scheduling problem, the open shop scheduling problem with repetitions (OSSPR), where the jobs can be processed on any machine more than once (operation by operation). Thereby, all the jobs can be scheduled in an unconstrained way, substantially increasing the number of feasible solutions in comparison with the classical open shop. The OSSPR has many applications in automotive and maintenance actives. To solve the problem, a mixed-integer linear programming model is presented and a new constraint programming model is proposed. Since the problem under study is NP-hard, a new efficient variable neighbourhood search is proposed using variable search strategies through the proposed constraint programming model. The objective function is makespan minimization, and it uses the lower bound deviation as performance criterion. Computational results show very good performance of the proposed metaheuristic on the instances tested. (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