04greedy-scheduling - Lecture notes 4-3 PDF

Preview

Summary

04greedy-scheduling - Lecture notes 4-3...

Description

Chapter 4 Greedy Algorithms

Slides prepared by A.Markopoulou for EECS215. Based on a set originally prepared by Kevin Wayne for Pearson-Addison Wesley. Copyright © 2005 All rights reserved.

1

Greedy Algorithm - Overview What is a greedy algorithm? An algorithm that locally (myopically) optimizes some measure at every step, on its way to the global solution. q

Greedy ordering - hard to define! No objective function, no precise definition.

Greedy algorithms are not always optimal. q

When they are, the problem has a special structure (optimal substructure+induction)

q

Even when they are not, they are often used as heuristics

How do we prove that a greedy algorithm finds an optimal solution? The greedy algorithm stays ahead

1.

q

We measure the progress (by some problem-specific measure) of Greedy at every step and we show that it is better than the progress of any other algorithm (including optimal)

Exchange argument (more general)

2.

q

Consider any optimal solution and gradually transform it into the greedy solution without hurting its quality

Structural Bound (even more general)

3.

2

Example Problems Interval Scheduling Greedy Stays Ahead, Exchange argument.

Interval Partitioning Structural Argument.

Minimizing Lateness Exchange Argument.

Common Themes: design (choice of greedy criterion), analysis, running time.

4.1 Interval Scheduling Interval scheduling. Job j starts at sj and finishes at fj. Two jobs compatible if they don't overlap. ■

■

■

Goal: find maximum subset of mutually compatible jobs.

a b c d e f g h 0

1

2

3

4

5

6

7

8

9

10

11

Time 4

Interval Scheduling: Greedy Algorithms Greedy template. Consider jobs in some order. Take each job provided it's compatible with the ones already taken. The challenge in designing a good greedy algorithm lies in identifying the right rule for greedy selection.

7

Interval Scheduling: Greedy Algorithms 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. –

Rationale: resource starts being used as quickly as possible

breaks earliest start time

8

Interval Scheduling: Greedy Algorithms 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. –

Rationale: resource starts being used as quickly as possible

[Shortest interval] Consider jobs in ascending order of interval length fj - sj. –

Rationale: use short jobs, to fit as many jobs as possible

breaks shortest interval

9

Interval Scheduling: Greedy Algorithms 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. –

Rationale: resource starts being used as quickly as possible

[Shortest interval] Consider jobs in ascending order of interval length fj - sj. –

Rationale: use short jobs, to fit as many jobs as possible

[Fewest conflicts] Consider jobs in ascending order of number of conflicts cj. –

Rationale: minimize conflicts to fit as many jobs as possible

breaks fewest conflicts

10

Interval Scheduling: Greedy Algorithms 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. –

Rationale: resource starts being used as quickly as possible

[Shortest interval] Consider jobs in ascending order of interval length fj - sj. –

Rationale: use short jobs, to fit as many jobs as possible

[Fewest conflicts] Consider jobs in ascending order of number of conflicts cj. –

Rationale: minimize conflicts to fit as many jobs as possible

[Earliest finish time] Consider jobs in ascending order of finish time fj. –

Rationale: scheduling one request, while ensuring that this request will finish as soon as possible

11

Interval Scheduling: Greedy Algorithm Greedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it is compatible with the ones already taken. §

Rationale: scheduling one request, while ensuring that this request will finish as soon as possible

Sort jobs by finish times so that f1 £ f2 £ ... £ fn. jobs selected

A ¬ f for j = 1 to n { if (job j compatible with A) A ¬ A È {j} } return A

Implementation details. ■

■

Remember job j* that was added last to A. Job j is compatible with A if sj ³ fj*.

12

Example – Revisited

A B C D E F G H 0

1

2

3

4

5

6

7

8

9

10

11

Time

13

Interval Scheduling: Demo B C A E D F G H

Time

0

1

2

3

4

5

6

7

8

9

10

11

0

1

2

3

4

5

6

7

8

9

10

11 14

Interval Scheduling: Demo B C A E D F G H 0

1

Time

2

3

4

5

6

7

8

9

10

11

2

3

4

5

6

7

8

9

10

11

B 0

1

15

Interval Scheduling: Demo B C A E D F G H 0

1

2

3

1

4

5

6

7

8

9

10

11

4

5

6

7

8

9

10

11

C

B 0

Time

2

3

16

Interval Scheduling: Demo B C A E D F G H 0

Time

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

A 0

17

Interval Scheduling: Demo B C A E D F G H 0

