[go: up one dir, main page]
Scribd
Upload
24 views8 pages

Algorithm 7

The job sequencing problem aims to maximize profit by scheduling jobs within their deadlines. Each job has an associated deadline and profit, and not all jobs may be completed on time. The optimal solution involves ordering jobs by profit to ensure maximum earnings while adhering to deadlines.

Uploaded by

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

Algorithm 7

The job sequencing problem aims to maximize profit by scheduling jobs within their deadlines. Each job has an associated deadline and profit, and not all jobs may be completed on time. The optimal solution involves ordering jobs by profit to ensure maximum earnings while adhering to deadlines.

Uploaded by

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

Algorithm Design & Analysis

CSE 2103
Lecture 7
Job Sequencing with Deadline
2

In job sequencing problem, the objective is to


find a sequence of jobs, which is completed
within their deadlines and gives maximum
profit.
Let us consider, a set of n given jobs which are
associated with deadlines and profit is earned,
if a job is completed by its deadline. These jobs
need to be ordered in such a way that there is
maximum profit.
It may happen that all of the given jobs may
not be completed within their deadlines.
Job Sequencing with Deadline
3

Assume, deadline of ith job Ji is di and the


profit received from this job is pi. Hence, the
optimal solution of this algorithm is a feasible
solution with maximum profit.
Thus, D(i)>0 for 1⩽i⩽n.

profit, i.e. p1⩾p2⩾p3⩾...⩾pn.


Initially, these jobs are ordered according to
Job Sequencing with Deadline
4
Job Sequencing with Deadline
5
Job Sequencing with Deadline
6
Job Sequencing with Deadline
Algorithm
7
8

THANK YOU

You might also like