Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps (Q1330796)

The paper deals with timing the movements of a prescribed set of packets with different source-destination types through a network of transmission lines, where the switches have limited buffers under transmission blocking. Given any network and any selection of paths for the packets, the goal is to produce a schedule (which specifies for each packet when to move and when to wait) that minimizes the total time and the maximum queue sizes needed to route all packets to their destination. Let \(d\) (dilation) denote the maximum distance travelled by any packet and \(c\) (congestion) denote the largest number of packets that must traverse a single edge during the whole transmission procedure. The first result is a simple on-line algorithm which produces a schedule of length \(O(c + d^* \log (Nd))\) using queues of size \(O(\log (Nd))\), where \(N\) is the number of packets to be transmitted. The main result states that there exists a schedule with the following properties: (i) the length is of order \(O(c + d)\), (ii) at most a constant number of packets wait in each step. The proof is not constructive: It is proved that the probability for such schedule to exist is nonzero on a suitable underlying probability space. Applications of the result to job-shop- scheduling problems are discussed.