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

• URL: http://arxiv.org/abs/2512.11864v1
• Date: Fri, 05 Dec 2025 12:35:44 GMT
• Title: Solving Parallel Machine Scheduling With Precedences and Cumulative Resource Constraints With Calendars
• Authors: Christoph Einspieler, Matthias Horn, Marie-Louise Lackner, Patrick Malik, Nysret Musliu, Felix Winter,
• Abstract summary: We introduce a novel variant of parallel machine scheduling with job precedences and calendar-based cumulative resource constraints.<n>We propose a construction as well as a tailored metaheuristic using local search to efficiently tackle large-scale problem instances.
• Score: 2.863183011550039
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Quantum-classical hybrid algorithm using quantum annealing for multi-objective job shop scheduling [0.5872014229110214]
  Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition.<n>We develop a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling.<n> Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods.
  arXiv  Detail & Related papers  (2025-11-05T07:39:09Z)
• A Production Scheduling Framework for Reinforcement Learning Under Real-World Constraints [0.0]
  Real-world production environments introduce additional complexities that cause traditional scheduling approaches to be less effective.<n>Reinforcement learning (RL) holds potential in addressing these challenges, as it allows agents to learn adaptive scheduling strategies.<n>We propose a modular framework that extends classical JSSP formulations by incorporating key real-world constraints.<n>JobShopLab is an open-source tool for both research and industrial applications.
  arXiv  Detail & Related papers  (2025-06-16T14:50:26Z)
• Efficient LLM Collaboration via Planning [56.081879390960204]
  Small and large models take turns acting as planner and executor, exchanging plans in a multi-stage cascade to collaboratively solve tasks.<n>We demonstrate that COPE achieves performance comparable to large proprietary models, while drastically reducing the inference API cost.
  arXiv  Detail & Related papers  (2025-06-13T08:35:50Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  We present Recipe2Plan, a novel benchmark framework based on real-world cooking scenarios.<n>Unlike conventional benchmarks, Recipe2Plan challenges agents to optimize cooking time through parallel task execution.
  arXiv  Detail & Related papers  (2025-03-04T03:27:02Z)
• A mathematical model for simultaneous personnel shift planning and unrelated parallel machine scheduling [3.0477617036157136]
  This paper addresses a production scheduling problem derived from an industrial use case. It focuses on unrelated parallel machine scheduling with the personnel availability constraint. It assumes shared personnel among machines, with one personnel required per machine for setup and supervision during job processing.
  arXiv  Detail & Related papers  (2024-02-24T01:04:04Z)
• Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning [73.19312285906891]
  In flexible job shop scheduling problem (FJSP), operations can be processed on multiple machines, leading to intricate relationships between operations and machines. Recent works have employed deep reinforcement learning (DRL) to learn priority dispatching rules (PDRs) for solving FJSP. This paper presents a novel end-to-end learning framework that weds the merits of self-attention models for deep feature extraction and DRL for scalable decision-making.
  arXiv  Detail & Related papers  (2023-05-09T01:35:48Z)
• A Memetic Algorithm with Reinforcement Learning for Sociotechnical Production Scheduling [0.0]
  This article presents a memetic algorithm with applying deep reinforcement learning (DRL) to flexible job shop scheduling problems (DRC-FJSSP) From research projects in industry, we recognize the need to consider flexible machines, flexible human workers, worker capabilities, setup and processing operations, material arrival times, complex job paths with parallel tasks for bill of material manufacturing, sequence-dependent setup times and (partially) automated tasks in human-machine-collaboration.
  arXiv  Detail & Related papers  (2022-12-21T11:24:32Z)
• Concepts and Algorithms for Agent-based Decentralized and Integrated Scheduling of Production and Auxiliary Processes [78.120734120667]
  This paper describes an agent-based decentralized and integrated scheduling approach. Part of the requirements is to develop a linearly scaling communication architecture. The approach is explained using an example based on industrial requirements.
  arXiv  Detail & Related papers  (2022-05-06T18:44:29Z)
• A Research Agenda for Artificial Intelligence in the Field of Flexible Production Systems [53.47496941841855]
  Production companies face problems when it comes to quickly adapting their production control to fluctuating demands or changing requirements. Control approaches aiming to encapsulate production functions in the sense of services have shown to be promising in order to increase flexibility of Cyber-Physical Production Systems. But an existing challenge of such approaches is finding production plans based on provided functionalities for a set of requirements, especially when there is no direct (i.e., syntactic) match between demanded and provided functions.
  arXiv  Detail & Related papers  (2021-12-31T14:38:31Z)
• Towards Standardizing Reinforcement Learning Approaches for Stochastic Production Scheduling [77.34726150561087]
  reinforcement learning can be used to solve scheduling problems. Existing studies rely on (sometimes) complex simulations for which the code is unavailable. There is a vast array of RL designs to choose from. standardization of model descriptions - both production setup and RL design - and validation scheme are a prerequisite.
  arXiv  Detail & Related papers  (2021-04-16T16:07:10Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Metaheuristics for the Online Printing Shop Scheduling Problem [0.0]
  This real scheduling problem, that emerged in the nowadays printing industry, corresponds to a flexible job shop scheduling problem with sequencing flexibility. A local search strategy and metaheuristic approaches for the problem are proposed and evaluated. Numerical experiments with classical instances of the flexible job shop scheduling problem show that the introduced methods are also competitive when applied to this particular case.
  arXiv  Detail & Related papers  (2020-06-22T15:38:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.