One of the most useful results in scheduling theory is the minimisation of flowtime on a single machine by the SPT, shortest processing time first, rule. Many important problems can be viewed as direct extensions of this basic model: These include various deterministic and stochastic scheduling problems, as well as problems in the control of single server, multiple server and networks of queues. Most of these problems are very complicated and do not have "nice", algorithmically calculable, optimal solutions. This research will investigate a new class of heuristics which provide approximate solutions for these problems, and new ways to assess their effectiveness. The research is based on two main ideas: The first is the calculation of appropriate dynamic priority indices to replace SPT. Such indices have the form of average reward per unit time maximized over stopping times, and generalize the Gittins index used in bandit problems. The second idea is a conjecture that SPT or other priority rules only fail to be optimal because of marginal phenomena or end effects, and therefore they can be shown to be close to optimal. It is expected that this research will show that these relatively simple rules have a turnpike property - for most states they give the optimal action.
