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

Source: [Solving Parallel Machine Scheduling With Precedences and Cumulative Resource Constraints With Calendars](<https://www.sota2.com/research/paper/6940e791456146936284f740>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-12-17T05:03:45.767Z

Authors: Christoph Einspieler, Matthias Horn, Marie-Louise Lackner, Patrick Malik, Nysret Musliu, Felix Winter

Published: 2025-12-05T12:35:44.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Job Scheduling on Randomly generated scheduling instances up to 20 jobs](<https://www.sota2.com/research/sota/job-scheduling-on-randomly-generated-scheduling-instances-up-to-20-jobs.md>): Job Scheduling; Randomly generated scheduling instances up to 20 jobs; Average Makespan: 465.3.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2512.11864>)

[PDF](<https://arxiv.org/pdf/2512.11864.pdf>)
