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

• Hybrid Quantum-HPC Solutions for Max-Cut: Bridging Classical and Quantum Algorithms [0.0]
  We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. We evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization.
  arXiv  Detail & Related papers  (2024-10-21T04:10:54Z)
• Evaluation of Quantum Annealing-based algorithms for flexible job shop scheduling [9.674641730446748]
  A flexible job shop scheduling problem (FJSSP) poses a complex optimization task. approximation methods are employed to ensure solutions are within acceptable timeframes. Quantum Annealing, a metaheuristic leveraging quantum mechanical effects, demonstrates superior solution quality in a shorter time.
  arXiv  Detail & Related papers  (2024-08-28T09:52:14Z)
• PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms [4.2435928520499635]
  Portfolio Optimization (PO) is a financial problem aiming to maximize the net gains while minimizing the risks in a given investment portfolio. We propose a novel scalable framework, denoted PO-QA, to investigate the variation of quantum parameters. Our results provide effective insights into comprehending PO from the lens of Quantum Machine Learning.
  arXiv  Detail & Related papers  (2024-07-29T10:26:28Z)
• 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)
• 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.