Operations Research 2025
Abstract Submission

2342. A Neural Decoder for Scheduling Problems with Complex Side Constraints

Invited abstract in session FA-3: Algorithms and Applications, stream Project Management and Scheduling.

Friday, 8:45-10:15
Room: H5

Authors (first author is the speaker)

1. Maziyar Khadivi
Advanced Control & Intelligent Systems Lab, University of Victoria
2. Kevin Tierney
Business Decisions and Analytics, University of Vienna
3. Homayoun Najjaran
Mechanical Engineering, University of Victoria

Abstract

Neural combinatorial optimization (NCO) has emerged as a promising approach for addressing NP-hard combinatorial optimization problems, such as routing, scheduling, and graph-based optimization. However, existing NCO methods struggle with real-world applications, particularly when dealing with complex side constraints that are difficult to represent compactly and when a masking mechanism is insufficient to enforce feasibility. The existing literature has yet to adequately address scenarios where deep neural networks (DNNs) must explicitly manage intricate operational constraints essential for solution feasibility and practical industrial implementations. To bridge this gap, we introduce a hybrid method that integrates a DNN with a heuristic decoder. Our DNN learns to optimally sequence a set of tasks, which are passed to the decoder, constructing the solution subject to the problem constraints. We validate the proposed method on the parallel machines scheduling problem with additional resources (PMSPR), a common problem in the manufacturing and service sectors, requiring the optimal assignment of jobs to machines supervised by limited additional resources. Derived from an industrial case study of a food processing plant, our PMSPR formulation accounts for operational constraints such as job release times, due dates, and machine eligibility. Compared to conventional operations research methods, including (meta)heuristics and exact solvers, our proposed approach helps reduce solving time. It enables real-time optimization in stochastic environments by rapidly inferring multiple scenarios to support ad hoc decisions under operational uncertainty.

Keywords

Status: accepted

Back to the list of papers