DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Quantum Shift Scheduling - A Comparison to Classical Approaches

Prüfer, Sven and Scherer, Antonius and Spörl, Andreas and Guggemos, Tobias and Pomplun, Nikolas and Lenzen, Christoph (2021) Quantum Shift Scheduling - A Comparison to Classical Approaches. In: 12th International Workshop on Planning and Scheduling for Space (IWPSS 2021). 12th International Workshop on Planning and Scheduling for Space (IWPSS 2021), 27.-29. Jul. 2021, virtuell.

[img] PDF

Official URL: https://sites.google.com/view/iwpss2021/schedule


Solving discrete optimization problems with constraints is a very common task in industry and research as it is fundamental in solving many planning tasks. In this paper we will look at an instance of a time table problem for generating shift schedules at the German Space Operation Center (GSOC). We describe the implementation of a quantum approach and compare the differences to classical optimization strategies, knowing that the problem sizes given to the quantum systems are not competitive yet. By doing so we are establishing a software chain that is able to map our problem to different physical systems which paves the way to problem solving as a hybrid solution where sub-problems are distributed among classical and quantum hardware. In this study we included three approaches to tackle the described problem. For the quantum part, we included a programmatically generated quantum circuit that yields a solution to a (sub) problem using Grovers algorithm, able to be run on any general quantum computer with sufficiently many qubits of sufficiently high quality. On the classical side, as a validation and benchmark reference, we use a heuristic search method, implemented by GSOCs own planning tool set Plato and PINTA (Lenzen et al. 2012; Nibler et al. 2021) as well as a constraint integer programming formulation solved by an external software framework, such as e. g. GLPK or SCIP (Gamrath et al. 2020). This paper builds on and extends results from (Scherer et al. 2021).

Item URL in elib:https://elib.dlr.de/145763/
Document Type:Conference or Workshop Item (Speech)
Title:Quantum Shift Scheduling - A Comparison to Classical Approaches
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Lenzen, ChristophUNSPECIFIEDhttps://orcid.org/0000-0003-3542-6303UNSPECIFIED
Date:27 July 2021
Journal or Publication Title:12th International Workshop on Planning and Scheduling for Space (IWPSS 2021)
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:No
EditorsEmailEditor's ORCID iDORCID Put Code
Chien, SteveJet Propulsion Laboratory, California Institute of TechnologyUNSPECIFIEDUNSPECIFIED
Keywords:Planning, Optimization, Quantum, Quantum Computing
Event Title:12th International Workshop on Planning and Scheduling for Space (IWPSS 2021)
Event Location:virtuell
Event Type:international Conference
Event Dates:27.-29. Jul. 2021
Organizer:California Institute of Technology
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Control Centre Technology
Location: Oberpfaffenhofen
Institutes and Institutions:Space Operations and Astronaut Training > Mission Technology
Deposited By: Prüfer, Sven
Deposited On:17 Nov 2021 09:49
Last Modified:17 Nov 2021 09:49

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.