Spacecraft Operator Scheduling with Grovers Algorithm

Abstract

The 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.