Job scheduling is a complex optimization problem with multiple variables, constraints, and goals. Solving such problems using classical computing can be challenging, since they are NP-hard and real-world instances can be quite large. Quantum computing is a promising solution, as it is theoretically faster than classical computing for certain types of problems. In this thesis, we use the filtering variational quantum eigensolver (F-VQE), a parameter- ized quantum algorithm, to solve a simplified real-world scheduling problem. The F-VQE algorithm optimizes solutions by filtering out unpromising ones and using a classical op- timization routine to refine the remaining solutions. Although the F-VQE algorithm is based on a paper by Amaro et al., it has not yet been fully evaluated for solving scheduling problems. While VQEs have been successful in solving combinatorial optimiza- tion problems, we seek to assess the performance of F-VQE in solving scheduling problems. We have two objectives in this research: firstly, to enhance and analyze the F-VQE al- gorithm, and secondly, to evaluate the potential of quantum computing in solving complex scheduling problems. To accomplish this, we will compare the performance of the F-VQE algorithm with other quantum and classical approaches for solving real-world scheduling problems. This will provide valuable insights into the effectiveness of quantum comput- ing for solving these problems, as well as identify potential improvements to the F-VQE algorithm. We delve deeper into the F-VQE algorithm to identify potential areas for improvement. We will examine various Ansatz designs and different filtering strategies. Additionally, we will investigate encoding techniques like Binary Encoding or Multi-Basis Encod- ing. Worthwhile additions are implemented and tested against. To compare the F-VQE algorithm’s performance with its improvements, other quantum algorithms and a classical heuristic approach, we review relevant literature on quantum computing and combinatorial optimization problems with constraints. We then implement a F-VQE, VQE and QAOA Solver, comparing their performance on a dataset of small scheduling problems from the German Aerospace Center (DLR). The objective of the Space- craft Quantum On-Call Scheduling (SQOS) problem is to determine the most suitable on-call shifts for operators assigned to each satellite mission. The Solvers are also compared with an approach using Grover’s algorithm, which is already implemented by the DLR. We evaluate the efficiency, scalability, and quality of solutions provided by each algorithm and discuss the potential benefits and drawbacks of the F-VQE for solving real-world scheduling problems.
Aufgabensteller:
Dauer der Arbeit:
Anzahl Bearbeiter: 1
Betreuer: