PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Annealing Implementation of Job-Shop Scheduling

Davide Venturelli, Dominic J. J. Marchand, Galo Rojo

arXiv:1506.08479v2quant-phmath.OC

TL;DR

The paper asks how quantum annealing can address the difficult JSP on limited hardware. It develops a time-indexed QUBO solver with preprocessing, embedding, and search strategies, then tests small instances against classical methods; the study reports exponential complexity growth with embedded Hamiltonian size and mixed hardware comparisons.

  • Problem

    The JSP is a hard practical scheduling problem, while current quantum-annealing hardware has limited qubit counts and benchmarking procedures remain under debate.

  • Method

    The paper formulates JSP decision problems as time-indexed QUBOs and combines variable pruning, graph embedding, parametrized ensembles, and optimized binary search.

  • Results

    The experiments on N = M ∈ {3, 4, 5, 6} show exponential complexity growth with embedded Hamiltonian size, while roughly half of instances were solved faster by D-Wave hardware than the MS algorithm.

  • Takeaways & Limitations

    The work demonstrates a hardware-aware end-to-end quantum-annealing JSP implementation and identifies preprocessing and search strategies for near-term experiments.

Abstract

from arXiv · show

A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.

I. I. INTRODUCTION

The paper formulates job-shop scheduling as a practically valuable constraint-satisfaction problem for quantum annealing, motivated by the difficulty of larger instances and limited quantum hardware.

  • Quantum annealing is investigated for small optimization problems that remain computationally challenging while current hardware has limited qubit counts.
  • The JSP allocates resources for ordered operation sequences subject to location and time constraints.
  • The paper provides compilation and running strategies for parametrized JSP instance ensembles and compares D-Wave Two results with classical exact solvers.
  • General-purpose solvers struggle with 10 x 10 instances, while some 20 x 15 instances remain unsolved to optimality and 20 x 20 instances are typically intractable.
  • The JSP convention uses jobs and machines indexed through lexicographically ordered operations, with each operation assigned a machine and execution time.
  • Each job uses a fraction θ of the machines, with θ = 0.5 meaning that every job uses 0.5M distinct machines.

B. Quantum annealing formulation

The formulation converts the JSP decision problem into a time-indexed QUBO whose penalties encode assignment, machine-capacity, and precedence constraints for quantum-annealing hardware.

  • B. Quantum annealing formulation: The QUBO is represented as a graph of binary variables, while the hardware solver is a connectivity-limited qubit graph requiring classical embedding.
  • B. Quantum annealing formulation: Embedding modifies the QUBO and introduces a distinction between logical QUBO values and the Ising energy seen by the optimizer.
  • B. Quantum annealing formulation: The paper solves the JSP decision version first, testing whether a schedule exists with makespan at most a specified timespan T.
  • II. II. QUBO PROBLEM FORMULATION: The time-indexed formulation assigns each operation binary variables for its possible discrete starting times.
  • A. Constraints: Penalty terms enforce that every operation starts once and only once.
  • A. Constraints: Quadratic constraints prevent simultaneous execution conflicts on each machine, including overlapping operations and prohibited simultaneous starts.
  • A. Constraints: Precedence penalties count violations between consecutive operations within each job.
  • A. Constraints: Positive penalty constants ensure infeasible schedules do not beat feasible ground states, whose decision-problem minimum is HT = 0.

B. Simple variable pruning

Simple variable pruning removes binary variables representing operation start times that violate bounds implied by within-job predecessor and successor work.

  • The formulation can prune many of its NMT binary variables by applying restrictions to the time index t.
  • Each operation receives an effective release time from preceding work and an upper bound from the timespan minus subsequent work.
  • Bits representing invalid starting times are fixed to zero and eliminated from the QUBO without changing any valid solution.

III. III. QUBO FORMULATION REFINEMENTS

