Scribd
Upload
6 views8 pages

Job Scheduling Algorithms Explained

The document discusses scheduling jobs at a campus xerox shop to maximize revenue. It introduces the problem, describes a brute force solution, and proposes using a greedy approach to sequentially allocate jobs to photocopiers. It notes some variations like machine speeds and costs that could impact the optimal solution.

Uploaded by

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

Job Scheduling Algorithms Explained

The document discusses scheduling jobs at a campus xerox shop to maximize revenue. It introduces the problem, describes a brute force solution, and proposes using a greedy approach to sequentially allocate jobs to photocopiers. It notes some variations like machine speeds and costs that could impact the optimal solution.

Uploaded by

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

NPTEL MOOC,JAN-FEB 2015

Week 1, Module 3

DESIGN AND ANALYSIS



OF ALGORITHMS

MADHAVAN MUKUND, CHENNAI MATHEMATICAL INSTITUTE


[Link]
Example 2: Xerox Shop

Campus Xerox has several photocopiers

Tomorrow is the deadline for BTech projects and


there is a rush of reports to be printed

How to schedule the pending jobs most


effectively?
Xerox Shop …
The number of pages for each job is known

Each customer has been promised delivery by a


deadline

Campus Xerox offers discount if deadline is not


met

How to sequentially allocate the jobs to


photocopiers to maximize revenue?
Xerox Shop …
Brute force

Try all possible allocations

Choose one that is optimum

Number of possibilities is exponential!

Even with 30 jobs, it would take hours to compute


an optimal schedule
Xerox Shop …

Decompose the problem

Choose a job to schedule first, and the machine


on which it will run, according to some strategy

Now, recursively solve the problem for N-1 jobs


Xerox Shop …
Greedy approach

Fix the choice of next job once and for all

Never go back and try another sequence

How to choose the next job?

Shortest processing time?

Earliest deadline?

How to show that this strategy is optimal?


Variations

Some photocopiers are old and slow, some are


new and fast

Time for a job depends on choice of machine

Cost of ink and paper varies across machines

Net revenue for a job depends on choice of


machine
Variations

Account for set up time between jobs

Need to reserve time slots to reload paper

Is there a valid greedy strategy?

You might also like