Heuristics for Scheduling an Assembly Problem with Lobster Precedences and Resource Constraint

• DOI: 10.2139/ssrn.4472425
• Publication Date: 2023-06-07T13:19:32Z
• Authors: Dario Bezzi; Andrea Corsini; Mauro Dell'A...
• Keywords: Heuristics; Resource constraints

In this work, we consider a scheduling problem faced by company involved in the production of off-road vehicles using three-level assembly process, subject to precedence, machines, and resource constraints. This has multiple characteristics shared with other problems, including specific precedence structure resulting Lobster graph, constraint limiting number simultaneously active an identical sequence present all jobs. To best our knowledge, no prior publications have ever addressed interplay these characteristics. We mathematical formulation adapt heuristic algorithms from related problems. also introduce two-step decomposition method tailored leverage structure, along simple pre-processing select most suitable algorithm based on input instance. extensively evaluate proposals two benchmark sets reflecting industrial use cases, various shop floor configurations, eight real-life scenarios. Our results demonstrate effectiveness highlight superiority compared proposals. Lastly, analysis reveals general importance correctly handling jobs, although certain conditions constraints may reduce its relevance.