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

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.

Keywords:

• Production sequencing
• makespan
• constraint programming
• exact methods

Disclosure statement

No potential conflict of interest was reported by the author(s).

Availability of data and materials

The data sets, results of all computational tests and statistical analyses are available in the following link: https://www.dropbox.com/sh/qm51b5a4pghhmvp/AAD4wy0XimKx_aKmrTD_7Vo2a?dl=0. Other data and answers to any questions are available upon request.

Additional information

Funding

This study was financed in part by the Brazilian Coordination for the Improvement of Higher Education Personnel (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES) [No. 88882.379108/2019-0]; the Brazilian National Council for Scientific and Technological Development (Conselho Nacional de Desenvolvimento Científico e Tecnológico-CNPq) [Nos. 404232/2016-7, 303594/2018-7, 306075/2017-2 and 430137/2018-4]; the São Paulo Research Foundation (Fundação de Amparado à Pesquisa do Estado de São Paulo - FAPESP) [No. #2020/16341-5].