A new two-stage constraint programming approach for open shop scheduling problem with machine blocking

Abstract

In this paper, a variant of the open shop scheduling problem is considered in which the intermediate storage is forbidden among two adjacent production stages (zero buffer or machine blocking constraint). The performance measure is to minimise the maximal completion time of the jobs (makespan). Since this is an NP-hard problem, a two-stage constraint programming approach is proposed as a new exact method. Computational experiments were carried out on 222 literature problem instances in order to test the performance of the proposed algorithm. The relative deviation is adopted as the performance criteria. Computational results point to the ability of the proposed method to solve large-sized instances in comparison with the developed mixed-integer linear programming model and a simple constraint programming model, both with user cuts. In all set of instances, the proposed two-stage method performed better than benchmarking methods and integer programming models, with average relative deviation regarding objective values as lower as 12%. In addition, the results point to a competitive efficiency in computational times of the proposed method with less than 200 s in the most instances to obtain the optimal solution, in comparison to competitive metaheuristics from literature of the problem, for the tested test instances.

Keywords:

• Production scheduling
• constraint programming
• two-stage
• zero buffer
• blocking

Data availability statement

The data sets, results of all computational tests and statistical analyses are available in the following link: http://dx.doi.org/10.13140/RG.2.2.24586.59845/1. Another data or any questions are available upon request.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the Brazilian National Council for Scientific and Technological Development (Conselho Nacional de Desenvolvimento Científico e Tecnológico) [Nos. 309755/2021-2, 407151/2021-4, and 312585/2021-7]; the Brazilian Coordination for the Improvement of Higher Education Personnel (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior) [No. 001]; the São Paulo Research Foundation (FAPESP) - through Grant no. #2021/11586-2.

Notes on contributors

Levi R. Abreu

Levi R. de Abreu has a graduate in Industrial Engineering from the University of Ceará (UFC), Fortaleza, Ceara, Brazil, and is a Ph.D. student in Production Engineering from the University of São Paulo (USP), São Carlos, São Paulo, Brazil. His research is concentrated on Production Scheduling Problems with heuristic and mathematical programming approaches, with industrial applications in general.

Marcelo S. Nagano

Marcelo S. Nagano is a Professor at the School of Engineering of São Carlos in the University of São Paulo, Brazil, where is currently hold the position of Head of the Operations Research Group of the Production Engineering Department. Along with your teaching duties, your research interests refer to decision systems and models in industry and services, including a range of decisions related to the design and optimisation of processes, production and planning and scheduling, as well as Knowledge Management and Innovation Management as a supporting infrastructure. In these areas, is carried out several research projects and produced a number of refereed publications. He has some editorial duties, most notably he is a member of the Editorial Board of International Journal of Industrial Engineering Computations, Management Science Letters, Technology Audit and Production Reserves and Journal of Applied Research on Industrial Engineering. He has more than two hundred papers published in important journals with impact factors and Journal Citation Reports in Web of Sciences and SCOPUS. He is currently conducting research in cooperation with the University of Alabama in Huntsville AL/USA, Tennessee Technological University, Cookeville, TN/USA, University of Seville, Seville/ES and University Polytechnic of Valencia, Valencia/ES.

Bruno A. Prata

Bruno A. Prata has a Ph.D. in Industrial Engineering (University of Porto, Portugal). He is an Associate Professor in the Department of Industrial Engineering of Federal University of Ceara (Fortaleza, Brazil). His main research interests are combinatorial optimisation problems, metaheuristics, and transportations systems. He regularly publishes papers in international scientific journals.