IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i3p329-d730539.html
   My bibliography  Save this article

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

Author

Listed:
  • Francisco Yuraszeck

    (Facultad de Ingeniería, Universidad Andres Bello, Quillota 980, Viña del Mar 2531015, Chile
    Escuela de Ingeniería Industrial, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, 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
    UPF Barcelona School of Management, Universitat Pompeu Fabra, C. Balmes 132-134, 08008 Barcelona, Spain)

  • Mariona Vilà

    (Academic Department, EAE Business School, 08015 Barcelona, Spain)

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.

Suggested Citation

  • Francisco Yuraszeck & Gonzalo Mejía & Jordi Pereira & Mariona Vilà, 2022. "A Novel Constraint Programming Decomposition Approach for the Total Flow Time Fixed Group Shop Scheduling Problem," Mathematics, MDPI, vol. 10(3), pages 1-26, January.
  • Handle: RePEc:gam:jmathe:v:10:y:2022:i:3:p:329-:d:730539
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/3/329/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/10/3/329/
    Download Restriction: no
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Antonin Ponsich & Bruno Domenech & Mariona Vilà, 2023. "Preface to the Special Issue “Mathematical Optimization and Evolutionary Algorithms with Applications”," Mathematics, MDPI, vol. 11(10), pages 1-6, May.
    2. Anran Zhao & Peng Liu & Xiyu Gao & Guotai Huang & Xiuguang Yang & Yuan Ma & Zheyu Xie & Yunfeng Li, 2022. "Data-Mining-Based Real-Time Optimization of the Job Shop Scheduling Problem," Mathematics, MDPI, vol. 10(23), pages 1-30, December.
    3. Fabian Riquelme & Elizabeth Montero & Leslie Pérez-Cáceres & Nicolás Rojas-Morales, 2022. "A Track-Based Conference Scheduling Problem," Mathematics, MDPI, vol. 10(21), pages 1-25, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:3:p:329-:d:730539. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.