Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

Technical Summary: Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

Problem Definition
The paper addresses the Distributed Flexible Job Shop Scheduling Problem (DFJSP) within the context of the wool textile industry. Unlike traditional Job Shop Scheduling Problems (JSSP) or even standard Flexible Job Shop Scheduling Problems (FJSP), the DFJSP involves geographically dispersed production sites where a single production order (job) may require operations to be performed at different factories. This specific use case, derived from a real-world wool textile manufacturer, introduces a unique complexity: not only are production orders distributed across sites, but individual production steps (operations) of a single job can also be distributed. Consequently, the model must account for shipping times between machines located in different factories, in addition to standard processing times and machine constraints. The objective is to minimize the makespan (total completion time) while satisfying precedence constraints, ensuring operations start only once, and preventing machine overlaps. This problem is identified as NP-hard, and the inclusion of inter-factory shipping times significantly increases the combinatorial complexity.

Methodology
The authors formulate the extended DFJSP as a Quadratic Unconstrained Binary Optimization (QUBO) problem to be solved using a D-Wave Advantage System 4.1 quantum annealer (QPU).

1. QUBO Formulation: The problem is mapped to binary variables $x_{i,o,m,t}$, representing whether operation $o$ of job $i$ starts on machine $m$ at time $t$. The cost function $H(x)$ is constructed as a weighted sum of penalty functions for constraints (precedence, operation-once, no-overlap) and an objective function for minimizing makespan.
2. Variable Pruning: To manage the problem size within the physical limits of the QPU, the authors employ variable pruning. This involves calculating lower and upper bounds for operation start times based on minimum predecessor times and maximum makespan limits, thereby eliminating binary variables that correspond to invalid schedules.
3. Parameter Determination: A critical methodological step involves the systematic calculation of Lagrange parameters ($\alpha, \beta, \gamma$) for the penalty terms. Rather than relying on trial-and-error, the authors derive these weights mathematically based on the maximum possible makespan ($t_{max}$) of the specific problem instance. This ensures that the energy of any valid solution is lower than the energy of any invalid solution.
4. Embedding and Configuration: The logical QUBO variables are embedded onto the physical QPU topology using chains of qubits. The authors investigate the impact of "chain strength" (the coupling strength between qubits in a chain) on solution quality, determining optimal values by analyzing the trade-off between system energy and the percentage of broken chains.
5. Comparison: The quantum annealing (QA) results are benchmarked against Simulated Annealing (SA) using the D-Wave Ocean SDK. Both methods are tested on problem instances ranging from 50 to 250 variables (the maximum embeddable size on the tested QPU), with SA also tested on larger instances (up to 400 variables) to establish a baseline for computational scaling.

Key Contributions
The paper outlines three primary contributions:

1. Extended DFJSP Model with QA: The authors present the first known application of Quantum Annealing to an extended DFJSP where both production orders and individual production steps are distributed across factories, explicitly modeling inter-site shipping times.
2. Systematic Parameter Calculation: The paper details a method for determining Lagrange parameters and QPU configuration settings (specifically chain strength) based on the mathematical formulation of the problem, moving away from heuristic trial-and-error approaches.
3. Economic and Performance Assessment: The study evaluates the potential for a speed advantage in using QA for industry-specific distributed scheduling, comparing solution quality and calculation time against classical SA.

Results

• Solution Quality: For problem instances up to 150 variables, QA produced consistent, valid solutions (no broken constraints), though Simulated Annealing (SA) generally returned solutions with slightly lower energy (better optimality). As problem size increased to 200 and 250 variables, QA solutions began to exhibit broken constraints (1 and 2 violations, respectively), leading to higher energy values. This degradation is attributed to the increasing difficulty of embedding larger logical problems onto the physical QPU graph, resulting in longer chains and a higher rate of chain breaks.
• Makespan: QA solutions for most problem sizes fell within the lower half of the possible makespan range, indicating viable production schedules. However, for the 250-variable instance, the makespan was in the upper half of the range.
• Computational Time: SA demonstrated faster calculation times for small problem instances. However, SA's CPU time grew exponentially with problem size. In contrast, the QPU access time for QA increased at a decreasing (logarithmic) rate. While the current hardware limits QA to embedding problems up to 250 variables, the trend suggests that for larger instances (extrapolated beyond 300 variables), QA could potentially offer a significant speed advantage over SA.

Significance and Claims
The paper claims that while current quantum annealing hardware faces limitations in embedding large-scale problems and achieving global minima compared to classical heuristics for small instances, it holds significant potential for the wool textile industry's specific DFJSP challenges. The authors assert that QA offers a promising alternative for large-scale distributed scheduling due to its favorable scaling of computation time relative to problem size. They conclude that with future hardware improvements (more qubits, better connectivity, and stability), QA could provide a definitive speed-up advantage for problem instances exceeding approximately 300 variables, making it a viable tool for complex, real-world multi-factory production planning. The work emphasizes that the successful application of QA relies heavily on careful problem formulation, specifically the mathematical derivation of penalty weights and the optimization of embedding parameters.