A Novel Constraint Programming Decomposition Approach for the Total Flow Time Fixed Group Shop Scheduling Problem

Francisco Yuraszeck, Gonzalo Mejía, Jordi Pereira and Mariona Vilà
Additional contact information
Francisco Yuraszeck: Facultad de Ingeniería, Universidad Andres Bello, Quillota 980, Viña del Mar 2531015, Chile
Gonzalo Mejía: Facultad de Ingeniería, Universidad de La Sabana, Campus Universitario Puente del Común, Km 7 Autopista Norte de Bogotá, Chía 250001, Colombia
Jordi Pereira: Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Padre Hurtado 750, Viña del Mar 2520001, Chile
Mariona Vilà: Academic Department, EAE Business School, 08015 Barcelona, Spain

Mathematics, 2022, vol. 10, issue 3, 1-26

Abstract: This work addresses a particular case of the group shop scheduling problem (GSSP) which will be denoted as the fixed group shop scheduling problem (FGSSP). In a FGSSP, job operations are divided into stages and each stage has a set of machines associated to it which are not shared with the other stages. All jobs go through all the stages in a specific order, where the operations of the job at each stage need to be finished before the job advances to the following stage, but operations within a stage can be performed in any order. This setting is common in companies such as leaf spring manufacturers and other automotive companies. To solve the problem, we propose a novel heuristic procedure that combines a decomposition approach with a constraint programming (CP) solver and a restart mechanism both to avoid local optima and to diversify the search. The performance of our approach was tested on instances derived from other scheduling problems that the FGSSP subsumes, considering both the cases with and without anticipatory sequence-dependent setup times. The results of the proposed algorithm are compared with off-the-shelf CP and mixed integer linear programming (MILP) methods as well as with the lower bounds derived from the study of the problem. The experiments show that the proposed heuristic algorithm outperforms the other methods, specially on large-size instances with improvements of over 10% on average.

Keywords: scheduling; fixed group shop; group shop; constraint programming (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/3/329/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/3/329/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:3:p:329-:d:730539

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().