The paper refines the basic QUBO through window shaving and a compromise between decision and optimization, while accounting for preprocessing cost in end-to-end runtime.

  • III. III. QUBO FORMULATION REFINEMENTS: The refinements extend the basic formulation with advanced execution-window reduction and a strategy bridging decision and full optimization versions.
  • A. Window shaving: Window shaving reduces the feasible execution windows of operations before QUBO solving.
  • A. Window shaving: Constraint-propagation techniques provide the general basis for reducing operation windows across time-indexed and disjunctive formulations.
  • A. Window shaving: Preprocessing time must be added to quantum-annealing runtime when reporting the whole algorithm’s time to solution.
  • A. Window shaving: The ICP procedure further prunes variables by analyzing one-machine subproblems rather than only one-job subproblems.
  • A. Window shaving: ICP has worst-case complexity O(N^2M^2T log(N)).

B. Timespan discrimination

The paper improves timespan discrimination and compilation by combining makespan-informed searches, embedding strategies, and parameter characterization for quantum annealing JSP instances.

  • Timespan discrimination: A single-call timespan-discrimination method separates valid schedules by makespan through added linear QUBO penalties.The energy spread must remain within the minimum logical QUBO gap ΔE = min{η, α, β}.
  • Makespan estimation: Pre-characterizing random JSP families provides makespan distributions that guide an informed binary search over candidate timespans.The distributions are approximated as normal using their average makespan and variance.
  • Compilation: Graph-minor embedding maps the QUBO graph onto the D-Wave Two’s Chimera architecture, using 257 qubits for 72 logical variables in one 5 x 5 JSP.Finding an optimal fewest-qubit embedding is NP-hard, so heuristic algorithms are used.
  • Makespan estimation: The mean and variance of optimal makespans are fitted using linear combinations of Np_min, Np_max, and the mean makespan.The reported coefficients include A_T = 0.67, B_T = 0.82, σ_0 = 0.7, A_σ = −0.03, B_σ = 0.43, and C_σ = 0.003.
  • Compilation: Embedding overhead scales quadratically with the number of binary variables and depends on the embedding algorithm and hardware connectivity.The study reports that available architectures admit JSP instances with total execution time around 20 time units.

V. V. RESULTS OF TEST RUNS AND DISCUSSION

The test runs benchmark the D-Wave Two on decision-form JSP instances against exhaustive classical solvers. Classical methods generally outperform the tested quantum hardware, although comparisons with MS show a promising signature for some instances.

  • Scope and optimization strategy: The study benchmarks only Hamiltonians with the optimal timespan T and proposes full optimization through adaptive binary search.The annealing success probability depends on the embedded Hamiltonian spectrum, environmental relaxation, noise, and annealing profile.
  • Experimental setup: The experiments run hundreds of JSP instances with N = M ∈ {3, 4, 5, 6}, θ ∈ {0.5, 1}, and P_p ∈ {[1, 1], [0, 2]}.Runtimes are reported using the most optimal tested J_F and repetitions targeting a 99% ground-state success probability.
  • Comparison with classical solvers: A classical algorithm on a modern single-core processor easily outperforms the D-Wave machine on the tested problem sizes.The study notes that these sizes are too small to clearly measure the classical algorithms’ asymptotic behavior.
  • Comparison with classical solvers: Algorithm B solves all tested full optimization problems within milliseconds, while D-Wave can take tenths of a second before binary-search overhead.The comparison involves different tasks: B performs full optimization, whereas D-Wave solves decision instances for specified timespans.
  • Comparison with MS: Roughly half of the instances are solved faster by D-Wave’s hardware than by the MS algorithm.The comparison uses a straightforward MS implementation that is not fully optimized.
  • Complexity patterns: D-Wave’s apparent complexity is sensitive mainly to total qubit count, whereas MS runtimes cluster by parametrized problem ensemble.This pattern is reported across the ensembles shown in Figure 4.

VI. VI. CONCLUSIONS

The paper presents a complete quantum-annealing JSP solver that combines problem formulation, pre-characterization, structured execution, and decoding. It also identifies classical preprocessing and tailored run strategies as useful components for improving performance.

  • VI. VI. CONCLUSIONS: The solver pipeline spans instance parametrization, ensemble pre-characterization, QUBO mapping, parameter setting, structured run strategies, and decoding.Figure 5 organizes the full optimization workflow into these stages.
  • VI. VI. CONCLUSIONS: Structured run strategies adapted to specific problems are presented as a previously unreported component of the approach.The paper discusses a prescription for these strategies in the appendix.
  • VI. VI. CONCLUSIONS: Majority voting within embedding components is the only decoding step required to recover error-free logical solutions.The time-indexed solutions can then be represented directly as Gantt charts.
  • VI. VI. CONCLUSIONS: Pre-characterization can both tune solver parameters and support classical preprocessing that prunes variables or reduces the search space.The paper identifies favorable polynomial-scaling classical algorithms as preprocessing tools.

Appendix A: JSP and QUBO formulation

The appendix compares penalty- and reward-based QUBO formulations for JSP constraints and examines their coefficient conditions and embedding consequences. It also notes hardware-precision disadvantages associated with the reward formulation.

  • 1. Penalties versus rewards formulation: The appendix introduces an alternative reward-based formulation that encodes precedence satisfaction as a reward rather than a penalty.This replaces the penalty term +ηh1 with a reward term −η′h′1.
  • 1. Penalties versus rewards formulation: The reward equals η′ times the number of satisfied precedence constraints, while a feasible schedule has energy −η′(kN −N).Feasibility corresponds to satisfying all constraints.
  • 1. Penalties versus rewards formulation: Allowing equality in the reward formulation gives h′1 more quadratic terms than h1, producing a more connected QUBO graph that is harder to embed.This disadvantage persists regardless of variable pruning.
  • 1. Penalties versus rewards formulation: The appendix also identifies another disadvantage when selecting η′, α, and β in the reward-based Hamiltonian.The supplied passage introduces this issue without fully stating its subsequent derivation.
  • 1. Penalties versus rewards formulation: The reward formulation must prevent constraint-breaking penalties from being outweighed by rewards, so its coefficients are constrained by an energy bound.The condition ensures that no infeasible solution has energy below the feasible-solution bound.
  • 1. Penalties versus rewards formulation: The penalty formulation requires η, α, and β to be greater than 0, whereas the reward formulation requires an equivalent coefficient condition.The appendix states that the associated bounds are summarized by a lemma.
  • 1. Penalties versus rewards formulation: The coefficient bounds are tight in examples presented by the authors.This indicates that the stated inequalities cannot generally be relaxed.
  • 1. Penalties versus rewards formulation: β/η′ must be greater than or equal to 3, creating a disadvantage under the limited precision of current hardware.The penalty-based formulation can instead use equal penalty coefficients and non-zero couplers in HT.

2. Timespan discrimination

Timespan discrimination assigns energy sectors to valid schedules with different makespans, providing information about the optimum without adding auxiliary makespan variables. The implementation also depends on embedding choices and hardware-aware parameter setting.

  • 2. Timespan discrimination: Timespan discrimination trades off information per solver call against the precision and efficiency required to identify the optimal makespan.It uses solution energies to distinguish schedules by makespan.
  • 2. Timespan discrimination: The scheme breaks ground-state degeneracy by assigning different energy sectors to different makespans while keeping them within the logical QUBO gap ΔE = min{η, α, β}.The resulting energy structure also changes the gap seen by the embedded Ising model.
  • 2. Timespan discrimination: Local fields on variables for each job’s last operation encode makespan information without introducing additional auxiliary variables and constraints.Because makespan equals the completion time of a last operation in valid schedules, these fields can penalize selected larger makespans.
  • 2. Timespan discrimination: The objective is to assign distinct T-dependent energy ranges to valid schedules with makespans in [T −K, T].The construction further subdivides each sector according to the number of operations that can complete.
  • 2. Timespan discrimination: The energy-resolution requirement scales with the logical gap and the number of machines and discriminated makespans.The appendix relates this resolution to ΔE, M, and K, with ϵ the minimum resolvable logical energy.
  • 2. Timespan discrimination: The full optimization solver uses the decision formulation together with a binary search over feasible timespans.This strategy is described as an implementation of optimization based on repeated decision problems.
  • 2. Timespan discrimination: Embedding maps each logical variable to a connected hardware subgraph whose inter-subgraph edges represent logical couplings.This graph-minor mapping is required by the locality of programmable interactions on quantum annealers.
  • 2. Timespan discrimination: A reusable embedding library could reduce embedding computation to lookup, but available embeddings might not be fully optimized for each instance.Hardware parameter ranges also require rescaling the logical fields and couplers.

