A competitive constraint programming approach for the group shop scheduling problem

Francisco Yuraszeck, Gonzalo Mejia, Dario Canut-De-Bon

Producción científica: Contribución a una revistaArtículo de la conferenciarevisión exhaustiva

1 Cita (Scopus)

Resumen

In this paper, we propose a competitive Constraint Programming (CP) approach to solve the Group Shop Scheduling Problem (GSSP) under the makespan minimization criteria. Our contribution is two-fold: we provide a flexible mathematical formulation to solve the GSSP that can be used without change to solve other closed-related scheduling problems such as the Open Shop Scheduling Problem (OSSP), Job Shop Scheduling Problem (JSSP), and Mixed Shop Scheduling Problem (MSSP); and we improve several lower bounds and upper bounds from 130 classical GSSP instances from the literature. We evaluate our approach by comparing the performance with competitive methods mainly based on metaheuristics, where we were able to prove optimality in more than 85% of the instances in competitive running time, with a relative percentage deviation lower than 3% on average. In contrast to metaheuristics approaches, our CP method does not require calibrations of multiple parameters, several replicates for each instance, and complex computational coding to be competitive in both, solution quality and computational running times.

Idioma originalInglés
Páginas (desde-hasta)946-951
Número de páginas6
PublicaciónProcedia Computer Science
Volumen220
DOI
EstadoPublicada - 2023
Evento14th International Conference on Ambient Systems, Networks and Technologies Networks, ANT 2023 and The 6th International Conference on Emerging Data and Industry 4.0, EDI40 2023 - Leuven, Bélgica
Duración: 15 mar. 202317 mar. 2023

Áreas temáticas de ASJC Scopus

  • Ciencia de la Computación General

Huella

Profundice en los temas de investigación de 'A competitive constraint programming approach for the group shop scheduling problem'. En conjunto forman una huella única.

Citar esto