On Optimal Scheduling Algorithms for Time-Shared Systems

Abstract

The problem of fmdlng those optimum scheduling algorithms for time-shared systems that mlmmize a cost function that depends on waiting time and required service time IS considered An optimality condmon which sometimes leads to infeasible algorithms is established The procedure is unproved upon by use of a mathematical programming technique but still does not always generate feasible algorithms. These results are used as upper bounds on the performance of known feasible algorithms so that it is possible to evaluate how close to optimal the present algorithms come.