Two Exact Algorithms for the Packet Scheduling Problem

We consider a classic packet scheduling problem [7] and its variants. This packet scheduling problem has applications in the areas of logistics, road traffic, and more. There is a network and a set of unit-length packets are to be transmitted over the network from their respective sources to their respective destinations. Each packet is associated with a directed path on which it must travel along. Time is discrete. Initially, all the packets stay on the first edges of their respective paths. Packets are pending on the edges at any time. In each time step, a packet can move along its path by one edge, given that edge having no other packets move onto it in the same time step. The objective is to minimize makespan – the earliest time by which all the packets arrive at their respective destination edges. This problem was proved NP-hard [1] and it has been studied extensively in the past three decades. In this paper, we first provide a semi-online algorithm GRD and show that GRD is optimal for scheduling packets on arborescence and/or anti-arborescence forests. We then provide a parameterized algorithm PDP which finds an optimal makespan for the general case. PDP is a dynamic programming algorithm and its running time complexity depends on the congestion and dilation in the input instance. The algorithm PDP’s idea is new and it is derived from an insightful lower bound construction for the general packet scheduling problem.