One Stop GATE Forum: Job scheduling

Message

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 d_i ³
 0 and a profit p_i ³
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
 p_i  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
 p_i  i Î
 J.
Begin with J = Æ
 and S
 p_i = 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 3^rd unit since the third job is not available 4^th 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)

Author	Message
gita Newbie Joined: 08Apr2007 Online Status: Offline Posts: 19	Topic: Job scheduling 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 d_i ³ 0 and a profit p_i ³ 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 p_i 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 p_i i Î J. Begin with J = Æ and S p_i = 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 3^rd unit since the third job is not available 4^th 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) Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged


One Stop GATE Forum : GATE Technical Discussions : GATE CS