Quantum Annealing Implementation of Job-Shop Scheduling

Abstract

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.

15 pages, 6 figure, presented at Constraint Satisfaction techniques for planning and Scheduling (COPLAS) Workshop of the 26th International Conference on Automated Planning and Scheduling 2016

Cited by in corpus (48)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Application of Quantum Annealing to Nurse Scheduling Problem
• Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
• Traffic Signal Optimization on a Square Lattice with Quantum Annealing
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
• Flight Gate Assignment with a Quantum Annealer
• Quantum Shuttle: Traffic Navigation with Quantum Computing
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
• Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer
• An energetic perspective on rapid quenches in quantum annealing
• Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Degeneracy, degree, and heavy tails in quantum annealing
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• Evaluating Ising Processing Units with Integer Programming
• A Novel Graph-based Approach for Determining Molecular Similarity
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem
• Quantum Annealing Approach for the Optimal Real-time Traffic Control using QUBO
• Search range in experimental quantum annealing
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Mean-field Coherent Ising Machines with artificial Zeeman terms
• Quantum-inspired optimization for wavelength assignment
• A QUBO formulation for top-$\tau$ eigencentrality nodes
• Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
• Petri Net Modeling for Ising Model Formulation in Quantum Annealing
• Quantum-assisted finite-element design optimization
• Combinatorial Optimization by Decomposition on Hybrid CPU--non-CPU Solver Architectures
• Quantum-assisted cluster analysis
• Quantum annealing with pairs of ${}^2\Sigma$ molecules as qubits
• Quantum and quantum-inspired optimization for solving the minimum bin packing problem
• Toward a standardized methodology for constructing quantum computing use cases
• Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach
• Quantum annealer accelerates the variational quantum eigensolver in a triple-hybrid algorithm
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing---Abridged Version
• Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer
• A QUBO Model for Gaussian Process Variance Reduction
• Assessment of image generation by quantum annealer