Inadequately planned factory layouts can lead to higher operational costs. The planning process is time-consuming and multiple planning parameters must be considered simultaneously, leading to large solution spaces. Automated planning approaches can support the planning team in the early phases of layout planning by generating layout variants that can afterwards be further specified. Recent studies from other disciplines have shown the potential of Quantum Annealing (QA) to solve complex assignment problems within seconds. Consequently, this paper presents a first implementation of a QA-based layout planning approach and demonstrates its advantages regarding scalability, solution quality, and computing time.
Inadequately planned factory layouts can lead to higher operational costs. The planning process is time-consuming and multiple planning parameters must be considered simultaneously, leading to large solution spaces. Automated planning approaches can support the planning team in the early phases of layout planning by generating layout variants that can afterwards be further specified. Recent studies from other disciplines have shown the potential of Quantum Annealing (QA) to solve complex assignment problems within seconds. Consequently, this paper presents a first implementation of a QA-based layout planning approach and demonstrates its advantages regarding scalability, solution quality, and computing time.
The earlystage of factory layout planning has a direct effect on the operating costs, efficiency, and productivity of manufacturing systems. Conventional automated planning approaches often face a trade-off between solution quality and computational effort. Recent studies have investigated the potential of quantum annealing (QA) for solving factory layout planning problems. However, existing studies have mainly focused on individual QA-based formulations, whereas current hybrid QA solvers support multiple model types that combine QA and classical methods. To explore the potential of QA for factory layout planning, this paper benchmarks four QA based approaches implemented with the corresponding solvers, including an iterative binary quadratic model (IBQM), a hybrid discrete quadratic model (HDQM), a hybrid constrained quadratic model (HCQM), and a hybrid nonlinear model (HNLM). To improve scalability, an iterative decomposition strategy is developed for IBQM, while a candidate selection procedure is introduced for HDQM. The approaches are benchmarked against genetic algorithm, particle swarm optimization, and a hybrid tabu search and simulated annealing approach on 14 layout instances with different layout sizes, geometric complexity, spatial restrictions, and transport route configurations. The comparative analysis considers solution quality, computation time, and scalability. The results show that QA-based approaches achieve competitive solution quality and substantial computational advantages, reducing computation time by up to 94.51% relative to the classical reference methods. Among them, IBQM obtains the best solution quality in 78.6% of the instances, with a maximum improvement of 17.41% associated with an 81.34% reduction in computation time. These findings provide a basis for their further application in industrial layout planning.
Abstract Quantum Annealing (QA) is a metaheuristic for solving optimization problems in a time-efficient manner. Therefore, quantum mechanical effects are used to compute and evaluate many possible solutions of an optimization problem simultaneously. Recent studies have shown the potential of QA for solving such complex assignment problems within milliseconds. This also applies for the field of job shop scheduling, where the existing approaches however focus on small problem sizes. To assess the full potential of QA in this area for industry-scale problem formulations, it is necessary to consider larger problem instances and to evaluate the potentials of computing these job shop scheduling problems while finding a near-optimal solution in a time-efficient manner. Consequently, this paper presents a QA-based job shop scheduling. In particular, flexible job shop scheduling problems in various sizes are computed with QA, demonstrating the efficiency of the approach regarding scalability, solutions quality, and computing time. For the evaluation of the proposed approach, the solutions are compared in a scientific benchmark with state-of-the-art algorithms for solving flexible job shop scheduling problems. The results indicate that QA has the potential for solving flexible job shop scheduling problems in a time efficient manner. Even large problem instances can be computed within seconds, which offers the possibility for application in industry.
Supply chain planning is a complex optimization problem that involves the coordination of multiple resources in order to reduce costs and maximize benefit. In this study, we propose a QUBO formulation for the scheduling of the transportation of materials to a factory with uncertain arrival times. The standard methods like network flow or MILP solvers escalate exponentially with the problem parameters, making computation times grow rapidly. Quantum annealing is a candidate for an optimization poccess that can solve this computationally intense problems, and thus it is important to be able to find compatible formulations. The model proposed makes use of the QUBO formulation to give optimal solutions to the scheduling with unceratinty. We will establish the problem from a stochastic optimization point of view, and then build a hamiltonian that encodes it, following the QUBO formulation. With the quick increase in qubit numbers of quantum computers, this model seems like a promising tool that will provide solutions to very relevant and computionally hard problems in the near future.
Abstract : One approach to solving planning problems is to compile them to another problem for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances encoded as Quadratic Unconstrained Binary Optimization (QUBO). Early quantum annealers are now available, and more sophisticated quantum annealers will likely be built over the next decades. Specific quantum annealing hardware implementations have specific constraints, restricting the types of QUBOs each can take as input. In this paper, we introduce the planning community to the key steps involved in compiling planning problems to quantum annealing hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we provide preliminary results from running an early quantum annealer on a parameterized family of hard planning problems. The results show that different mappings can lead to a substantial difference in performance, even when many superficial features of the resulting instances are similar. We also provide some insights gained from this early study, and suggest directions for future work.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.
Abstract One approach to solving planning problems is to compile them to other problems for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances of quadratic unconstrained binary optimization (QUBO) problem. Early quantum annealers are now available, though their constraints restrict the types of QUBOs they can take as input. Here, we introduce the planning community to the key steps in compiling planning problems to QA hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we describe preliminary results from running an early quantum annealer on a parametrized family of hard planning problems. The results show that different mappings can substantially affect performance, even when many features of the resulting instances are similar. We conclude with insights gained from this early study that suggest directions for future work.