A Decision Diagram Approach for the Parallel Machine Scheduling Problem with Chance Constraints

Nicolás Casassus, Margarita Castro, Gustavo Angulo · 2025

Read A Decision Diagram Approach for the Parallel Machine Scheduling Problem with Chance Constraints by Nicolás Casassus, Margarita Castro, Gustavo Angulo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20889.txt.

Introduction

Nicolás Casassus, Margarita Castro, and Gustavo Angulo split a hard scheduling puzzle into two halves in a 2025 paper. Factories must assign jobs to parallel machines when job lengths are unsure. Each machine must finish on time with a set level of trust, not just on average. The team lets a master step hand jobs to machines, then checks each machine's plan on its own.

The check step uses tree-like diagrams that pack all valid orders for one machine. Two versions of the diagram are offered, one with a straight cost count and one with a bent count that keeps the diagram small. Failed checks yield cuts that steer the master away from bad assignments. Across 405 test cases, the best diagram method solved 55 more cases than the best classic method, and its leftover gaps ran far smaller.

Catalog record

CREATORNicolás Casassus, Margarita Castro, Gustavo Angulo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20889

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Decision Diagram Approach for the Parallel Machine Scheduling Problem with Chance Constraints Nicolás Casassus, Margarita Castro, Gustavo Angulo Abstract The Chance-Constrained Parallel Machine Scheduling Problem (CC-PMSP) assigns jobs with uncertain processing times to machines, ensuring that each machine’s availability constraints are met with a certain probability. We present a decomposition approach where the master problem assigns jobs to machines, and the subproblems schedule the jobs on each machine while verifying the solution’s feasibility under the chance constraint. We propose two different Decision Diagram (DD) formulations to solve the subproblems and generate cuts. The first formulation employs DDs with a linear cost function, while the second uses a non-linear cost function to reduce the diagram’s size. We show how to generate no-good and irreducible infeasible subsystem (IIS) cuts based on our DDs. Additionally, we extend the cuts proposed by Lozano & Smith lozano2018 to solve two-stage stochastic programming models. Our DD-based methodology outperforms traditional integer programming (IP) models designed to solve the CC-PMSP in several instances. Specifically, our best DD-based approach solves 55 more instances than the best IP alternative (from a total of 405) and typically achieves smaller gaps (50% vs. 120% gap on average). ∎ MSC 90B36 90C15 90C10 1 INTRODUCTION Scheduling problems represent a fundamental area within operational research, with numerous practical applications across economic and industrial sectors pinedo2023 . These problems focus on efficiently allocating limited resources over time to execute a set of tasks while optimizing one or more objectives. They naturally arise in various contexts, such as manufacturing environments where jobs must be assigned to machines and their processing order determined, hospitals scheduling surgeries and medical interventions, airports establishing takeoff and landing sequences, and logistics centers coordinating loading, unloading, and distribution processes, to name a few baker2019 ; blazewicz2019 ; brucker2006 ; cardoen2010 ; rinnooy1976 ; lenstra1977 ; pinedo2023 . Efficient scheduling of these activities can significantly contribute to cost reduction, optimize the use of limited resources, reduce waiting times, and improve service quality. Among the various scheduling problems, the Parallel Machine Scheduling Problem (PMSP) involves scheduling a set of jobs on a set of machines, considering that each job has an execution time and a setup time between jobs baker2019 ; brucker2006 ; pinedo2023 . Multiple objective functions can be used to optimize the problem, such as minimizing job execution time, minimizing job tardiness, and minimizing setup times. This problem, classified as NP-hard, has been extensively studied in scientific literature due to its combinatorial complexity and practical relevance baker2019 ; brucker2006 ; lenstra1977 . However, traditional deterministic models assume perfect knowledge of processing and setup times, an assumption that is rarely met in real-life applications. In practice, execution times are subject to variations caused by multiple factors, including equipment breakdowns, changes in resource availability, and variability in human performance, among others. This uncertainty can significantly compromise the feasibility and quality of solutions obtained through deterministic approaches. This research focuses on the Chance-Constrained Parallel Machine Scheduling Problem (CC-PMSP), a version of PMSP that incorporates uncertainty in job execution and setup times. The problem seeks to assign jobs to different machines, guaranteeing with a certain probability that all assigned jobs can be completed within the available machine time. Given the computational challenges of solving the CC-PMSP, we propose a decomposition approach that divides the problem into two levels. The master problem handles job assignment to machines, determining which jobs will be processed by each machine. The subproblems, one for each machine and scenario, determine the optimal processing sequence of the assigned jobs and verify the feasibility of the solution under the chance constraint. One of the main drawbacks of such decomposition is that the subproblems correspond to NP-hard problems (i.e., sequence problems with setup times). This work proposes Decision Diagrams (DDs), which are graphical structures employed in optimization to represent the feasibility set of discrete optimization problems bergman2016decision , to solve these subproblems, aiming to leverage their high reusability across different subproblems. These DDs have been utilized in numerous applications, particularly in scheduling and sequencing problems, with high success cire2013 . Our decomposition encodes the subproblem using a DD and generates cuts from it to guide the master problem toward optimal solutions. We propose two different DD formulations to address this challenge. The first one, called DD-LastJob (DD-LJ), employs a linear cost function to evaluate paths in the diagram. The second, called DD-JobSet (DD-JS), employs a non-linear cost function that significantly reduces the diagram’s size. Additionally, we develop mechanisms to generate No-Good and Irreducible Infeasible Set (IIS) cuts based on our DDs, which efficiently eliminate infeasible solutions from the search space. In summary, the main contributions of this work are the following: 1. We present a novel variant of the CC-PMSP and propose a decomposition methodology based on DDs. 2. We propose two DD formulations (DD-LJ and DD-JS) to efficiently solve the subproblems and present novel algorithms to generate No-Good and IIS cuts based on such DDs. 3. We adapt the methodology proposed by Lozano & Smith lozano2018 for two-stage stochastic programming problems to the CC-PMSP, which can be easily extended to other chance-constrained problems. 4. We provide extensive numerical experiments and empirical evidence demonstrating that the proposed DD-based methodology outperforms Integer Programming (IP) alternatives. The remainder of the paper is organized as follows. Section 2 establishes our research foundation with a literature review, followed by the description and formalization of the CC-PMSP in Section 3 . Section 4 introduces our decomposition strategy, while Section 5 reviews DDs and presents the DD-LJ and DD-JS formulations for CC-PMSP subproblems. Section 6 details algorithms for generating No-Good and IIS cuts based on these DDs, followed by our computational experiments and results analysis in Section 7 . Finally, Section 8 presents our findings, draws conclusions, and outlines directions for future research. 2 Literature Review This research studies chance-constrained programming (CCP) problems with binary variables. Specifically, we consider problems with the following structure \displaystyle\max \displaystyle\mathbf{u}^{\top}\mathbf{x} (1a) s.t. \displaystyle\mathbf{A}\mathbf{x} \displaystyle\leq\mathbf{b} (1b) \displaystyle\mathbb{P}(\exists\mathbf{y}\in\mathcal{Y}(\mathbf{x},\omega)) \displaystyle\geq 1-\varepsilon (1c) \displaystyle\mathbf{x} \displaystyle\in\{0,1\}^{n}, (1d) where the objective function ( 1a ) seeks to maximize the sum of utilities associated with the solution, subject to deterministic linear constraints ( 1b ), a chance constraint ( 1c ) ensuring feasibility with probability at least 1-\varepsilon ( \varepsilon\in(0,1) ) with respect to realizations \omega\in\Omega of random parameters, and binary constraints ( 1d ). We now review the literature related to CCP problems and DDs. 2.1 Chance-Constrained Programming Problems CCP problems have been studied since at least the work of prekopa1970 , but remain computationally challenging for two main reasons: (i) the solution space is not convex, and (ii) evaluating the feasibility of a solution requires integrating multi-dimensional functions luedtke2014 . Traditional methods only achieve good solutions in special cases. For example, if the chance constraint is a linear inequality where the random coefficients follow a normal distribution, it is possible to reformulate the problem as a deterministic non-linear convex problem if \varepsilon<0.5 calafiore2006 . Another example is for problems with \mathcal{Y}(\mathbf{x},\omega)=\{\mathbf{y}:T\mathbf{x}+W\mathbf{y}\geq h(\omega)\} , where h(\omega) follows a discrete finite distribution, which can be solved with a IP formulation kucukyavuz2012 . Luedtke luedtke2014 proposed a formulation to exactly solve problems with chance constraints, considering discrete distributions with finite support and

Read the complete text