Quantum Annealing Implementation of Job-Shop Scheduling
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Solving Classical and Quantum Spin Glasses with Deep Boltzmann Quantum States
Deep Boltzmann Quantum States with natural-gradient optimization and annealing-like training match exact or best-known solutions for large infinite-range Ising spin glasses and solve job shop scheduling instances.
-
Mitigating the barren plateau problem in linear optics
A dual-valued phase shifter in linear optics creates variational cost landscapes with fewer local minima and outperforms prior linear-optical variational algorithms by mitigating barren plateaus.
-
Multi-tasking through quantum annealing
MTQA embeds multiple NP-hard problems such as minimum vertex cover and graph partitioning into spatially distinct regions on quantum hardware, delivering comparable solution quality to single-task annealing with reduc...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.