In this paper, we consider a wireless sensor network where the network topology is a tree and medium access control is TDMA. We focus on TDMA scheduling problem studied in [1]. Since scheduling problems are considered as a member in the class of NP-hard, it is difficult to obtain the optimal solution in the scheduling problem. To overcome the difficulty, we develop a computational method using quantum annealing in order to find near-optimal solutions in the TDMA scheduling problem. We provide some numerical results to compare the computational method using quantum annealing with other methods in terms of quality of solution, computation time and size of problem.
In this paper, we consider a wireless sensor network where the network topology is a tree and medium access control is TDMA. We focus on TDMA scheduling problem studied in [1]. Since scheduling problems are considered as a member in the class of NP-hard, it is difficult to obtain the optimal solution in the scheduling problem. To overcome the difficulty, we develop a computational method using quantum annealing in order to find near-optimal solutions in the TDMA scheduling problem. We provide some numerical results to compare the computational method using quantum annealing with other methods in terms of quality of solution, computation time and size of problem.
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.
The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem.
Most of the modern day computations are considered as an NP-hard like solving a puzzle or traveling salesman problem. Over the decades, engineers are exploring for many approaches of solution, out of which Quantum Annealing has depicted the efficacy. In this paper, we do a review study of Quantum Annealing (i.e., an approach to find the global mini-mum of a particular function that can provide better heuristics for the NP-hard optimization problem) and discussed briefly about quantum computers. Not only that, we also showcase few applications of quantum annealing which include scheduling problem, lung cancer detection, coherence in quantum annealer, and clustering.
Quantum annealing (QA) has shown good solutions quickly in benchmarks of combinatorial optimization problems. There are not many real-world problems that illustrate the effectiveness of QA compared to the typical optimization methods. We applied QA to a shift scheduling problem for call centers with four conditions. The shift scheduling problem for call centers optimizes shifts for a specific period of time while satisfying various constraints, such as satisfying the desired worker's shifts. In this paper, we formulated the shift scheduling problem for call centers in QUBO to apply QA. We tuned various parameters required to execute the QA. Then, we compared QA with six typical optimization methods using a classical computer to investigate QA's effectiveness for the shift scheduling problem for call centers. The results show that for three instances with up to 126 variables, QA is about 3-14 times faster than other methods and obtains enough quality of solutions. This shows that QA can be one of the effective methods to solve practical applications in the real-world.
Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.
In recent years, quantum computing has emerged as a rapidly advancing interdisciplinary field, attracting growing attention from both academia and industry owing to its fundamentally novel approach to information processing and its potential to achieve computational capabilities beyond the reach of classical systems. This paper presents a structured review of quantum computing approaches applied to scheduling problems, which are among the most challenging NP-hard optimization problems. We first introduce fundamental principles of quantum computing, including gate-based models, quantum annealing, and hybrid frameworks. We then explore how various scheduling problems such as job-shop, flow-shop, and project scheduling-are encoded into quantum models, particularly using QUBO formulations suitable for current quantum devices. Finally, we discuss key limitations such as hardware constraints and model scalability, and we identify research directions to advance quantumenhanced scheduling methods. By grounding theory in empirical case studies and highlighting near-term deployable solutions, this study bridges the gap between quantum algorithm development and practical scheduling demands, offering a roadmap for researchers and practitioners in quantum optimization.