Past exam of the probability, statistics and options I course of the University of Oxford / 2007 / S / 1 / Solution

The first four jobs all have deadlines at most ten, but their total processing time is $2+4+3+2=11$. They cannot all be completed by time ten on one machine, so at least one is late in every schedule.

Moore's algorithm processes jobs in nondecreasing deadline order. Whenever the electric current on-time list first misses the new job's deadline, remove from that list a job with the largest processing time and put it on the late list. Continue, then append the rejected jobs after the on-time list. The theorem for this algorithm states that it minimizes the number of late jobs when all jobs are initially available.

The source order is already deadline order. The steps areAfter the first removal the cumulative time is seven; after the second it is eleven. Append jobs two and five. One optimal schedule isIts completion times are $2,5,7,11,15,20$. Comparing with the corresponding deadlines verifies that precisely jobs two and five are late. Moore's theorem certifies that no schedule can improve on that number.