The use of stochastic models for scheduling problems far from making the problems harder, tends to make them more tractable. This is illustrated by previous results on the scheduling of jobs on parallel machines with the weighted flowtime as objective criterion: While the deterministic problem is NP-hard, it has been proved that a simple, easily applied heuristic (Smith's Rule) is very close to optimal in the general stochastic setting. Continuing focus on heuristics will be used to tackle three further stochastic scheduling problems of practical importance: Scheduling of parallel machines subject to due dates, preemptive scheduling of parallel machines, and scheduling of machines in series (flowshops). The least restrictive assumptions on processing time distributions will be used. A deeper level of understanding for the dynamic optimal simultaneous operation of several machines is suggested in the new "Restless Bandits" model of Peter Whittle. Whittle suggests a Lagrangian relaxation and a priority rule which generalizes the Gittins' index of bandit problems as upper and lower bounds for an optimal policy. Other important recent results on control of queueing networks are those obtained by J.M. Harrison and L.M. Wein, using Brownian control problems as approximations. Another objective of this research is to prove Whittle's conjecture that his bounds are asymptotically optimal, and to discover a strong connection between Whittle's approach and that of Harrison and Wein. Based on these results it should be possible to derive some new heuristics and to prove their asymptotic optimality.
