A set J of jobs are to be scheduled on M identical machines. Each job j E J has a processing requirement p5,- (denoting the number of machine days...

It is a kind of problem about max-flow and min-cut.

2. A set J of jobs are to be scheduled on M identical machines. Each job j E J has a processingrequirement p5,- (denoting the number of machine days required to complete the job), a releasedate rj (representing the beginning of the day when job 3' becomes available for processing),and a due date dj 2 T'J' + pg: (representing the beginning of the day by which the job must becompleted). We aSSume that a machine can work on only One job at a time and that each jobcan be processed by at most one maChine at a time. However, we allow preemptions (ie, we caninterrupt a job and process it on different machines on different days). The scheduling problemis to determine a feasible schedule that completes all jobs before their due dates or to show thatno such schedule exists. Formulate this problem as a maximum flow problem.