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.
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. The main disadvantage of calculations on quantum computers is their non-determinism. For optimization problems, of course, it is possible to get surprisingly good results but without a guarantee of the actual optimality of the result, i.e, an assurance that there exists no better solution which could potentially be found by the quantum machine. In this paper, we propose an novel approach that provides such a guarantee of optimality. We generate a solution that is optimal in the strict mathematical sense, without probabilistic considerations. To accomplish this, we use the D-Wave quantum machine working as a sampler implementing quantum annealing -- an approach considered a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then, we use the Branch and Bound scheme controlled by quantum annealing. This allows us to obtain very quickly -- in constant time -- the boundaries of the considered subproblems. Our approach is a combination of calculations realized on a quantum machine controlled by procedures implemented on a classical computer, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness criterion. The proposed quantum algorithm shows a significant advantage over the classical CPU approach both in terms of calculation time and the number of generated solution tree nodes.
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.
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.
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.