Vyom World.com  . Let's Touch the Sky Together!  
. . . . . . .
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.
Screensavers New!
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 an Overview
GATE Preparation
Study Materal
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
Free Traffic Builder
Webmaster Articles
Web Hosting
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!

    Post your Resume to 5800+ Companies

    Reliable Web Hosting

    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.



    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


    1 - yes - 20

    2 yes - - 15

    3 cannot accommodate --

    4 - - yes 5


    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)

    Study Notes Home | Next Section>>


    Discussion Center



    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    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

    Copyright ©2003-2019 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy