Question

1. Suppose you have four jobs that must be processed, with the following table giving their charac- teristics(all times in hours): Each job can be processed on any of three identical machines; to be Job 1 23 4 Processing time 21.524 | 2 | 0 | 0.5 | 1 Release time Processing time 5346 finished, a job must be processed for its entire processing time, but this processing time can be interrupted and even moved to a different machine if necessary. For example, we could process job 1 from hour 2 to 3 on machine 1, then pause it, then process it from hour 4 to 5 on machine 2. However, you cant double-up and process a job simultaneously on two machines. Formulate a maximum flow model that decides whether the jobs can be scheduled on the three machines so that each job begins processing on or after its release time and ends processing no later than its due time. Hint: Your network should have a node for every job, but also nodes for intervals of time that represent machine processing capacity.

Answer 1

Job 1: Total Processing Time: 5 hrs

Job 2: Total Processing Time: 3 hrs

Job 3: Total Processing Time: 4 hrs

Job 4: Total Processing Time: 6 hrs

Machine Times:

Machine	Processing time	Release time
1	2	2
2	1.5	0
3	2	0.5
4	4	1

Ans)

We can finish given 4 jobs in maximum of 7.5 hrs.

Time (in hrs)	Machine1	Machine2	Machine3	Machine4
0-0.5	Job 3		Job1	Job4
0.5-1	Job 3		Job1	Job4
1- 1.5	Job3		Job1	Job4
1.5-2.0	Job3		Job1	Job4
2.0-2.5		Job1		Job4
2.5-3.0		Job3	Job1	Job4
3.0-3.5		Job3	Job1	Job4
3.5-4.0		Job3	Job1	Job4
4.0-4.5	Job4	Job1	Job2
4.5-5.0	Job4	Job1
5.0-5.5	Job4			Job2
5.5-6.0	Job4			Job2
6.0-6.5				Job2
6.5-7.0				Job2
7.0-7.5				Job2

At max, we can finish the job within 7.5hours