The generalized flexible job shop scheduling problem. (October 2021) - Boyer, Vincent; Vallikavungal, Jobish; Cantú Rodríguez, Xavier; Salazar-Aguilar, M. Angélica
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.