Top

Published in:

2021 | OriginalPaper | Chapter

OnCall Operator Scheduling for Satellites with Grover’s Algorithm

Authors : Antonius Scherer, Tobias Guggemos, Sophia Grundner-Culemann, Nikolas Pomplun, Sven Prüfer, Andreas Spörl

Published in: Computational Science – ICCS 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The application of quantum algorithms on some problems in NP promises a significant reduction of time complexity. This work uses Grover’s Algorithm, designed to search an unstructured database with quadratic speedup, to find valid a solution for an instance of the on-call operator scheduling problem at the German Space Operation Center. We explore new approaches in encoding the problem and construct the Grover oracle automatically from the given constraints and independent of the problem size. Our solution is not designed for currently available quantum chips but aims to scale with their growth in the next years.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Implementing Quantum Finite Automata Algorithms on Noisy Devices

next chapter Multimodal Container Planning: A QUBO Formulation and Implementation on a Quantum Annealer

This is needed e. g., for updating an on-call schedule during the year when operators have updated their vacations, for example. In this case only the future will be replanned, but the past may influence the applied constraints in the future.

The number of used qubits is given by the sum of counts of problem-encoding qubits, necessary global conflict counter register qubits and one Grover phase-flip qubit, so e. g., \(\log _2 4 \cdot 2\cdot 3+2+1=15\).

Except for Case V, where the approximations are not valid, but the exact formula reproduces the numbers given in the table.

Including qubit initialisation and measurement operations.

Abernathy, W.J., Baloff, N., Hershey, J.C., Wandel, S.: A three-stage manpower planning and scheduling model-a service-sector example. Oper. Res. 21(3), 693–711 (1973)CrossRef

Akbari, M., Zandieh, M., Dorri, B.: Scheduling part-time and mixed-skilled workers to maximize employee satisfaction. Int. J. Adv. Manuf. Technol. 64(5–8), 1017–1027 (2013)CrossRef

Bai, R., Burke, E.K., Kendall, G., Li, J., McCollum, B.: A hybrid evolutionary approach to the nurse rostering problem. IEEE Trans. Evol. Comput. 14(4), 580–590 (2010)CrossRef

Bard, J.F., Wan, L.: The task assignment problem for unrestricted movement between workstation groups. J. Sched. 9(4), 315–341 (2006)MathSciNetCrossRef

Van den Bergh, J., Beliën, J., De Bruecker, P., Demeulemeester, E., De Boeck, L.: Personnel scheduling: a literature review. Eur. J. Oper. Res. 226(3), 367–385 (2013)MathSciNetCrossRef

Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46(4–5), 493–505 (1998). https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-PCrossRef

Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemp. Math. 305, 53–74 (2002)MathSciNetCrossRef

Burke, E.K., De Causmaecker, P., Berghe, G.V., Van Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7(6), 441–499 (2004)MathSciNetCrossRef

Cerf, N.J., Grover, L.K., Williams, C.P.: Nested quantum search and NP-complete problems. arXiv preprint arXiv:quant-ph/9806078 (1998)

10.

Coecke, B., Horsman, D., Kissinger, A., Wang, Q.: Kindergarden quantum mechanics graduates (... or how I learned to stop gluing LEGO together and love the ZX-calculus). CoRR abs/2102.10984 (2021). https://arxiv.org/abs/2102.10984.pdf

11.

Cordeau, J.F., Laporte, G., Pasin, F., Ropke, S.: Scheduling technicians and tasks in a telecommunications company. J. Sched. 13(4), 393–409 (2010)MathSciNetCrossRef

12.

Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)

13.

Gilliam, A., Woerner, S., Gonciulea, C.: Grover adaptive search for constrained polynomial binary optimization. arXiv preprint arXiv:1912.04088 (2019)

14.

Glos, A., Krawiec, A., Zimborós, Z.: Space-efficient binary optimization for variational computing (2020)

15.

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (ed.) Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM, New York (1996)

16.

Hartung, J., Nibler, R., Peat, C., Spörl, A.K., Wörle, M.T., Lenzen, C.: GSOC SoE-Editor 2.0 - A Generic Sequence of Events Tool (2016). https://doi.org/10.2514/6.2016-2568

17.

Hogg, T.: Highly structured searches with quantum computers. Phys. Rev. Lett. 80(11), 2473 (1998)MathSciNetCrossRef

18.

Ikeda, K., Nakamura, Y., Humble, T.S.: Application of quantum annealing to nurse scheduling problem. Sci. Rep. 9(1), 1–10 (2019)

19.

Jaumard, B., Semet, F., Vovor, T.: A generalized linear programming model for nurse scheduling. Eur. J. Oper. Res. 107(1), 1–18 (1998)CrossRef

20.

Lenzen, C., Wörle, M.T., Mrowka, F., Spörl, A., Klaehn, R.: The algorithm assembly set of Plato. In: 12th International Conference on Space Operations, SpaceOps 2012 (2012). ePoster. https://elib.dlr.de/75694/

21.

Nibler, R., Mrowka, F., Wörle, M.T., Hartung, J., Lenzen, C., Peat, C.: PINTA and TimOnWeb - (more than) generic user interfaces for various planning problems. In: 10th International Workshop on Planning and Scheduling for Space, IWPSS 2017 (July 2017). https://elib.dlr.de/114095/

22.

Peruzzo, A., et al.: A variational eigenvalue solver on a quantum processor. eprint. arXiv preprint arXiv:1304.3061 (2013)

23.

Sanders, Y.R., et al.: Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum 1(2), 020312 (2020)

24.

Tabi, Z., et al.: Quantum optimization for the graph coloring problem with space-efficient embedding. In: 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 56–62 (2020). https://doi.org/10.1109/QCE49297.2020.00018

25.

van de Wetering, J.: ZX-calculus for the working quantum computer scientist. arXiv preprint arXiv:2012.13966 (2020). https://arxiv.org/pdf/2012.13966.pdf

26.

Wörle, M.T., Spörl, A., Hartung, J., Lenzen, C., Mrowka, F.: The mission planning system for the firebird spacecraft constellation. In: Proceedings of the 14th International Conference on Space Operations, Daejeon, Republic of Korea (2016)

Title: OnCall Operator Scheduling for Satellites with Grover’s Algorithm
Authors: Antonius Scherer
Tobias Guggemos
Sophia Grundner-Culemann
Nikolas Pomplun
Sven Prüfer
Andreas Spörl
Publisher: Springer International Publishing
Book: Computational Science – ICCS 2021
Print ISBN: 978-3-030-77979-5

Electronic ISBN: 978-3-030-77980-1

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-77980-1_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner