Solving Parallel Machine Scheduling With Precedences and Cumulative Resource Constraints With Calendars

Abstract

The task of finding efficient production schedules for parallel machines is a challenge that arises in most industrial manufacturing domains. There is a large potential to minimize production costs through automated scheduling techniques, due to the large-scale requirements of modern factories. In the past, solution approaches have been studied for many machine scheduling variations, where even basic variants have been shown to be NP-hard. However, in today's real-life production environments, additional complex precedence constraints and resource restrictions with calendars arise that must be fulfilled. These additional constraints cannot be tackled efficiently by existing solution techniques. Thus, there is a strong need to develop and analyze automated methods that can solve such real-life parallel machine scheduling scenarios. In this work, we introduce a novel variant of parallel machine scheduling with job precedences and calendar-based cumulative resource constraints that arises in real-life industrial use cases. A constraint modeling approach is proposed as an exact solution method for small scheduling scenarios together with state-of-the-art constraint-solving technology. Further, we propose a construction heuristic as well as a tailored metaheuristic using local search to efficiently tackle large-scale problem instances. This metaheuristic approach has been deployed and is currently being used in an industrial setting.