1

2

3

4

B 0

1

Time

5

6

7

8

9

10

11

5

6

7

8

9

10

11

E 2

3

4

18

Interval Scheduling: Demo B C A E D F G H 0

1

2

3

1

4

5

6

7

8

9

10

11

4

5

6

7

8

9

10

11

D

B 0

Time

2

3

19

Interval Scheduling: Demo B C A E D F G H 0

1

2

3

4

B 0

1

5

3

4

6

7

8

9

10

11

6

7

8

9

10

11

F

E 2

Time

5

20

Interval Scheduling: Demo B C A E D F G H 0

1

2

3

4

B 0

1

5

6

E 2

3

4

Time

7

8

9

10

11

7

8

9

10

11

G 5

6

21

Interval Scheduling: Demo B C A E D F G H 0

1

2

3

4

B 0

1

5

6

7

8

E 2

3

4

Time 9

10

11

9

10

11

H 5

6

7

8

22

Interval Scheduling: Analysis Approach Theorem. Greedy algorithm is optimal. Pf. Let OPT be one optimal solution. Let A be the solution found by greedy. §Note: It would be too much to require A=OPT. There may be many optimal solutions and we want to show that greedy finds one optimal solution. Approach 1: Analysis by a Greedy stays ahead argument. § show that |A|= |OPT| Approach 2: Analysis by an Exchange argument. § Start by OPT and transform it to A, without hurting its quality.

23

Interval Scheduling: a Greedy stays ahead argument Theorem. Greedy algorithm is optimal. Pf. Consider A (found by greedy) and OPT (one optimal solution). Enumerate the intervals: A={i1 £i2£ ...£ ik},OPT={j1£ j2£...£jm} We want to show that k=m. Greedy stays ahead: for all r£k: f(ir)£ f(jr) ■

■

■

■

Greedy:

ir-1

OPT:

■

ir ?

jr-1

–

By induction. True for r=1.

–

Assume it is true for r-1, i.e., f(ir-1)£f(jr-1)

–

OPT a compatible set, i.e., f(jr-1)£s(jr)

–

Therefore f(ir-1)£ s(jr).

jr

Greedy would have selected jr at the rth step unless f(ir)£f(jr).

This implies that k>=m. –

Indeed, f(ik)£f(jk). If m>k, then there exists jk+1 in OPT with f(ik) £ f(jk)£s(jk+1), and the greedy would have chosen it at step k+1. Contradiction. 24

Interval Scheduling: an Exchange argument Theorem. Greedy algorithm is optimal. Pf. (by contradiction) ■

■

■

Assume greedy is not optimal, and let's see what happens. Let i1, i2, ... ik denote set of jobs selected by greedy. Let j1, j2, ... jm denote set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r. job ir+1 finishes before jr+1

Greedy:

i1

i1

ir

OPT:

j1

j2

jr

ir+1

jr+1

...

why not replace job jr+1 with job ir+1? 25

Interval Scheduling: an Exchange argument Theorem. Greedy algorithm is optimal. Pf. (by contradiction) ■

■

■

Assume greedy is not optimal, and let's see what happens. Let i1, i2, ... ik denote set of jobs selected by greedy. Let j1, j2, ... jm denote set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r. job ir+1 finishes before jr+1

Greedy:

i1

i1

ir

ir+1

OPT:

j1

j2

jr

ir+1

...

solution still feasible and optimal, but contradicts maximality of r. 26

Interval Scheduling: Running Time Greedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it's compatible with the ones already taken. Sort jobs by finish times so that f1 £ f2 £ ... £ fn. A ¬ f for j = 1 to n { if (sj ³ fj*) A ¬ A È {j} j*=j } return A

Iclicker Question: Running Time? Answer:    

A: O(n) B: O(nlogn) C: O(n2) D: None of the above 27

Interval Scheduling: Running Time Greedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it's compatible with the ones already taken. Sort jobs by finish times so that f1 £ f2 £ ... £ fn. A ¬ f for j = 1 to n { if (sj ³ fj*) A ¬ A È {j} j*=j } return A

Running Time: O(nlogn) Input: s(i) and f(i) ■

■

■

O(nlogn) to: sort intervals by fi O(n): one pass through all intervals x constant time per interval

28

Variations and Related Problems

Online Interval Scheduling We dont know future intervals Weighted Interval Scheduling Intervals have weight and we want to maximize the total weight Interval Partitioning (or Interval Coloring) We want to schedule all intervals on the minimum number of resources

