Scheduling time-constrained communication in linear networks
Micah Adler, Ramesh K. Sitaraman, Arnold L. Rosenberg, WALTER P. UNGER · 1998
We study the problem of centrally scheduling multiple messages in a linear network, when each message has both a release time and a deadline.We show that the problem of transmitting optimally many messages is NP-hard, both when messages may be buffered in transit and when they may not be; for either case, we present efficient algorithms that produce approximately optimal schedules.In particular, our bufferless scheduling algorithm achieves throughput that is within a factor of two of optimal.We show that buffering can improve throughput in general by a logarithmic factor (but no more), but that in several significant special cases, such as when all messages can be released immediately, buffering can help by only a small constant factor.Finally, we show how to convert our centralized, offline bufferless schedules to equally productive fully