Past exam of the probability, statistics and options I course of the University of Oxford / 2007 / S (Combinatorial Optimisation)

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.

flow conservation determines the unspecified initial arcs:Every entry respects capacity, and the initial value is four. In the residual network take the augmenting pathThe step $4\to 3$ is the reverse residual arc of the used arc $3\to 4$. Its use cancels some existing flow rather than sending new physical flow on a nonexistent original arc. The residual capacities along the path are $2,1,2,2,1$, so augment by their minimum, one.

The resulting original-arc flows areTheir value is five. The cut separating the sink from all other nodes has capacity $c_{46}+c_{56}=3+2=5$. Every feasible flow is bounded by this cut capacity, so the value-five flow is optimal.

Start the augmenting-path algorithm from the zero flow. With integer capacities and an integer electric current flow, every residual capacity is an integer, so a path bottleneck is a positive integer. Augmenting by it preserves integrality and increases the flow value by at least one. The value is bounded by the finite total capacity leaving the source, so the process terminates. At termination there is no augmenting path, hence the flow is maximum by the max-flow min-cut theorem. Its value is an integer.

Equivalently a minimum cut has capacity equal to the sum of integer arc capacities, so the maximum flow value equals an integer. Thus integer capacities guarantee an integer optimal volume, even though arbitrary feasible real-valued flows need not themselves have integer entries.