We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Quantum computer-aided job scheduling for storage and retrieval systems.
- Authors
Windmann, Stefan
- Abstract
In this paper, a quantum computer-aided approach to job scheduling for automated storage and retrieval systems is introduced. The approach covers application cases, where various objects need to be transported between storage positions and the order of transport operations can be freely chosen. The objective of job scheduling is to arrange the transport operations in a sequence, where the cumulative costs of the transport operations and empty runs between subsequent transport operations are minimized. The scheduling problem is formulated as an asymmetric quadratic unconstrained binary optimization (QUBO) problem, in which the transport operations are modeled as nodes and empty runs are modeled as edges, with costs assigned to each node and each edge. An Quantum Approximate Optimization Algorithm (QAOA) is used to solve the QUBO. Evaluations of the quantum computer-aided job scheduling approach have been conducted on the IBM Q System One quantum computer in Ehningen. In particular, the running time for the solution of the QUBO has been investigated, as well as the scalability of the approach with respect to the required number of qubits. Zusammenfassung: In diesem Beitrag wird ein Quantencomputer-gestützter Ansatz zur Auftragsplanung für automatisierte Regalbediengeräte vorgestellt. Der Ansatz adressiert Anwendungsfälle, in denen verschiedene Objekte zwischen Lagerpositionen transportiert werden, wobei die Reihenfolge der Transportvorgänge frei gewählt werden kann. Das Ziel der Auftragsplanung ist es, die Reihenfolge so zu optimieren, dass die kumulierten Kosten für die eigentlichen Transportvorgänge sowie zusätzlich erforderliche Leerfahrten minimiert werden. Das Scheduling-Problem wird als asymmetrisches quadratisches, binäres Optimierungsproblem (QUBO) formuliert, in dem die eigentlichen Transportvorgänge als Knoten und die Leerfahrten als Kanten modelliert werden, denen jeweils Kosten zugeordnet werden. Zur Lösung des QUBO-Problems wird ein Quantum Approximate Optimization Algorithm (QAOA) verwendet. Die Evaluierung des vorgeschlagenen Ansatzes wurde auf dem IBM Q System One Quantencomputer in Ehningen durchgeführt, wobei insbesondere die Laufzeit für die Lösung des QUBOs sowie die Skalierbarkeit des Ansatzes in Bezug auf die benötigte Anzahl von Qubits untersucht wurde.
- Subjects
AUTOMATED storage retrieval systems; QUANTUM computers; OPTIMIZATION algorithms; SCHEDULING
- Publication
Automatisierungstechnik, 2024, Vol 72, Issue 1, p15
- ISSN
0178-2312
- Publication type
Article
- DOI
10.1515/auto-2023-0072