5.3 Job Scheduling:
In a job-scheduling problem, we are given a list of n jobs. Every job i is associated with an integer deadline di ³
0 and a profit pi ³
0 for any job i, profit is earned if and only if the job is completed within its deadline. A feasible solution with maximum sum of profits is to be obtained now.
To find the optimal solution and feasibility of jobs we are required to find a subset J such that each job of this subset can be completed by its deadline. The value of a feasible solution J is the sum of profits of all the jobs in J.
Steps in finding the subset J are as follows:
S
pi i Î
J is the objective function chosen for optimization measure.
Using this measure, the next job to be included should be the one which increases S
pi i Î
J.
Begin with J = Æ
and S
pi = 0 iÎ
J
Add a job to J which has the largest profit
Add another job to this J keeping in mind the following condition:
Search for job which has the next maximum profit.
See if this job is union with J is feasible or not.
If yes go to step (e) and continue else go to (iv)
Search for the job with next maximum profit and go to step (b)
Terminate when addition of no more jobs is feasible.
Illustration:
Consider 5 jobs with profits (p1,p2,p3,p4,p5) = (20,15,10,5,1) and maximum delay allowed (d1,d2,d3,d4,d5) = (2,2,1,3,3).
Here maximum number of jobs that can be completed is = Min(n,maxdelay(di))
= Min(5,3)
= 3.
Hence there is a possibility of doing 3 jobs.
There are 3 units of time
Time Slot
[0-1] [1-2] [2-3] Profit
Job
1 - yes - 20
2 yes - - 15
3 cannot accommodate --
4 - - yes 5
40
In the first unit of time job 2 is done and a profit of 15 is gained, in the second unit job 1 is done and a profit 20 is obtained finally in the 3rd unit since the third job is not available 4th job is done and 5 is obtained as the profit in the above job 3 and 5 could not be accommodated due to their deadlines.
Exercise 5
Write the algorithm for solving cassette-filling problem on your own.
When one medium is not enough to store all files how do you solve it.
Write the algorithm to implement knapsack problem
What is 0/1 knapsack, write algorithm and know the difference between general knapsack and 0/1 knapsack.
Write the algorithm for job scheduling method.
Solve for 4 job with profits (100,10,15,27) and delays (2,1,2,1)
