This paper explores the application of the quantum approximate optimization algorithm (QAOA) to the oversubscribed satellite scheduling problem (OSSP), a critical challenge in optimizing communication tasks between satellites and ground stations. The OSSP involves assigning tasks within predefined time windows while minimizing conflicts from overlapping assignments, a problem inherently combinatorial in nature. By formulating the OSSP as a quadratic unconstrained binary optimization problem and translating it into a quantum circuit suitable for QAOA, we present an algorithm for the optimization of the QAOA’s parameters as the number of circuit levels [Formula: see text] increases, by retaining the best parameter values found at each iteration. Experimental evaluations on quantum simulators demonstrate the effectiveness of our approach, thus realizing the QAOA’s potential in addressing complex scheduling tasks efficiently and providing insights into its scalability and applicability in real-world satellite operations.
This paper explores the application of the quantum approximate optimization algorithm (QAOA) to the oversubscribed satellite scheduling problem (OSSP), a critical challenge in optimizing communication tasks between satellites and ground stations. The OSSP involves assigning tasks within predefined time windows while minimizing conflicts from overlapping assignments, a problem inherently combinatorial in nature. By formulating the OSSP as a quadratic unconstrained binary optimization problem and translating it into a quantum circuit suitable for QAOA, we present an algorithm for the optimization of the QAOA’s parameters as the number of circuit levels [Formula: see text] increases, by retaining the best parameter values found at each iteration. Experimental evaluations on quantum simulators demonstrate the effectiveness of our approach, thus realizing the QAOA’s potential in addressing complex scheduling tasks efficiently and providing insights into its scalability and applicability in real-world satellite operations.
Task scheduling with constrained time intervals and limited resources remains a fundamental challenge across domains such as manufacturing, logistics, cloud computing, and healthcare. This study presents a novel variant of the Quantum Approximate Optimization Algorithm (QAOA) designed to address the task scheduling problem formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model. The proposed method, referred to as Quantum Time Interval Scheduler (QTIS), integrates an ancilla-assisted quantum circuit to dynamically detect and penalize overlapping tasks, enhancing the enforcement of scheduling constraints. Two complementary implementations are explored for overlap detection: a quantum approach based on RY rotations and CCNOT gates, and a classical alternative relying on preprocessed interval comparisons. QTIS decomposes the problem Hamiltonian, Hp, into two components, each parameterized by a distinct angle. The first component encodes the objective function, while the second captures penalty terms associated with overlapping intervals, which are controlled by the auxiliary circuit. Subsequently, three minimization strategies are evaluated: standard QAOA, T-QAOA, and HT-QAOA, showing that employing separate parameters for the different components of the problem Hamiltonian leads to lower energy values and improved solution quality. Results confirm the efficiency of QTIS in scheduling tasks with fixed temporal windows while minimizing conflicts, demonstrating its potential to advance hybrid quantum-classical optimization in complex scheduling environments.
Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.
Scheduling medical staff in healthcare institutions is a complex and critical task that requires balancing operational constraints, personnel availability, quality of care, and staff well-being. These interdependent factors make the creation of optimal schedules particularly challenging necessitating sophisticated approaches that effectively reconcile institutional needs and medical staff expectations. This project explores an innovative alternative approach: quantum optimization. By formulating the scheduling problem as a QUBO (Quadratic Unconstrained Binary Optimization) model, we aim to leverage the capabilities of quantum algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA) This framework allows constraints and objectives to be reformulated as quadratic functions, facilitating their integration into Ising models and their resolution on quantum gate_based circuit systems.To this end, we implement a hybrid quantum-classical solution using QAOA on IBM’s Qiskit platform. We analyze QAOA’s performance on problem instances of up to 27 qubits, and compare it against classical solvers such as CPLEX. Through this comparative approach, we assess the practical viability of quantum optimization in medical staff scheduling and contribute to the broader investigation of quantum computing in operational planning within healthcare systems.
Abstract The scheduling complexity of Agile Earth Observation Satellites (AEOSs) increases significantly as Earth Observation missions progress. This makes traditional optimization techniques less effective, restricting their application to small-scale and open-loop scheduling problems. In this paper, we investigate the potential of quantum solvers to address the closed-loop scheduling problem for a formation of AEOSs, overcoming the limitations of classical optimization techniques. To this end, we formulate the scheduling problem as a novel Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e., a formulation specifically designed for quantum solvers. Moreover, penalty functions are introduced to minimize mission energy consumption and reduce deviations between the original and rescheduled solutions. The formulated QUBO problem is implemented on a D-Wave quantum annealer for a daily and large-scale scheduling scenario. The obtained results demonstrate significant improvements in computational efficiency and solution quality compared to traditional methods like Simulated Annealing and Tabu Search, highlighting the potential of quantum solvers in optimizing complex scheduling tasks for AEOS formations.
Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.
Combinatorial Optimization (CO) is one of the most important areas in the field of optimization, with practical applications found in every industry, including both the private and public sectors. In recent years, it was discovered that a mathematical formulation known as QUBO (Quadratic Unconstrained Binary Optimization) problem can embrace an exceptional variety of important CO problems found in the industry. In this work, we explore the Quantum Approximate Optimization Algorithm (QAOA) as a quantum computing approach to solve the Knapsack Problem efficiently by formulating the problem as a QUBO model. Here we implemented QAOA on a quantum emulator, leveraging quantum superposition and entanglement to explore multiple solutions simultaneously. The method offers a promising route for solving large, complex scheduling and resource allocation problems that are tough for classical algorithms, with potential applications in logistics, HPC resource scheduling, and energy optimization.