Scherer, A. B. A. (2021):Spacecraft Operator Scheduling with Grovers AlgorithmThe application of quantum algorithms on some problems in NP promises a significant reduction of time complexity. This thesis uses Grover's Algorithm, originally designed to search an unstructured database with quadratic speedup, to find valid solution bit-strings to the NP-hard personnel scheduling problem. Under consideration of various hard and soft constraints, we implement this by using the IBMQ backend and Qiskit to optimize the German Aerospace Center's spacecraft on-call operator scheduling. We seek an optimal assignment for 52 operators to 17 positions over a period of 180 days under constraints on schedule and personnel. Further, we evaluate the solution quality and compare the performance with classical and quantum alternatives. While still restricted by intermediate-scale quantum devices in the near term, we explore new approaches in encoding and batching the problem to reduce the required number of qubits. In the end, a feasible near-term solution that scales well with the quantum devices of the upcoming years is presented.
|