| Job Scheduling |
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)
|
