Multi-objective Quantum Annealing approach for solving flexible job shop
scheduling in manufacturing
- URL: http://arxiv.org/abs/2311.09637v1
- Date: Thu, 16 Nov 2023 07:45:57 GMT
- Title: Multi-objective Quantum Annealing approach for solving flexible job shop
scheduling in manufacturing
- Authors: Philipp Schworm, Xiangquian Wu, Matthias Klar, Moritz Glatt, Jan C.
Aurich
- Abstract summary: This paper introduces Quantum Annealing-based solving algorithm (QASA) to address Flexible Job Shop Scheduling problem.
Experiments on benchmark problems show QASA, combining tabu search, simulated annealing, and Quantum Annealing, outperforms a classical solving algorithm (CSA) in solution quality.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Flexible Job Shop Scheduling (FJSSP) is a complex optimization problem
crucial for real-world process scheduling in manufacturing. Efficiently solving
such problems is vital for maintaining competitiveness. This paper introduces
Quantum Annealing-based solving algorithm (QASA) to address FJSSP, utilizing
quantum annealing and classical techniques. QASA optimizes multi-criterial
FJSSP considering makespan, total workload, and job priority concurrently. It
employs Hamiltonian formulation with Lagrange parameters to integrate
constraints and objectives, allowing objective prioritization through weight
assignment. To manage computational complexity, large instances are decomposed
into subproblems, and a decision logic based on bottleneck factors is used.
Experiments on benchmark problems show QASA, combining tabu search, simulated
annealing, and Quantum Annealing, outperforms a classical solving algorithm
(CSA) in solution quality (set coverage and hypervolume ratio metrics).
Computational efficiency analysis indicates QASA achieves superior Pareto
solutions with a reasonable increase in computation time compared to CSA.
Related papers
- Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances [0.0]
This paper establishes a new protocol to generate graph instances with their associated near-optimal minor-embedding mappings to D-Wave Quantum Annealers.
We use this method to benchmark QA on large instances of unconstrained and constrained optimization problems and compare the performance of the QPU with efficient classical solvers.
arXiv Detail & Related papers (2024-05-02T15:19:39Z) - Assessing Quantum Computing Performance for Energy Optimization in a
Prosumer Community [1.072460284847973]
"Prosumer problem" is the problem of scheduling the household loads on the basis of the user needs, the electricity prices, and the availability of local renewable energy.
Quantum computers can offer a significant breakthrough in treating this problem thanks to the intrinsic parallel nature of quantum operations.
We report on an extensive set of experiments, on simulators and real quantum hardware, for different problem sizes.
arXiv Detail & Related papers (2023-11-17T15:48:51Z) - Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
We introduce the Pointer Q-Network (PQN), a hybrid neural architecture that integrates model-free Q-value policy approximation with Pointer Networks (Ptr-Nets)
Our empirical results demonstrate the efficacy of this approach, also testing the model in unstable environments.
arXiv Detail & Related papers (2023-11-05T12:03:58Z) - Federated Conditional Stochastic Optimization [110.513884892319]
Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML.
This paper proposes algorithms for distributed federated learning.
arXiv Detail & Related papers (2023-10-04T01:47:37Z) - Multi-Objective Optimization and Network Routing with Near-Term Quantum
Computers [0.2150989251218736]
We develop a scheme with which near-term quantum computers can be applied to solve multi-objective optimization problems.
We focus on an implementation based on the quantum approximate optimization algorithm (QAOA)
arXiv Detail & Related papers (2023-08-16T09:22:01Z) - Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing
Problem [0.0]
We discuss the Capacitated Vehicle Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP)
Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically.
Quantum computing may offer a way to improve the time to solution.
arXiv Detail & Related papers (2023-04-19T13:03:50Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace.
One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz.
We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
arXiv Detail & Related papers (2021-05-14T11:31:14Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
Security-constrained optimal power flow (SCOPF) is fundamental in power systems.
Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs.
This paper proposes a novel approach that combines deep learning and robust optimization techniques.
arXiv Detail & Related papers (2020-07-14T12:38:21Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.