際際滷

際際滷Share a Scribd company logo

Job scheduling

Download as ODP, PDF
S
Sanjay Singh

The document describes an interval scheduling problem where jobs have start and end times and the goal is to schedule as many jobs as possible on a processor without overlapping jobs. It discusses using a greedy algorithm to solve this by considering jobs in order of increasing finish time and selecting a job if it does not overlap previously selected jobs. The algorithm runs in O(n log n) time, sorting jobs by finish time first, then selecting non-overlapping jobs in order, for a total time that is polynomial in n.

1 of 11
Downloaded 58 times
Job Scheduling Sanjay Singh Devis Karumanchi Durgesh Waghmare Litun Patra
Problem statement Consider the following variation on the Interval Scheduling Problem. You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each such job comes with a start time and an end time; if the job is accepted to run on the processor, it must run continuously, every day, for the period between its start and end times. Given a list of n such jobs, your goal is to accept as many jobs as possible (regardless of their length), subject to the constraint that the processor can run at most one job at any given point in time. Provide an algorithm to do this with a running time that is polynomial in n. You may assume for simplicity that no two jobs have the same start or end times. Example. Consider the following four jobs, specified by (start time, end-time) pairs. (6 P.M., 6 A.M.), (9 P.M., 4 A.M.), (3 A.M., 2 P.M.), (1 P.M., 7 P.M.). The optimal solution would be to pick the two jobs (9 P.M., 4 A.M.) and (1P.M., 7 P.M.), which can be scheduled without overlapping.
Greedy paradigm Two important components Builds up the solution in small steps Choose a decision myopically To optimize some underlying criterion Choose what is best for the moment Typically works in stages A decision made in one stage can not be changed later The choice must lead to the feasible solution Expected to be an optimal solution
Activity selection problem Selecting maximal set of mutually compatible activities Simple and elegant method Mutually compatible activities If each activity i occurs during the half open interval [si, fi) When do [si, fi) and [sj, fj) not overlap? i < j or j < i
Problem definition Job scheduling Job j starts at sj and finishes at fj Two jobs i and j are compatible if they do not overlap Goal: Find maximum subset of mutually compatible jobs.
Illustration
Interval Scheduling Greedy template. Consider jobs in some order. Take each job provided it's compatible with the ones already taken. - [Earliest start time] Consider jobs in ascending order of start time sj. - [Earliest finish time] Consider jobs in ascending order of finish time fj. - [Shortest interval] Consider jobs in ascending order of interval length fj sj. - [Fewest conflicts] For each job, count the number of conflicting jobs cj. Schedule in ascending order of conflicts cj. `
The strategies that fail Earliest start time fails Shortest interval fails Fewer conflict strategy fails
Solution Greedy algorithm Consider jobs in increasing order of finish time. Take each job provided it is compatible with the ones already taken.
Time complexity Sorting the jobs in increasing order of their finish times takes O(n log n) time Consider the job with the earliest finish time and thereon include the jobs into the solution set that are compatible with the preceding one. This takes O(n) time So the total running time comes out to be O(n log n)
Thank you

More Related Content

Job scheduling

  • 1. Job Scheduling Sanjay Singh Devis Karumanchi Durgesh Waghmare Litun Patra
  • 2. Problem statement Consider the following variation on the Interval Scheduling Problem. You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each such job comes with a start time and an end time; if the job is accepted to run on the processor, it must run continuously, every day, for the period between its start and end times. Given a list of n such jobs, your goal is to accept as many jobs as possible (regardless of their length), subject to the constraint that the processor can run at most one job at any given point in time. Provide an algorithm to do this with a running time that is polynomial in n. You may assume for simplicity that no two jobs have the same start or end times. Example. Consider the following four jobs, specified by (start time, end-time) pairs. (6 P.M., 6 A.M.), (9 P.M., 4 A.M.), (3 A.M., 2 P.M.), (1 P.M., 7 P.M.). The optimal solution would be to pick the two jobs (9 P.M., 4 A.M.) and (1P.M., 7 P.M.), which can be scheduled without overlapping.
  • 3. Greedy paradigm Two important components Builds up the solution in small steps Choose a decision myopically To optimize some underlying criterion Choose what is best for the moment Typically works in stages A decision made in one stage can not be changed later The choice must lead to the feasible solution Expected to be an optimal solution
  • 4. Activity selection problem Selecting maximal set of mutually compatible activities Simple and elegant method Mutually compatible activities If each activity i occurs during the half open interval [si, fi) When do [si, fi) and [sj, fj) not overlap? i < j or j < i
  • 5. Problem definition Job scheduling Job j starts at sj and finishes at fj Two jobs i and j are compatible if they do not overlap Goal: Find maximum subset of mutually compatible jobs.
  • 7. Interval Scheduling Greedy template. Consider jobs in some order. Take each job provided it's compatible with the ones already taken. - [Earliest start time] Consider jobs in ascending order of start time sj. - [Earliest finish time] Consider jobs in ascending order of finish time fj. - [Shortest interval] Consider jobs in ascending order of interval length fj sj. - [Fewest conflicts] For each job, count the number of conflicting jobs cj. Schedule in ascending order of conflicts cj. `
  • 8. The strategies that fail Earliest start time fails Shortest interval fails Fewer conflict strategy fails
  • 9. Solution Greedy algorithm Consider jobs in increasing order of finish time. Take each job provided it is compatible with the ones already taken.
  • 10. Time complexity Sorting the jobs in increasing order of their finish times takes O(n log n) time Consider the job with the earliest finish time and thereon include the jobs into the solution set that are compatible with the preceding one. This takes O(n) time So the total running time comes out to be O(n log n)