Deadline-Aware Scheduling of Entanglement Requests in Quantum Networks

Quantum networks are emerging as a rapidly developing field with diverse applications. Current research mainly focuses on maximizing the number of entangled pairs between remote nodes or optimizing the success probability of entanglement requests within a given time slot. However, practical applications often necessitate consideration of request deadlines and tolerable delays. This paper addresses the problem of scheduling quantum links to fulfill entanglement requests under the deadline constraints, aiming to maximize the number of satisfied requests. We formulate the problem using an integer linear program based on the principles of flow networks, whose solution is optimal. In addition, a greedy algorithm is proposed, inspired by the idea that the request with the earliest deadline need to be fulfilled first. We then carry out simulation to evaluate the performance of the proposed methods. The results demonstrate that the solution yielded by the greedy algorithm can approach the optimal solution.