Job scheduling
Printed From: One Stop GATE
Category: GATE Technical Discussions
Forum Name: GATE CS
Forum Discription: General Technical Discussions, Queries, doubts etc. for GATE in CS.
URL: http://forum.onestopgate.com/forum_posts.asp?TID=1098
Printed Date: 08Feb2025 at 6:14am
Topic: Job scheduling
Posted By: gita
Subject: Job scheduling
Date Posted: 08Apr2007 at 10:52pm
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 http://www.vyomworld.com/gate/cs/ada/5.3.asp# - 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)
|
|