Minimum Message Waiting Time Scheduling in Distributed Systems

In this paper, we examine the problem of packet scheduling in a single-hop multichannel system, with the goal ofminimizing the average message waiting time. Such an objective function represents the delay incurred by the users before receivingthe desired data. We show that the problem of finding a schedule with minimum message waiting time is NP-complete, by means ofpolynomial time reduction of the time table design problem to our problem. We present also several heuristics that result in outcomesvery close to the optimal ones. We compare these heuristics by means of extensive simulations