2025/04/29 by Nicolás Casassus, Casassus, Nicolás, Margarita P. Castro +3 · 1 citation
Decision Sciences · Engineering · #FOS: Mathematics #Optimization and Control (math.OC) #Resource-Constrained Project Scheduling #Risk and Portfolio Optimization #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2504.20889
openalex publication_date 2025/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (2018) 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).