Scheduling an Assembly Problem with Precedences and Resource Constraints
Dario Bezzi(1), Andrea Corsini(2) and Mauro Dell’Amico(2)
(1)Department of Management, Information and Production Engineering, University of Bergamo
(2)DISMI, University of Modena and Reggio Emilia, 42100 Reggio Emilia, Italy.
Abstract
In this work, we consider a real-life scheduling problem involving the production of off-road vehicles using a three-level assembly process, subject to precedence, machines, and resource constraints. This problem has multiple characteristics shared with others, including parallel machines and an identical precedence sequence in one assembly level. However, it also comprises less investigated aspects such as a specific job precedence structure resulting in a directed rooted in-tree and a global resource constraint limiting the number of simultaneously active machines. To the best of our knowledge, no prior publications have ever addressed the interplay of all these characteristics. Therefore, we present a mathematical formulation of the problem and introduce a lower-bound procedure for extensively benchmarking algorithms. Inspired by related scheduling problems, we propose constructive and job sequencing heuristics and develop CORE, a novel metaheuristic tailored to leverage the problem structure. All these algorithms are evaluated on two benchmark sets reflecting industrial use cases, various shop floor configurations, and eight real-life scenarios. Our results reveal the general effectiveness of job sequencing approaches and demonstrate the overall superiority of the CORE metaheuristic.
----------