A collection of jobs requires service. Each job has an associated cost function; normally costs accrue when a job is completed. The amount of service needed to complete a job is a random variable with a known probability distribution. Service may be allocated to jobs according to a sot of order constraints between the jobs. The problem is to find a strategy of allocating service which minimizes the total expected costs of all jobs in the system and which observes the order constraints.