Scribd
Upload
176 views24 pages

Job Sequencing With Deadline: Unit 3 Greedy Methods

The document describes the job sequencing problem with deadlines and the greedy algorithm approach. It involves scheduling n jobs on a single machine to maximize total profit while meeting all deadline constraints. The greedy algorithm selects the next highest profit job at each step if it does not violate feasibility. An example problem is provided and solved optimally with the greedy approach by processing jobs in order of decreasing profit and feasibility. The time complexity of the greedy algorithm is analyzed as O(n^2) in the worst case.

Uploaded by

sejal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
176 views24 pages

Job Sequencing With Deadline: Unit 3 Greedy Methods

The document describes the job sequencing problem with deadlines and the greedy algorithm approach. It involves scheduling n jobs on a single machine to maximize total profit while meeting all deadline constraints. The greedy algorithm selects the next highest profit job at each step if it does not violate feasibility. An example problem is provided and solved optimally with the greedy approach by processing jobs in order of decreasing profit and feasibility. The time complexity of the greedy algorithm is analyzed as O(n^2) in the worst case.

Uploaded by

sejal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 24

JOB SEQUENCING WITH

DEADLINE
UNIT 3
Greedy Methods
The problem is stated as below
• There are n jobs to be processed on a machine

• Each job i has a deadline di ≥ 0 and profit pi ≥ 0

• pi is earned iff the job is completed by its deadline

• To complete the job, it is processed in one machine for a unit of time.


• Only one machine is available for processing job

• Only one job is processed at a time on the machine.

• A feasible solution is a subset of job J such that each job


is completed by its deadline.

• An optimal solution is a feasible solution with a maximum


profit
• Greedy Algorithm is adopted to determine how the next job is
selected for an optimal solution.
This problem can be solved by greedy algorithm. For the optimal
solution, after choosing a job , it will add the next job to the subset
such that i € J ∑ pi , increases and resulting subset become feasible.

pi is the total profit of i th subset of jobs. In other words we have to


check all possible feasible subset J with their total profit value, for
a given set of jobs.
Feasible solution for a set of job J is such that, if the jobs of set J
can be processed in the order without violating any deadline then
J is a feasible solution.
Example :
Let ,
no. of job, n = 4 and
jobs are 1, 2, 3, 4
profit (p1,p2,p3,p4) = (100,10,15,27)
deadline (d1,d2,d3,d4) = (2,1,2,1).

Find the optimal solution set.


Feasible solutions profit (p1,p2,p3,p4) = (100,10,15,27)
deadline (d1,d2,d3,d4) = (2,1,2,1).
• Here solution 3 is optimal.

• The optimal solution is got by processing the job 1 and 4 in the order
job 4 followed by job 1.

• The maximum profit is 127. Thus, the job 4 begins at time zero and
job 1 end at time 2.
• Consider solution 3 i.e maximum profit job subset J = ( 1,4 )
Here , at first J= Ø and i € J ∑ pi=0.
Job 1 is added to J as it has the largest profit and is a feasible
solution.
Next add job 4 .Then also J = ( 1,4 ) is feasible because if the job
processes in the sequence ( 4,1 ) then job 4 will start in zero time
and job 1 will finish in 2 time within its deadline.
Next if job 3 is added then j=(1,3,4) is not feasible because all the
job 1,3,4 can not be completed within its deadline. So job 3 is not
added to the set. Similarly after adding job 2 J=(1,2,4) is not
feasible.
Hence J = ( 1,4 ) is a feasible solution set with maximum profit
127. This is an optimal solution
Algorithm 1
Gantt chart example job 3 [dead line 5](4to 5 ) and job 5 [deadline 4] (2to 3)

Job x Job y job5 jobz job3

0 time 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6
Job A Job B
P1 d 2 P2 d 3

Job A Job B Job C


P1 d 2 P2d3 P3 d 1

Job C Job A Job B


P3 d 1 P1 d 2 P2 d 3

Job C Job A Job B job D


P3 d 1 P1 d 2 P2 d 3 P4 d 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
COMPLEXITY ANALYSIS OF JS
ALGORITHM
Let n be the number of jobs and s be the number of
jobs included in the solution.
The loop between lines (the for-loop) is
iterated (n-1)times.
Each iteration takes O(k) where k is the number of
existing jobs.
The time needed by the algorithm is 0(sn) s <=n so
the worst case time is 0().
If di = n - i+1 1 <=i <= n, JS takes θ ().
time D and J need θ(s) amount of space.
Find the solution ?
Algorithm ???
• Faster
0 1 2 3 4 5 6
Job A Job B
P1 d 2 P2 d 3

Job C Job A Job B


P3 d 1 P1 d 2 P2d3

Job C Job A Job B job D


P3 d 1 P1 d 2 P2 d 3 P4 d 2

You might also like