Average waiting time assignment. I. The single link case

A system is considered in which V users are competing for the transmission capacity of a link. The users generate messages in a Poisson manner. The message length distribution of each user is arbitrary and may differ for different users. The objective is to investigate nonpreemptive service-time independent scheduling as a means of selectively controlling the average waiting time of the users. The average waiting time assignments that can be realized are characterized. They can be used to establish, in O(V log V) computations, whether a given average waiting time assignment is feasible. The proof of the result relies on a universal scheduling strategy which is simple, is time-invariant, and can be used to realize any feasible average waiting time assignment. A waiting time cost function is associated with each user in order to investigate the problem of finding a nonpreemptive scheduling strategy that minimizes the overall waiting time cost. A set of optimality conditions is given for this problem, and an algorithm is constructed solving it in O (V) log V steps. With a simple modification, the algorithm also solves the problem of finding a nonpreemptive scheduling strategy that minimizes the lexicographic ordering of the waiting time costs. Results are extended to the preemptive case