Vyom World.com Let's Touch the Sky Together!
 Home VyomWorld.com Home Free Magazines! VyomLinks.com Home JobsAssist.com Home Vyom Network Contact Us Jobs & Careers Resume Submitter Placement Papers IT Companies Directory Computer Jobs Interview Questions Online Exams Vyom Career eMag. Fun Screensavers New! Send FREE SMS! SMS Jokes Source Codes Library Source Codes Home ASP Source Codes C Source Codes C++ Source Codes COBOL Source Codes Java Source Codes Pascal Source Codes Submit Source Codes GATE GATE an Overview GATE Preparation Study Materal GRE GRE an Overview GRE Questions GRE Preparation GRE Universities TOEFL Preparation TOEFL Resources GMAT Preparation GMAT Resources MBA Preparation MBA Resources Networking Concepts Networking Concepts Testing Preparation Testing Resources Webmasters Free Traffic Builder Webmaster Articles Web Hosting Tutorials Hardware Tutorial 1500 Free eBooks New! FREE Publications
Vyom Career eMag.
 Get 9,000+ Interview Questions & Answers in an eBook. 9,000+ Interview Questions All Questions Answered 5 FREE Bonuses Free Upgrades Get it now!
Get 9,000+ Interview Questions with Answers in an eBook

### Analysis and Design of Algorithms

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:

1. S pi i Î J is the objective function chosen for optimization measure.
2. Using this measure, the next job to be included should be the one which increases S pi i Î J.
3. Begin with J = Æ and S pi = 0 iÎ J
4. Add a job to J which has the largest profit
5. Add another job to this J keeping in mind the following condition:
1. Search for job which has the next maximum profit.
2. See if this job is union with J is feasible or not.
3. If yes go to step (e) and continue else go to (iv)
4. Search for the job with next maximum profit and go to step (b)
6. 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

1. Write the algorithm for solving cassette-filling problem on your own.
2. When one medium is not enough to store all files how do you solve it.
3. Write the algorithm to implement knapsack problem
4. What is 0/1 knapsack, write algorithm and know the difference between general knapsack and 0/1 knapsack.
5. Write the algorithm for job scheduling method.
6. Solve for 4 job with profits (100,10,15,27) and delays (2,1,2,1)

 Discussion Center

Recently Updated: New Placement Papers added.
Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory