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

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