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

Author(s)

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

Affiliation

^[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

• Document type: Journal article
• Source: ENGINEERING OPTIMIZATION; AUG 2021.
• Web of Science Citations: 0

Abstract

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)

• FAPESP's process: 20/16341-5 - Exact and approximate methods to solve the Open Shop scheduling problem with explicit sequence-dependent setup times
• Grantee: Levi Ribeiro de Abreu
• Support Opportunities: Scholarships in Brazil - Master