The generalized flexible job shop scheduling problem. (October 2021)

• Record Type: Journal Article
• Authors: Boyer, Vincent; Vallikavungal, Jobish; Cantú Rodríguez, Xavier; Salazar-Aguilar, M. Angélica
• Is Part Of: Computers & industrial engineering. Volume 160(2021)
• Publication Date: 2021-10
• Subjects: Flexible job-shop scheduling problem -- Constraint programming -- Time lag constraints -- Machine capacity -- Holding times; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2021.107542
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The Generalized Flexible Job-Shop Scheduling Problem is introduced. Maximum time lags constraints and machine capacity are considered. A constraint programming model and a mixed-integer programming model are proposed. A Greedy Randomized Adaptive Search Procedure is used for solving large instances. A benchmark of instances is proposed to promote future research. Abstract: In this work, we introduce a generalized flexible job-shop scheduling problem in which, besides the classical constraints of the flexible job shop scheduling problem other hard constraints such as machine capacity, time lags, holding times, and sequence-dependent setup times are taken into account. This problem is inspired by a real situation observed in a seamless rolled ring manufacturer. We propose a mixed integer linear programming (MILP) and a constraint programming (CP) models to represent the problem. Additionally, we develop a metaheuristic based on a Greedy Randomized Adaptive Search Procedure (GRASP) able to tackle efficiently large instances of the problem. The results show that CP outperforms the MILP and the proposed GRASP outperforms the CP when solving instances with more than 100 jobs.