4.1 Interval Partitioning Interval partitioning. Lecture j starts at sj and finishes at fj. Goal: find minimum number of classrooms to schedule all lectures so ■

■

■

■

that no two occur at the same time in the same room. …or jobs and processors … or intervals and colors

Ex: This schedule uses 4 classrooms to schedule 10 lectures.

e c

j g

d b

h

a 9

9:30

f 10

10:30

11

11:30

12

12:30

1

1:30

i 2

2:30

3

3:30

4

4:30

Time 30

Interval Partitioning Interval partitioning. Lecture j starts at sj and finishes at fj. Goal: find minimum number of classrooms to schedule all lectures so ■

■

that no two occur at the same time in the same room. Ex: This schedule uses only 3.

c

d b

a 9

9:30

f

j

g

i

e 10

10:30

11

11:30

12

12:30

h 1

1:30

2

2:30

3

3:30

4

4:30

Time 31

Interval Partitioning: Lower Bound on Optimal Solution Def. The depth of a set of open intervals is the maximum number that contain any given time. Key observation. Number of classrooms needed ³ depth. Ex: Depth of schedule below = 3 Þ schedule below is optimal. q

This is a general way to prove optimality: show a structural bound for every feasible

solution and that our algorithm achieves the bound.

Q. Does there always exist a schedule equal to depth of intervals?

c

d b

a 9

9:30

f

j

g

i

e 10

10:30

11

11:30

12

12:30

h 1

1:30

2

2:30

3

3:30

4

4:30

Time 32

Interval Partitioning: Greedy Algorithm Greedy algorithm. Consider lectures in increasing order of start time: assign lecture to any compatible classroom.

Sort intervals by starting time so that s1 £ s2 £ ... £ sn. number of allocated classrooms (colors) d ¬ 0 for j = 1 to n if (lecture schedule else allocate schedule d ¬ d + }

{ j is compatible with some classroom k) lecture j in classroom k a new classroom d + 1 lecture j in classroom d + 1 1

Implementation. O(n log n). One pass (O(n)), ordering intervals by starting time (O(n log n)). For each classroom k, maintain the finish time of the last job added. [Keep the classrooms in a priority queue]. ■

■

■

33

Interval Partitioning: Greedy Analysis Observations. Greedy algorithm (1) schedules all classes to a classroom (2) never schedules two incompatible lectures in the same classroom (3)

Uses exactly depth labels/classrooms:

■

Let d = number of classrooms that the greedy algorithm allocates.

■

Classroom d is opened because we needed to schedule a job, say j, that is incompatible with all d-1 other classrooms.

■

Since we sorted by start time, all these incompatibilities are caused by lectures that start no later than sj.

■

Thus, we have d lectures overlapping at time sj + e.

Theorem. Greedy algorithm is optimal. Pf. Key observation Þ all schedules use ³ depth classrooms. ■

■

Greedy uses exactly d=depth classrooms 

35

So far: Greedy Algorithms Examples: Interval Scheduling: Greedy stays ahead+ exchange arguments+induction Interval Partitioning: Structural bounds

Common Themes: Design choice of greedy criterion/strategy Prove optimality greedy stays ahead, exchange argument, structural bound induction Running time O(n) steps + implementation details

36

4.2 Scheduling to Minimize Lateness

Demonstrates Exchange Arguments and Induction.

37

Scheduling to Minimizing Lateness Minimizing lateness problem. Single resource processes one job at a time. Job j requires tj units of processing time and is due at time dj. ■

■

If j starts at time sj, it finishes at time fj = sj + tj. Lateness: !j = max { 0, fj - dj }. Goal: schedule all jobs to minimize maximum lateness L = max !j.

■

■

■

1

2

3

4

5

6

tj

3

2

1

4

3

2

dj

6

8

9

9

14

15

Ex:

lateness = 2

d3 = 9 0

1

d2 = 8 2

d6 = 15 3

4

d1 = 6 5

6

7

max lateness = 6

lateness = 0

d5 = 14 8

9

10

d4 = 9 11

12

13

14

15

38

Minimizing Lateness: Greedy Algorithms Greedy template. Consider jobs in some order. ■

[Shortest processing time first] Consider jobs in ascending order of processing time tj.

■

■

[Earliest deadline first] Consider jobs in ascending order of deadline dj.

[Smallest slack] Consider jobs in ascending order of slack dj - tj.

39

Minimizing Lateness: Greedy Algorithms Greedy template. Consider jobs in some order. ■

[Shortest processing time first] Consider jobs in ascending order of processing time tj.

■

1

2

tj

1

10

dj

100

10

countere...