2. Quantum annealing optimization solver

The solver identifies JSP instances by family and constructs annealer query ensembles using pre-characterized success and annealing parameters. It distinguishes invalid schedules, valid schedules below the discrimination threshold, and valid schedules that may reveal the optimum.

  • Instance families are pre-characterized by N, M, θ, execution-time distributions, optimal-makespan distributions, and solver parameters.Queries are triples specifying annealing time, repeated annealings, and the embedded Hamiltonian.
  • The query ensemble assumes sufficient statistics and generalized adiabaticity so measured parameters can support ground-state sampling.The paper notes that these assumptions require family-specific measurements of R⋆ and t⋆A.
  • The assumptions could not be experimentally verified on D-Wave Two because the expected optimal annealing time was below the device’s minimum programmable value.The authors also considered the machine time required for large-scale testing too onerous for this initial study.
  • R⋆=500 000 and t⋆A=min(tA)=20 µs were used for the reported results.
  • The annealer can return invalid schedules, valid schedules not discriminated by the timespan procedure, or valid schedules that may correspond to a global minimum.These cases are represented by the configuration sets E, V, and S, respectively.

3. Search strategy

The solver uses pre-characterized makespan distributions to guide a binary search over feasible timespans, while bounds and solver limitations determine the search interval. This reduces the number of annealer calls relative to linear search.

  • The guided search models optimal makespans with a fitted normal distribution truncated by instance-dependent bounds Tmax and Tmin.
  • Each query bisects (Tmin, Tmax] so the probability of finding the optimum on either side is approximately equal.The split point is selected by solving the distribution-based equation and rounding to the nearest integer.
  • Search updates Tmin when no schedule is found and updates Tmax when a valid schedule satisfies the lower-timespan condition.A third condition can indicate that the optimal makespan has been found when K>0.
  • Fewer than three expected annealer calls are required for experimentally testable D-Wave Two instances, compared with twice that without pre-characterization.For larger instances, the query-set size scales logarithmically under the stated variance-scaling condition.
  • The search interval can use job and machine lower bounds, stronger ICP bounds, classical upper bounds, or practical embedding limits.If the solver fails below an embedding-based upper limit, it must report failure or switch to a classical approach.

Appendix C: Classical algorithms

The classical preprocessing pipeline reduces JSP processing windows before quantum solving by propagating precedence and machine-order constraints. Its shaving loop repeatedly updates machine-specific and job-specific bounds until no further variables can be removed.

  • Classical algorithms are used both for benchmarking and as preprocessing, including variable pruning to reduce qubit requirements.
  • Variable pruning: Simple variable pruning assigns each operation a head ri and tail qi, restricting its start-time window to [ri, T −pi−qi].The head is the total duration of preceding operations, while the tail is the total duration of following operations.
  • Variable pruning: Machine-specific constraints can force an operation order when ra+pa+pb+qb>T, enabling head and tail updates through immediate selections.These updates further reduce processing windows beyond job precedence alone.
  • Variable pruning: Ascendant-set updates strengthen machine-based pruning, after which updated heads and tails are propagated along each job’s precedence chain.The process repeats until no additional ascendant-set updates are available.
  • Shaving algorithm: The shaving algorithm alternates machine updates with window propagation until convergence.UpdateMachine runs in O(N log(N)) and PropagateWindows in O(NM).
  • Shaving algorithm: The stated overall complexity of the shaving procedure is O(N^2M^2T log(N)).

2. Classical algorithm implementation

The study compares quantum-annealing results with established classical JSP methods and benchmarks those classical methods on a conventional processor.

  • Brucker et al.’s branch-and-bound method is used because of its state-of-the-art status on smaller JSP instances and competitive larger-instance performance.The implementation was interfaced with the authors’ code and timed without optimization.
  • The Martin–Shmoys time-based approach was implemented using efficient O(n log(n)) head-and-tail adjustments and a simple branch-and-bound strategy.The paper notes that no publicly available standard code was found and that multiple variants exist.
  • Classical-method benchmarking used an Intel Core i7-930 processor clocked at 2.8 GHz.
Loading 1506.08479v2…