On the Kleinrock-Nilsson problem of optimal scheduling algorithms for time-shared systems (Q1061598)

We seek to minimize the mean-squared deviation of a waiting time function from a desired response function over the class of waiting time functions satisfying the Kleinrock-Nilsson necessary conditions. We will characterize analytically the optimal policy as the minimum majorant in the appropriate class of the cumulative ''response to go''. We will show that, in general, the monotonicity necessary condition results in optimal policies which depend in some sense on the future and are anticipating.