Consider the problem of scheduling a collection of processes on one processor. Each process Ji has a work xi , a release time ri , and a deadline di . All these values are positive integers. A job can not be run before its release time or after its deadline. The goal is to find the slowest possible speed that will allow you to finish do all the work from each job. If a job is processed at speed s for t units of time, this will complete s t units of work from that job. The processor can process at most one job at each moment of time. But a processor can switch between processes arbitrarily. For example, the processor can run J1 for a while, then switch to J2, then back to J1, then to J3, etc. The times of these switches need not be integer.

(a) Express this problem as a linear program.

(b) Construct the dual program.

(c) Give a natural English interpretation of the dual problem (e.g. similar to how we interpreted the dual of the max flow problem as the min cut problem).

(d) Explain how to give a simple proof that the input is infeasible for a particular speed. You should be able to come up with a method that would convince someone who knows nothing about linear programming. Hint: Figure out what this problem has to do with bipartite matching.