CS计算机代考程序代写 algorithm Microsoft PowerPoint - CSE101 2 Bin Packing und Scheduling.pptx

Microsoft PowerPoint – CSE101 2 Bin Packing und Scheduling.pptx

O. Braun

1Bin Packing

Bin Packing

O. Braun

2Bin Packing

Bin Packing

Minimizing the number of paper
rolls when cutting single lanes out
of it.

Minimizing the number of
containers needed to transport a
good.

Objects

Length/
Size/
Weight

4
3

Bin

O. Braun

3Bin Packing

Bin Packing

4
3

0 0

10 10

Objects

Bin

Here: 3 bins.
Is there a better
possibility?
Better =
„less bins“?

O. Braun

4Bin Packing

Bin Packing

4
3

0 0

10 10

0 0

Objects

Bin

Here: 3 bins.
Is there a better
possibility?
Better =
„less bins“?

O. Braun

5Bin Packing

Bin Packing

4
3

0 0

10 10

Lower Bound:
We need at least

bins.

0 0

Objects

Bin

O. Braun

6Bin Packing

First Fit

• Nine different groups of students want to go to a Baseball game.
• The groups consist of 4, 1, 2, 5, 3, 2, 3, 6, 3 persons.
• The buses have a maximum passenger capacity of 6 places.
• The groups want to stick together and are therefore not dividable.

First Fit: As long as there are enough places in a bus, fill the bus up with the next group.
Otherwise use a new bus. Start always with the first bus and proceed then to the next
bus and so on.

O. Braun

7Bin Packing

First Fit

A B C D E F G

1 2
3

3
5

3
4

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

8Bin Packing

First Fit

A B C D E F G

1 2
3

3
5

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

9Bin Packing

First Fit

A B C D E F G

2
3

3
5

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

10Bin Packing

First Fit

A B C D E F G

2
3

3
5

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

11Bin Packing

First Fit

A B C D E F G

2
3

4
2

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

12Bin Packing

First Fit

A B C D E F G

4
2

5
3

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

13Bin Packing

First Fit

A B C D E F G

4
2

5
3

2 2

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

14Bin Packing

First Fit

A B C D E F G

4
2

5
3

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

15Bin Packing

First Fit

A B C D E F G

4
2

5
3

6 6 6

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

16Bin Packing

First Fit

4
2

5
3

3
6

3
3

3 3

A B C D E F G

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

17Bin Packing

First Fit

4
2

5
3

3
6

A B C D E F G

First Fit: As long as there are enough places in a bus, fill the bus up with the next group. Otherwise use
a new bus. Start always with the first bus and proceed then to the next bus and so on.

O. Braun

18Bin Packing

First Fit Decreasing

First Fit Decreasing: First sort the groups in non‐increasing order. Then use First Fit.

O. Braun

19Bin Packing

First Fit Decreasing

1 2
3

3
5

3
4

A B C D E F G

O. Braun

20Bin Packing

First Fit Decreasing

A B C D E F G

1
2

3
5

3
4

O. Braun

21Bin Packing

First Fit Decreasing

A B C D E F G

1
2

3
5

3
4

O. Braun

22Bin Packing

First Fit Decreasing

A B C D E F G

1
2

3
4

O. Braun

23Bin Packing

First Fit Decreasing

A B C D E F G

1
2

O. Braun

24Bin Packing

First Fit Decreasing

A B C D E F G

1
2

33 2

5
4

3
3

O. Braun

25Bin Packing

First Fit Decreasing

A B C D E F G

1
2

5
4

3
3

O. Braun

26Bin Packing

First Fit Decreasing

A B C D E F G

1
2

5
4

3
3

O. Braun

27Bin Packing

First Fit Decreasing

A B C D E F G

1
2

5
4

2
2

O. Braun

28Bin Packing

First Fit Decreasing

A B C D E F G

6
5

4
3

2
2

2 2

O. Braun

29Bin Packing

First Fit Decreasing

A B C D E F G

6
5

4
3

2
2

O. Braun

30Bin Packing

First Fit Decreasing

A B C D E F G

6
5

4
3

2
2

O. Braun

31Bin Packing

Next Fit

Next Fit: Same as First Fit, but a bus leaves as soon as a group does not fit in it anymore.

O. Braun

32Bin Packing

Next Fit

1 2
3

3
5

3
4

O. Braun

33Bin Packing

Next Fit

2
3

3
5

O. Braun

34Bin Packing

Next Fit

2
3

3
5

4
2

O. Braun

35Bin Packing

Next Fit

2
3

4
2

O. Braun

36Bin Packing

Next Fit

1 2

4
2

O. Braun

37Bin Packing

Next Fit

1 2

5
3

4
2

O. Braun

38Bin Packing

Next Fit

1 2

5
3

4
2

O. Braun

39Bin Packing

Next Fit

1 2

3
5

3
4

O. Braun

40Bin Packing

Bin Packing

a) How would you define the problem?
Remember: A problem is defined by
• input domain / problem instance
• output specification

b) Howmany possible solutions are there? (now you need Counting…)

c) How would you develop a Complete Enumeration algorithm?

O. Braun

41Bin Packing

Bin Packing

a) How would you define the problem?
Remember: A problem is defined by
• input domain / problem instance binsize (10), A (6), B (3), C (4), D(3), E(4)
• output specification permutation of the jobs such that planning them

in this order will lead to the minimum
number of bins, here: A, C, B, D, E

b) Howmany possible solutions are there? (now you need Counting…)
e.g. n! permutations distributed with first fit (more precisely n!(n1! * … *nk!) when
there are n1 objects with the same size s1, …, nk objects with the same size sk and
n1=…=nk)

c) How would you develop a Complete Enumeration algorithm?

O. Braun

42Bin Packing

Online vs. Offline algorithms

First Fit and Next Fit are ONLINE algorithms,
First Fit Decreasing is an OFFLINE algorithm as all objects must be known before the
algorithm starts sorting them.
Why could Next Fit make sense?
The bins (e.g. buses) are filled quite ok and can leave already and then return. Total
waiting time is reduced. Also e.g. good for liquidity reasons: items can be sold already
and the company does not have to wait until all objects are produced.

O. Braun

43Bin Packing

Next Fit – Worst‐Case‐Analysis

Next Fit requires up to about 100% bins more than the optimal solution does.

Find a problem instance where Next Fit behaves that bad in comparison to the optimal
solution.

O. Braun

44Bin Packing

Next Fit – Worst‐Case‐Analysis

Bin size: 100
100 x „1“
99 x „100“
in the order 1, 100, 1, 100, …, 1, 100, 1

Next Fit:
Bin 1 Bin 2 Bin 3 … Bin 197 Bin 198 Bin 199
1 100 1 1 100 1

Optimal:
Bin 1 Bins 2‐100
100x“1“ 1x“100“

NF/OPT = 199/100 = 1.99

O. Braun

45Bin Packing

Next Fit – Worst‐Case‐Analysis

This example has to be generalized for an arbitrary large number of objects.
Let  be chosen to be a sufficiently small positive real number.
Bin size: 1. Objects:
n objects of size  and n‐1 objects of size 1.
NF: (,1, ,1,…, ,1,)

n bins packed with []
n‐1 bins packed with [1]
 2n‐1 bins

OPT: (,…, ,1,…, 1)
1 bin packed with [,…,]
n‐1 bins packed with [1]
 n bins

NF/OPT = (2n‐1)/n = 2‐1/n

O. Braun

46Bin Packing

First Fit – Worst‐Case‐Analysis

First Fit requires up to about 70% bins more than the optimal solution does.

Find a problem instance where First Fit behaves that bad in comparison to the optimal
solution.

O. Braun

47Bin Packing

First Fit – Worst‐Case‐Analysis

Bin size: 1000
6 x „501“
6 x „334“
6 x „165“

First Fit:
Bin 1 Bins 2‐4 Bins 5‐10
6x“165“ 2x“334“ 1x“501“

Optimal:
Bins 1‐6
501
334
165

FF/OPT = 10/6 = 1.67

This example has to
be generalized for an
arbitrary number of
objects!

O. Braun

48Bin Packing

Fist Fit – Worst‐Case‐Analysis

This example has to be generalized for an arbitrary large number of objects.
Let  be chosen to be a sufficiently small positive real number.
Bin size: 1. Objects:
6n objects of size 3/6+ = 1/2+
6n objects of size 2/6+ = 1/3+
6n objects of size 1/6‐2 = 1/6‐2

FF:  (1/6‐2,…,1/6‐2,1/3+,…,1/3+,1/2+,…,1/2+)
n   bins packed with 6 items of size [1/6‐2] in each bin
3n  bins packed with 2 items of size [1/3+]  in each bin
6n  bins packed with 1 item  of size [1/2+]  in each bin
 10n bins

OPT: (1/2+,1/3+,1/6‐2,…,1/2+,1/3+,1/6‐2)
6n bins packed with [1/2+,1/3+,1/6‐2] in each bin
 6n bins

FF/OPT = (10n)/(6n) = 5/3 = 1.67

O. Braun

49Bin Packing

First Fit – Worst‐Case‐Analysis

Bin size: 1000
10x [501]
10x [334]
3x [165]
7x [110]
7x [55]

First Fit:
Bin 1 Bin 2 Bins 3‐7 Bins 8‐17
7x[55] 2x[110] 2x[334] 1x[501]
5x[110] 3x[165]

Optimal:
Bins 1‐3 Bins 4‐10
501 501
334 334
165 110

55
FF/OPT = 17/10 = 1.7

This example has to
be generalized for an
arbitrary number of
objects!

O. Braun

50Bin Packing

Fist Fit – Worst‐Case‐Analysis

This example has to be generalized for an arbitrary large number of objects. Let  be
chosen to be a sufficiently small positive real number.
Bin size: 1. Objects:
10n objects of size 3/6+ = 1/2+
10n objects of size 2/6+ = 1/3+
3n objects of size 1/6‐2
7n objects of size 2/18‐ = 1/9‐
7n objects of size 1/18‐ = 1/18‐

FF: (1/18‐,…,1/18‐,2/18‐,…,2/18‐,1/6‐2,…,1/6‐2,2/6+,…,2/6+,3/6+,…,3/6+)
n   bins packed w. 7 items of s. [1/18‐] and 5 items of s. [2/18‐]  in each bin
n   bins packed w. 2 items of s. [2/18‐] and 3 items of s. [3/18‐2] in each bin
5n  bins packed w. 2 items of s. [1/3+] in each bin
10n bins packed w. 1 item of s. [1/2+] in each bin
 17n bins

OPT: (1/2+,1/3+,1/6‐2,…,1/2+,1/3+,1/6‐2
1/2+,1/3+,1/9‐,1/18‐,…, 1/2+,1/3+,1/9‐,1/18‐)

3n bins packed with [3/6+,2/6+,1/6‐2] in each bin
7n bins packed with [9/18+,6/18+,2/18‐,1/18‐] in each bin
 10n bins

FF/OPT = (17n)/(10n) = 17/10 = 1.7

O. Braun

51Bin Packing

First Fit Decreasing – Worst‐Case‐Analysis

First Fit Decreasing requires up to about 22% bins more than the optimal solution does.

Find a problem instance where First Fit Decreasing behaves that bad in comparison to the
optimal solution.

O. Braun

52Bin Packing

First Fit Decreasing – Worst‐Case‐Analysis

O. Braun

53Bin Packing

First Fit Decreasing – Worst‐Case‐Analysis

O. Braun

54Bin Packing

First Fit Decreasing – Worst‐Case‐Analysis

Bin size: 1000
6x [501]
6x [252]
6x [251]
12x [248]

First Fit Decreasing:
Bins 1‐6 Bins 7‐8 Bins 9‐11
[501] 3x[251] 4x[248]
[252]

Optimal:
Bins 1‐6 Bins 7‐9
[501] 2x[252]
[251] 2x[248]
[248]

FFD/OPT = 11/9 = 1.22

This example has to
be generalized for an
arbitrary number of
objects!

O. Braun

55Bin Packing

Fist Fit Decreasing – Worst‐Case‐Analysis

This example has to be generalized for an arbitrary large number of objects. Let  be
chosen to be a sufficiently small positive real number.
Bin size: 1. Objects:
6n+4 objects of size [1/2+
6n+4 objects of size [1/4+2
6n+4 objects of size [1/4+

12n+8 objects of size [1/4‐2

FFD: 6n+4 bins packed with [1/2+1/4+2]
2n+1 bins packed with [1/4+,1/4+,1/4+
1 bin packed with [1/4+1/4‐21/4‐21/4‐2]
3n+1 bins packed with 4x[1/4‐2]
1 bin packed with [1/4‐2]

 11n+8 bins

OPT: 6n+4 bins packed with [1/2+1/4+,1/4‐2]
3n+2 bins packed with [1/4+21/4+2,1/4‐2,1/4‐2]

 9n+6 bins

FF/OPT = (11n+8)/(9n+6) = 11/9

O. Braun

56Bin Packing

Bin Packing for experts

Develop your own Bin Packing algorithm.

Work out some problem instances that show how your algorithm works.

Analyze your algorithm‘s worst‐case behavior.

O. Braun

57Scheduling

Scheduling

O. Braun

58Scheduling

Scheduling

parallel, identical
processors

P1
P2

t0 1 2 3 4 5 6 7 8 9 10 11 12

Scheduling
Processors

Objectives

• preemptive
• offline
• online

minimizing the
makespan

J1
J3

J2
J2

Jobs

P1
P2

t0 1 2 3 4 5 6 7 8 9 10 11 12

J1
J2+J3J1

O. Braun

59Scheduling

Scheduling models: 3‐fields‐notation

Processor models:
1 Single Processor Scheduling
P Parallel Processor Scheduling (parallel, identical processors)
F Flow Shop Scheduling
J Job Shop Scheduling

Jobs:
pmtn preemptive (a job can be interrupted at any time on any pocessor and resumed later on

the same or any other processor without any additional (setup) time costs)

Optimization goals (here: all are minimization goals):
Cmax makespan = maximum completion time of a job
Cj sum of the completion times
Lmax maximum lateness of a job
Uj number of delayed jobs
Tj sum of tardiness of all jobs

O. Braun

60Scheduling

Scheduling‐Models and 3‐Fields‐Notation
Processors Optimization Goal Algorithm Running

Time
Worst-case
(*=optimal)

1
(single processor)

min. makespan Cmax any active schedule polynomial *
min. sum of completion times ∑Cj SPT polynomial *
min. maximum lateness Lmax Earliest Due Date polynomial *
min. number of delayed jobs ∑Uj Moore polynomial *
min. sum of tardiness of delayed jobs ∑Tj n! permutations exponential *

P
(parallel,
identical
processors)

min. makespan (preemptions allowed) Cmax Mc Naughton polynomial *
min. sum of completion times ∑Cj SPT polynomial *

min. makespan (no preemptions allowed) Cmax n! permutations exponential *

List Scheduling polynomial 2 – 1/m
(Graham)

LPT polynomial 4/3 – 1/(3m)
(Graham)

F
(Flow-Shop)

min. makespan (with 2 processors) Cmax Johnson polynomial *

min. makespan (>3 processors) Cmax n! permutations exponential *

J
(Job-Shop)

min. makespan (with 2 processors and max. 2 stations) Cmax Jackson polynomial *

min. makespan (>3 processors) Cmax n! permutations exponential *

Giffler/Thompson polynomial

O. Braun

61Scheduling

Parallel Processor
Scheduling

O. Braun

62Scheduling

P|pmtn|Cmax: McNaughton

• processing of the jobs can be interrupted

• continue to work on the jobs after an interruption is

possible

… on any processor (including the same)

… at any time

…without any time penalty (like setup costs)

P1
P2
P3
P4
P5

0 1 2 3 4 5 6 7 8 9 10 11

max max: max ,
jp pC p

m


  
  

  



O. Braun

63Scheduling

Approximation algorithms for P||Cmax

P3
0 1 2 3 4 5 6

C DA B E

pA=2 pB=2 pC=1 pD=1 pE=3

0 1 2 3 4 5 6

P3
0 1 2 3 4 5 6

0 1 2 3 4 5 6

P3
0 1 2 3 4 5 6

0 1 2 3 4 5 6

List Scheduling LPT SPT

List Scheduling: Take the next job from the list,
schedule this job on that processor that has
done the least amount of work so far (if there
are more than one of such processors, take
that with the smallest index) – „utilization
principle“.
LPT: sort before in non‐increasing order
SPT: sort before in non‐decreasing order

O. Braun

64Scheduling

Example

Schedule the following n=8 jobs on m=3 parallel processors.

a) Use McNaughton‘s algorithm. What is Cmax and what is Cj? Reason why McNaughton constructs always
optimal schedules for makespan optimization on parallel processors when preemptions are allowed.

In the following there are no preemptions allowed, obeye the utilization principle.
b) Draw the LPT schedule as a Gantt-Chart. What is Cmax and what is Cj ?
c) Draw the SPT schedule as a Gantt-Chart. What is Cmax and what is Cj ?
d) Find the list that leads to the schedule with minimum makespan. Draw the Gantt-Chart.
e) Find the list that leads to the schedule with minimum sum of completion times. Draw the Gantt-Chart.
f) Find the list that leads to the schedule with maximum makespan. Draw the Gantt-Chart.
g) Find the list that leads to the schedule with maximum sum of completion times. Draw the Gantt-Chart.

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

O. Braun

65Scheduling

Example

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

a) Use McNaughton‘s algorithm. What is Cmax and what is Cj? Reason why McNaughton constructs
always optimal schedules for makespan optimization on parallel processors when preemptions are
allowed.

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

O. Braun

66Scheduling

Solution

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Cj=71

(not 74!)

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

a) Use McNaughton‘s algorithm. What is Cmax and what is Cj? Reason why McNaughton constructs
always optimal schedules for makespan optimization on parallel processors when preemptions are
allowed.

O. Braun

67Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

b) Draw the LPT schedule as a Gantt-Chart. What is Cmax and what is Cj ?

O. Braun

68Scheduling

Solution

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Lower Bound:
max{9, 36/3} = 12
 LPT is optimal.

Cj=76

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

b) Draw the LPT schedule as a Gantt-Chart. What is Cmax and what is Cj ?

O. Braun

69Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

c) Draw the SPT schedule as a Gantt-Chart. What is Cmax and what is Cj ?

O. Braun

70Scheduling

Solution

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

c) Draw the SPT schedule as a Gantt-Chart. What is Cmax and what is Cj ?

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Cj=19+26+11=56

O. Braun

71Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

d) Find the list that leads to the schedule with minimum makespan. Draw the Gantt-Chart.

O. Braun

72Scheduling

Solution

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Lower Bound:
max{9, 36/3} = 12

The LPT schedule
is the optimal schedule
in this specific case.

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

d) Find the list that leads to the schedule with minimum makespan. Draw the Gantt-Chart.

O. Braun

73Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

e) Find the list that leads to the schedule with minimum sum of completion times. Draw the Gantt-
Chart.

O. Braun

74Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

SPT-schedule
is always optimal
forminimizing
sum of completion
times (with parallel
processors).

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

e) Find the list that leads to the schedule with minimum sum of completion times. Draw the Gantt-
Chart.

O. Braun

75Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

f) Find the list that leads to the schedule with maximum makespan. Draw the Gantt-Chart.

O. Braun

76Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

f) Find the list that leads to the schedule with maximum makespan. Draw the Gantt-Chart.

O. Braun

77Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

g) Find the list that leads to the schedule with maximum sum of completion times.
Draw the Gantt-Chart.

O. Braun

78Scheduling

Example

P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

As SPT is optimal,
LPT must be worst.

3 ZEA

B 4 ZE

C 7 ZE

D 3 ZE

E 5 ZE

F 3 ZE

G 9 ZE

2 ZEH

g) Find the list that leads to the schedule with maximum sum of completion times.
Draw the Gantt-Chart.

O. Braun

79Scheduling

Worst‐case
Analysis

O. Braun

80Scheduling

Ron Graham

• 1999 Professor at UCSD:
CSE & Math Department

• Chief Scientist:
California Institute for
Telecommunications
and Information Technology
(Calit2, Qualcomm Institute)

Check out these websites:
• http://www.math.ucsd.edu/~fan/ron/
• https://vimeo.com/136044050
• https://www.simonsfoundation.org/

science_lives_video/ronald‐graham/

O. Braun

81Scheduling

• 10/31/1935

• 1962 PhD in Mathematics (UC Berkeley)

• Chief Scientist Bell Labs (AT&T) (37 years)

• married to Fan Chung (Professor in the Math department at UCSD) since 1983

• Euler Medal (1994)

• Steele Prize (2003)

Ron Graham

Worst-case
analysis

O. Braun

82Scheduling

Ron Graham

• President of the
International Jugglers Association

• Show im Cirque Du Soleil

O. Braun

83Scheduling

Ron Graham

O. Braun

84Scheduling

List Scheduling for P||Cmax

C DA B E
P1

P1
P2
P3

50 1 2 3 4 50 1 2 3 4

Schedule IISchedule I

O. Braun

85Scheduling

List Scheduling for P||Cmax

C DA B E

Schedule IISchedule I

P1
P2
P3

50 1 2 3 4 50 1 2 3 4

A bad List‐Schedule can roughly be up to 2 times longer than an optimal schedule.

Graham, R.L., Bounds for certain multiprocessing anomalies, Bell System
Technical Journal 45, 1563–1581, 1966

O. Braun

86Scheduling

Worst‐case analysis of List Scheduling

Graham, R.L., Bounds for certain multiprocessing anomalies, Bell System
Technical Journal 45, 1563–1581, 1966

O. Braun

87Scheduling

Worst‐case analysis of List Scheduling

Graham, R.L., Bounds for certain multiprocessing anomalies, Bell System
Technical Journal 45, 1563–1581, 1966

O. Braun

88Scheduling

Worst‐case analysis of List Scheduling

Graham, R.L., Bounds for certain multiprocessing anomalies, Bell System
Technical Journal 45, 1563–1581, 1966

O. Braun

89Scheduling

Worst‐case analysis of List Scheduling

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

take the longest job out
and schedulue all other
jobs optimally

then schedule the longest job:
it will never start later than
sum of all other processing times / m
(here: 27 / 3 = 9)

Upper Bound for sk:

O. Braun

90Scheduling

Worst‐case analysis of List Scheduling

O. Braun

91Scheduling

Ron Graham

The world has lost a great mathematician in person of Ron Graham.

Ron Graham passed away on Monday evening, 6th of July 2020 at the age of 84.

O. Braun

92Scheduling

Ron Graham

O. Braun

93Scheduling

LPT for P||Cmax

A B C

D E F G

P1
P2
P3

50 1 2 3 4 116 7 8 9 10

P1
P2
P3

50 1 2 3 4 116 7 8 9 10

Schedule I Schedule II

LPT: Longest Processing
Time first (d.h. sort the
jobs from large to small –
largest first, smallest last.
If two jobs are equal
schedule that with the
smaller index first.)

O. Braun

94Scheduling

LPT for P||Cmax

P1
P2
P3

50 1 2 3 4 116 7 8 9 10

P1
P2
P3

50 1 2 3 4 116 7 8 9 10

Schedule I Schedule II

A B C

D E F G

A bad LPT‐Schedule can be roughly up to 4/3 times longer than an optimal schedule.

Graham, R.L., Bounds on multiprocessing timing anomalies, SIAM Journal on
Applied Mathematics 17, 416–429, 1969

LPT: Longest Processing
Time first (d.h. sort the
jobs from large to small –
largest first, smallest last.
If two jobs are equal
schedule that with the
smaller index first.)

O. Braun

95Scheduling

Worst‐case analysis of LPT

Graham, R.L., Bounds on multiprocessing timing anomalies, SIAM Journal on
Applied Mathematics 17, 416–429, 1969

O. Braun

96Scheduling

Worst‐case analysis of LPT

Graham, R.L., Bounds on multiprocessing timing anomalies, SIAM Journal on
Applied Mathematics 17, 416–429, 1969

O. Braun

97Scheduling

Single‐Processor
Scheduling

O. Braun

98Scheduling

Single‐Processor Scheduling

min. maximum lateness Lmax Lj = Cj – dj
Earliest Due Date

min. number of delayed jobs ∑Uj Uj={1, if Lj > 0; 0, otherwise
Moore

min. sum of delays ∑Tj Tj=max{Lj,0}
(Greedy) Heuristics
Complete Enumeration
Branch-And-Bound

O. Braun

99Scheduling

min. maximum lateness (Lmax)

A B C D E
pj 7 8 10 6 4
dj 2 14 6 8 18

0 7 15 25 31 35

A B C D E

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

O. Braun

100Scheduling

min. maximum lateness (Lmax)

A B C D E
pj 7 8 10 6 4
dj 2 14 6 8 18
Cj 7 15 25 31 35
Lj 5 1 19 23 17

Just scheduled in that order would give:
Lmax=23 (job D)

0 7 15 25 31 35

A B C D E

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

O. Braun

101Scheduling

min. maximum lateness (Lmax)

A B C D E
pj 7 8 10 6 4
dj 2 14 6 8 18

0 7 15 25 31 35

A B C D E

A C D B E
pj 7 10 6 8 4
dj 2 6 8 14 18
Cj 7 17 23 31 35
Lj 5 11 15 17 17 Lmax=17 (job B or job E)

EDD is optimal for 1 | | Lmax

0 7 17 23 31 35

A C D B E

Earliest Due Date (EDD) algorithm:

Order the jobs by nondecreasing due dates
(breaking ties alphabetically) and
schedule in that order.

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

O. Braun

102Scheduling

Theorem: EDD is optimal for 1||Lmax

O. Braun

103Scheduling

min. maximum lateness (Lmax)

A B C D E
pj 4 3 8 1 7
dj 6 10 3 3 14

0 4 7 15 16 23

A B C D E

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

O. Braun

104Scheduling

min. maximum lateness (Lmax)

A B C D E
pj 4 3 8 1 7
dj 6 10 3 3 14
Cj 4 7 15 16 23
Lj -2 -3 12 13 9

Just scheduled in that order would give:
Lmax=13 (job D)

0 4 7 15 16 23

A B C D E

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

O. Braun

105Scheduling

min. maximum lateness (Lmax)

A B C D E
pj 4 3 8 1 7
dj 6 10 3 3 14

0 4 7 15 16 23

A B C D E

C D A B E
pj 8 1 4 3 7
dj 3 3 6 10 14
Cj 8 9 13 16 23
Lj 5 6 7 6 9 Lmax=9 (job E)

EDD is optimal for 1 | | Lmax

0 8 9 13 16 23

C D A B E

Earliest Due Date (EDD):

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

O. Braun

106Scheduling

Single processor scheduling

min. maximum lateness Lmax Lj = Cj – dj
Earliest Due Date

min. number of delayed jobs ∑Uj Uj={1, if Lj > 0; 0, otherwise
Moore

min. sum of delays ∑Tj Tj=max{Lj,0}
(Greedy) Heuristics
Complete Enumeration
Branch-And-Bound

O. Braun

107Scheduling

Moore‐Hodgson Algorithm

Moore‐Hodgson Algorithm.
• Schedule jobs in ascending order of

due dates.
• If in scheduling job j we encounter a

due date violation,
then delete from among the jobs in
the schedule (including job j ) the one
with the largest processing time.

• Ties are broken alphabetically.
• All deleted jobs are scheduled at the

end, after the on‐time jobs.

O. Braun

108Scheduling

min. number of delayed jobs ∑Uj with Uj={1, if Lj > 0; 0, otherwise

C D A B E

Moore‘s algorithm starts with Earliest Due Date (EDD):

dj 3 3 6 10 14

A B C D E
pj 4 3 8 1 7
dj 6 10 3 3 14

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

O. Braun

109Scheduling

Lj 5
0 8

C D A B E
dj 3

A B C D E
pj 4 3 8 1 7
dj 6 10 3 3 14

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

min. number of delayed jobs ∑Uj with Uj={1, if Lj > 0; 0, otherwise

O. Braun

110Scheduling

Lj 5
0 8

C D A B E
dj 3

D A B E C

A B C D E
pj 4 3 8 1 7
dj 6 10 3 3 14

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

min. number of delayed jobs ∑Uj with Uj={1, if Lj > 0; 0, otherwise

Lj -2 -1 -2 1
0 1 5 8 15

D A B E C
dj 3 6 10 14

O. Braun

111Scheduling

Lj 5
0 8

C D A B E
dj 3

Lj -2 -1 -2 1
0 1 5 8 15

D A B E C
dj 3 6 10 14

A B C D E
pj 4 3 8 1 7
dj 6 10 3 3 14

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

min. number of delayed jobs ∑Uj with Uj={1, if Lj > 0; 0, otherwise

E has the largest processing
time out of D, A, B, E

O. Braun

112Scheduling

Lj -2 -1 -2
0 1 5 8

D A B C E
dj 3 6 10

∑Uj=2 (jobs C, E)

A B C D E
pj 4 3 8 1 7
dj 6 10 3 3 14

Lj = Cj – dj
Uj = {1, if Lj > 0; 0, otherwise
Tj = max{Lj,0}

min. number of delayed jobs ∑Uj with Uj={1, if Lj > 0; 0, otherwise

Moore is optimal for 1 | | ∑Uj

Lj 5
0 8

C D A B E
dj 3

Lj -2 -1 -2 1
0 1 5 8 15

D A B E C
dj 3 6 10 14

O. Braun

113Scheduling

Correctness of the Moore‐Hodgson Algorithm

O. Braun

114Scheduling

Correctness of the Moore‐Hodgson Algorithm

O. Braun

115Scheduling

Example (Moore‐Hodgson)

O. Braun

116Scheduling

Example (Moore‐Hodgson)

O. Braun

117Scheduling

Example

Given:
A B C D

pj 12 8 15 9
dj 16 26 25 27

a) Determine the optimal schedule for 1||Lmax

b) Determine the optimal schedule for 1||∑Uj

c) Determine the optimal schedule for 1||∑Tj

O. Braun

118Scheduling

1||Lmax

Lj -4 2 9 17
0 12 27 35 44

A C B D

a) Earliest Due Date (EDD): A B C D
pj 12 8 15 9
dj 16 26 25 27

dj 16 25 26 27

Lmax=17 (job D)

O. Braun

119Scheduling

1||∑Uj

Lj -4 2
0 12 27

A C B D

b) Moore‘s algorithm: A B C D
pj 12 8 15 9
dj 16 26 25 27

dj 16 25

O. Braun

120Scheduling

1||∑Uj
b) Moore‘s algorithm: A B C D

pj 12 8 15 9
dj 16 26 25 27

Lj -4 -6 2
0 12 20 29

A B D C
dj 16 26 27

Lj -4 2
0 12 27

A C B D
dj 16 25

O. Braun

121Scheduling

1||∑Uj
b) Moore‘s algorithm: A B C D

pj 12 8 15 9
dj 16 26 25 27

Lj -4 -6 2
0 12 20 29

A B D C
dj 16 26 27

Lj -4 2
0 12 27

A C B D
dj 16 25

A has the largest processing
time out of A, B, D

O. Braun

122Scheduling

1||∑Uj
b) Moore‘s algorithm:

Job A is moved to the end

Lj -18 -10
0 8 17

B D C A
dj 26 27

∑Uj=2 (jobs A, C)

Lj -4 -6 2
0 12 20 29

A B D C
dj 16 26 27

Lj -4 2
0 12 27

A C B D
dj 16 25

A B C D
pj 12 8 15 9
dj 16 26 25 27

A has the largest processing time
Out of A, B, D!

O. Braun

123Scheduling

1 | | Tj Complete Enumeration

c) n! possible permutations

O. Braun

124Scheduling

1 | | Tj Complete Enumeration

( . , . , . , A)

44^16= 28

28+6= 34

( . , . , B, A)

32^26= 6

( . , C, B, A)

24^25= 0

( D, C, B, A)

9^27= 0

Tj 0 0 6 28
0 9 24 32 44

D C B A

dj 27 25 26 16

O. Braun

125Scheduling

1 | | Tj Complete Enumeration

( . , . , . , A)

44^16= 28

( . , . , . , A)

44^16= 28

34 34 35 35 33 33

28+6= 34 28+7= 35 28+5= 33

( . , . , B, A)

32^26= 6

( . , C, B, A)

24^25= 0

( D, C, B, A)

9^27= 0

( . , D, B, A)

24^27= 0

( C, D, B, A)

15^25= 0

( . , . , C, A)

32^25= 7

( . , B, C, A)

17^26= 0

( D, B, C, A)

9^27= 0

( . , D, C, A)

17^27 = 0

( B, D, C, A)

8^26= 0

( . , . , D, A)

32^27= 5

( . , B, D, A)

23^26= 0

( C, B, D, A)

15^25= 0

( . , C, D, A)

23^25= 0

( B, C, D, A)

8^26= 0

O. Braun

126Scheduling

1 | | Tj Complete Enumeration

( . , . , . , B)

44^26= 18

38 38 34 29 38 29

18+20= 38 18+11= 29 18+9= 27

( . , . , A, B)

36^16= 20

( . , C, A, B)

24^25= 0

( D, C, A, B)

9^27= 0

( . , D, A, B)

24^27= 0

( C, D, A, B)

15^25= 0

( . , . , C, B)

36^25= 11

( . , A, C, B)

21^16= 5

( D, A, C, B)

9^27= 0

( . , D, C, B)

21^27 = 0

( A, D, C, B)

12^16= 0

( . , . , D, B)

36^27= 9

( . , A, D, B)

27^16= 11

( C, A, D, B)

15^25= 0

( . , C, D, B)

27^25= 2

( A, C, D, B)

12^16= 0

O. Braun

127Scheduling

1 | | Tj Complete Enumeration

( . , . , . , C)

44^25= 19

32 32 27 22 25 21

19+13= 32 19+3= 22 19+2= 21

( . , . , A, C)

29^16= 13

( . , B, A, C)

17^26= 0

( D, B, A, C)

9^27= 0

( . , D, A, C)

17^27= 0

( B, D, A, C)

8^26= 0

( . , . , B, C)

29^26= 3

( . , A, B, C)

21–16= 5

( D, A, B, C)

9^27= 0

( . , D, B, C)

21^27 = 0

( A, D, B, C)

12^16= 0

( . , . , D, C)

29^27= 2

( . , A, D, C)

20^16= 4

( B, A, D, C)

8^26= 0

( . , B, D, C)

20^26= 0

( A, B, D, C)

12^16= 0

O. Braun

128Scheduling

1 | | Tj Complete Enumeration

( . , . , . , D)

44^27= 17

36 36 37 28 31 27

17+19= 36 17+9= 26 17+10= 27

( . , . , A, D)

35^16= 19

( . , B, A, D)

23^26= 0

( C, B, A, D)

15^25= 0

( . , C, A, D)

23^25= 0

( B, C, A, D)

8^26= 0

( . , . , B, D)

35^26= 9

( . , A, B, D)

27^16= 11

( C, A, B, D)

15^25= 0

( . , C, B, D)

27^25 = 2

( A, C, B, D)

12^16= 0

( . , . , C, D)

35^25= 10

( . , A, C, D)

20^16= 4

( B, A, C, D)

8^26= 0

( . , B, C, D)

20^26= 0

( A, B, C, D)

12^16= 0

O. Braun

129Scheduling

1 | | Tj Complete Enumeration

Optimal solution:

Tj 0 0 2 19
0 12 20 29 44

A B D C

dj 16 26 27 25

∑Tj=21

∑Uj=2 (Jobs C, D)

Lmax=19 (Job C)

O. Braun

130Scheduling

1 | | Tj Minimization Problem: Upper Bounds

1a. Compute a first upper bound (EDD):

Tj 0 2 9 17 ∑Tj=28
0 12 27 35 44

A C B D

dj 16 25 26 27

1b. Compute a second upper bound (SPT):

Tj 0 0 13 19 ∑Tj=32
0 8 17 29 44

B D A C

dj 26 27 16 25

28
Best

Upper
Bound

O. Braun

131Scheduling

1 | | Tj Minimization problem: Lower Bounds

2. Compute Lower Bounds:

A first lower bound:
• When A is scheduled as the last job, then we know that a smaller value than TA = 28 will not be possible.
• This lower bound might be improved (i.e. enlarged) as there might be delays of the preceding jobs

B, C, D .

We might improve (enlarge) this lower bound further (the first jobs might cause additional delays):
• d=27 = largest deadline of the remaining jobs B, C, D
• When we increase all deadlines of jobs B, C, D to d=27, then ∑Tj (j=B,C,D) will possible become

smaller, but it won‘t for sure increase.
• When all jobs have the same deadline d, then SPT gives the smallest possible total sum of delays ∑Tj
• The SPT-order is BDC with completion times 8, 17, 32 and tardinesses 0, 0, 5.

Result: Given that A is scheduled last, the total tardiness is for sure greater or equal to 28+5=33.

Tj 28
0 32 44

A
dj 16 sum of all processing times

job A‘s deadline

A is 44-16=28 days late

O. Braun

132Scheduling

1 | | Tj Branch-And-Bound A is last job

( . , . , . , A)

44^16= 28

( . , . , . , A)

44^16= 28

34 34 35 35 33 33

( . , . , B, A)

32^26= 6

( . , C, B, A)

24^25= 0

( D, C, B, A)

9^27= 0

( . , D, B, A)

24^27= 0

( C, D, B, A)

15^25= 0

( . , . , C, A)

32^25= 7

( . , B, C, A)

17^26= 0

( D, B, C, A)

9^27= 0

( . , D, C, A)

17^27 = 0

( B, D, C, A)

8^26= 0

( . , . , D, A)

32^27= 5

( . , B, D, A)

23^26= 0

( C, B, D, A)

15^25= 0

( . , C, D, A)

23^25= 0

( B, C, D, A)

8^26= 0

Tj 0 0 5 28

TA+∑Tj (j=B,C,D)=28+5=33 > 28

0 8 17 32 44

B D C A

dj 27 27 27 16
pj

O. Braun

133Scheduling

1 | | Tj Branch-And-Bound B is last job

Tj 0 0 9 18

TB+∑Tj (j=A,C,D)=18+9=27 < 28 Search strategy: DFS BFS Best First Search 0 9 21 36 44 D A C B dj 27 27 27 26 ( . , . , . , B) 44^26= 18 38 38 34 29 38 29 ( . , . , A, B) 36^16= 20 ( . , C, A, B) 24^25= 0 ( D, C, A, B) 9^27= 0 ( . , D, A, B) 24^27= 0 ( C, D, A, B) 15^25= 0 ( . , . , C, B) 36^25= 11 ( . , A, C, B) 21^16= 5 ( D, A, C, B) 9^27= 0 ( . , D, C, B) 21^27 = 0 ( A, D, C, B) 12^16= 0 ( . , . , D, B) 36^27= 9 ( . , A, D, B) 27^16= 11 ( C, A, D, B) 15^25= 0 ( . , C, D, B) 27^25= 2 ( A, C, D, B) 12^16= 0 28 O. Braun 134Scheduling 1 | | Tj Branch-And-Bound B is last job pj dj A 12 16 B 8 26 C 15 25 D 9 27 Tj 0 0 20 18 TA+TB+∑Tj (j=C,D)=38+0=38 > 28

0 9 24 36 44

D C A B

dj 27 27 16 26

( . , . , . , B)

44^26= 18

38 38 34 29 38 29

( . , . , A, B)

36^16= 20

( . , C, A, B)

24^25= 0

( D, C, A, B)

9^27= 0

( . , D, A, B)

24^27= 0

( C, D, A, B)

15^25= 0

( . , . , C, B)

36^25= 11

( . , A, C, B)

21^16= 5

( D, A, C, B)

9^27= 0

( . , D, C, B)

21^27 = 0

( A, D, C, B)

12^16= 0

( . , . , D, B)

36^27= 9

( . , A, D, B)

27^16= 11

( C, A, D, B)

15^25= 0

( . , C, D, B)

27^25= 2

( A, C, D, B)

12^16= 0

O. Braun

135Scheduling

1 | | Tj Branch-And-Bound B is last job

Tj 0 0 11 18

TC+TB+∑Tj (j=A,D)=29+0=29 > 28

0 9 21 36 44

D A C B

dj 27 27 25 26

( . , . , . , B)

44^26= 18

38 38 34 29 38 29

( . , . , A, B)

36^16= 20

( . , C, A, B)

24^25= 0

( D, C, A, B)

9^27= 0

( . , D, A, B)

24^27= 0

( C, D, A, B)

15^25= 0

( . , . , C, B)

36^25= 11

( . , A, C, B)

21^16= 5

( D, A, C, B)

9^27= 0

( . , D, C, B)

21^27 = 0

( A, D, C, B)

12^16= 0

( . , . , D, B)

36^27= 9

( . , A, D, B)

27^16= 11

( C, A, D, B)

15^25= 0

( . , C, D, B)

27^25= 2

( A, C, D, B)

12^16= 0

O. Braun

136Scheduling

1 | | Tj Branch-And-Bound B is last job

Tj 0 2 9 18

TD+TB+∑Tj (j=A,C)=27+2=29 > 28

0 12 27 36 44

A C D B

dj 25 25 27 26

( . , . , . , B)

44^26= 18

38 38 34 29 38 29

( . , . , A, B)

36^16= 20

( . , C, A, B)

24^25= 0

( D, C, A, B)

9^27= 0

( . , D, A, B)

24^27= 0

( C, D, A, B)

15^25= 0

( . , . , C, B)

36^25= 11

( . , A, C, B)

21^16= 5

( D, A, C, B)

9^27= 0

( . , D, C, B)

21^27 = 0

( A, D, C, B)

12^16= 0

( . , . , D, B)

36^27= 9

( . , A, D, B)

27^16= 11

( C, A, D, B)

15^25= 0

( . , C, D, B)

27^25= 2

( A, C, D, B)

12^16= 0

O. Braun

137Scheduling

1 | | Tj Branch-And-Bound C is last job

Tj 0 0 2 19

TC+∑Tj (j=A,B,D)=19+2=21 < 28 0 8 17 29 44 B D A C dj 27 27 27 25 ( . , . , . , C) 44^25= 19 32 32 27 22 25 21 ( . , . , A, C) 29^16= 13 ( . , B, A, C) 17^26= 0 ( D, B, A, C) 9^27= 0 ( . , D, A, C) 17^27= 0 ( B, D, A, C) 8^26= 0 ( . , . , B, C) 29^26= 3 ( . , A, B, C) 21–16= 5 ( D, A, B, C) 9^27= 0 ( . , D, B, C) 21^27 = 0 ( A, D, B, C) 12^16= 0 ( . , . , D, C) 29^27= 2 ( . , A, D, C) 20^16= 4 ( B, A, D, C) 8^26= 0 ( . , B, D, C) 20^26= 0 ( A, B, D, C) 12^16= 0 28 O. Braun 138Scheduling 1 | | Tj Branch-And-Bound C is last job pj dj A 12 16 B 8 26 C 15 25 D 9 27 Tj 0 0 13 19 TA+TC+∑Tj (j=B,D)=32+0=32 > 28

0 8 17 29 44

B D A C

dj 27 27 16 25

( . , . , . , C)

44^25= 19

32 32 27 22 25 21

( . , . , A, C)

29^16= 13

( . , B, A, C)

17^26= 0

( D, B, A, C)

9^27= 0

( . , D, A, C)

17^27= 0

( B, D, A, C)

8^26= 0

( . , . , B, C)

29^26= 3

( . , A, B, C)

21–16= 5

( D, A, B, C)

9^27= 0

( . , D, B, C)

21^27 = 0

( A, D, B, C)

12^16= 0

( . , . , D, C)

29^27= 2

( . , A, D, C)

20^16= 4

( B, A, D, C)

8^26= 0

( . , B, D, C)

20^26= 0

( A, B, D, C)

12^16= 0

O. Braun

139Scheduling

1 | | Tj Branch-And-Bound C is last job

Tj 0 0 3 19

TB+TC+∑Tj (j=A,D)=22+0=22 < 28 0 9 21 29 44 D A B C dj 27 27 26 25 ( . , . , . , C) 44^25= 19 32 32 27 22 25 21 ( . , . , A, C) 29^16= 13 ( . , B, A, C) 17^26= 0 ( D, B, A, C) 9^27= 0 ( . , D, A, C) 17^27= 0 ( B, D, A, C) 8^26= 0 ( . , . , B, C) 29^26= 3 ( . , A, B, C) 21–16= 5 ( D, A, B, C) 9^27= 0 ( . , D, B, C) 21^27 = 0 ( A, D, B, C) 12^16= 0 ( . , . , D, C) 29^27= 2 ( . , A, D, C) 20^16= 4 ( B, A, D, C) 8^26= 0 ( . , B, D, C) 20^26= 0 ( A, B, D, C) 12^16= 0 28 O. Braun 140Scheduling 1 | | Tj Branch-And-Bound C is last job pj dj A 12 16 B 8 26 C 15 25 D 9 27 Tj 0 5 3 19 TD+TA +TB+TC = 0+5+3+19=27 < 28 NEW BEST SOLUTION! 0 9 21 29 44 D A B C dj 27 16 26 25 ( . , . , . , C) 44^25= 19 32 32 27 22 25 21 ( . , . , A, C) 29^16= 13 ( . , B, A, C) 17^26= 0 ( D, B, A, C) 9^27= 0 ( . , D, A, C) 17^27= 0 ( B, D, A, C) 8^26= 0 ( . , . , B, C) 29^26= 3 ( . , A, B, C) 21–16= 5 ( D, A, B, C) 9^27= 0 ( . , D, B, C) 21^27 = 0 ( A, D, B, C) 12^16= 0 ( . , . , D, C) 29^27= 2 ( . , A, D, C) 20^16= 4 ( B, A, D, C) 8^26= 0 ( . , B, D, C) 20^26= 0 ( A, B, D, C) 12^16= 0 27 O. Braun 141Scheduling 1 | | Tj Branch-And-Bound C is last job pj dj A 12 16 B 8 26 C 15 25 D 9 27 Tj 0 0 3 19 TA+TD +TB+TC = 0+0+3+19=22 < 27 NEW BEST SOLUTION! 0 9 21 29 44 A D B C dj 16 27 26 25 ( . , . , . , C) 44^25= 19 32 32 27 22 25 21 ( . , . , A, C) 29^16= 13 ( . , B, A, C) 17^26= 0 ( D, B, A, C) 9^27= 0 ( . , D, A, C) 17^27= 0 ( B, D, A, C) 8^26= 0 ( . , . , B, C) 29^26= 3 ( . , A, B, C) 21–16= 5 ( D, A, B, C) 9^27= 0 ( . , D, B, C) 21^27 = 0 ( A, D, B, C) 12^16= 0 ( . , . , D, C) 29^27= 2 ( . , A, D, C) 20^16= 4 ( B, A, D, C) 8^26= 0 ( . , B, D, C) 20^26= 0 ( A, B, D, C) 12^16= 0 22 O. Braun 142Scheduling 1 | | Tj Branch-And-Bound C is last job pj dj A 12 16 B 8 26 C 15 25 D 9 27 Tj 0 0 2 19 TD+TC+∑Tj (j=A,B)=21+0=21 < 22 0 8 20 29 44 B A D C dj 26 26 27 25 ( . , . , . , C) 44^25= 19 32 32 27 22 25 21 ( . , . , A, C) 29^16= 13 ( . , B, A, C) 17^26= 0 ( D, B, A, C) 9^27= 0 ( . , D, A, C) 17^27= 0 ( B, D, A, C) 8^26= 0 ( . , . , B, C) 29^26= 3 ( . , A, B, C) 21–16= 5 ( D, A, B, C) 9^27= 0 ( . , D, B, C) 21^27 = 0 ( A, D, B, C) 12^16= 0 ( . , . , D, C) 29^27= 2 ( . , A, D, C) 20^16= 4 ( B, A, D, C) 8^26= 0 ( . , B, D, C) 20^26= 0 ( A, B, D, C) 12^16= 0 22 O. Braun 143Scheduling 1 | | Tj Branch-And-Bound C is last job pj dj A 12 16 B 8 26 C 15 25 D 9 27 Tj 0 4 2 19 TB+TA+TD+TC = 0+4+2+19=25 > 22

0 8 20 29 44

B A D C

dj 26 16 27 25

( . , . , . , C)

44^25= 19

32 32 27 22 25 21

( . , . , A, C)

29^16= 13

( . , B, A, C)

17^26= 0

( D, B, A, C)

9^27= 0

( . , D, A, C)

17^27= 0

( B, D, A, C)

8^26= 0

( . , . , B, C)

29^26= 3

( . , A, B, C)

21–16= 5

( D, A, B, C)

9^27= 0

( . , D, B, C)

21^27 = 0

( A, D, B, C)

12^16= 0

( . , A, D, C)

20^16= 4

( B, A, D, C)

8^26= 0

( . , B, D, C)

20^26= 0

( A, B, D, C)

12^16= 0

( . , . , D, C)

29^27= 2

O. Braun

144Scheduling

1 | | Tj Branch-And-Bound C is last job

Tj 0 0 2 19

TA+TB+TD+TC = 0+0+2+19=21 < 22 NEW BEST SOLUTION! 0 12 20 29 44 A B D C dj 16 26 27 25 ( . , . , . , C) 44^25= 19 32 32 27 22 25 21 ( . , . , A, C) 29^16= 13 ( . , B, A, C) 17^26= 0 ( D, B, A, C) 9^27= 0 ( . , D, A, C) 17^27= 0 ( B, D, A, C) 8^26= 0 ( . , . , B, C) 29^26= 3 ( . , A, B, C) 21–16= 5 ( D, A, B, C) 9^27= 0 ( . , D, B, C) 21^27 = 0 ( A, D, B, C) 12^16= 0 ( . , A, D, C) 20^16= 4 ( B, A, D, C) 8^26= 0 ( . , B, D, C) 20^26= 0 ( A, B, D, C) 12^16= 0 ( . , . , D, C) 29^27= 2 21 O. Braun 145Scheduling 1 | | Tj Branch-And-Bound D is last job Tj 0 0 9 17 TD+∑Tj (j=A,B,C)=17+9=26 > 21

0 8 20 35 44

B A C D

dj 26 26 26 27
pj

( . , . , . , D)

44^27= 17

36 36 37 28 31 27

( . , . , A, D)

35^16= 19

( . , B, A, D)

23^26= 0

( C, B, A, D)

15^25= 0

( . , C, A, D)

23^25= 0

( B, C, A, D)

8^26= 0

( . , . , B, D)

35^26= 9

( . , A, B, D)

27^16= 11

( C, A, B, D)

15^25= 0

( . , C, B, D)

27^25 = 2

( A, C, B, D)

12^16= 0

( . , . , C, D)

35^25= 10

( . , A, C, D)

20^16= 4

( B, A, C, D)

8^26= 0

( . , B, C, D)

20^26= 0

( A, B, C, D)

12^16= 0

O. Braun

146Scheduling

Comparison of optimal solutions

min. maximum lateness Lmax Lj = Cj – dj

min. number of delayed jobs ∑Uj Uj={1, if Lj > 0; 0, otherwise

min. sum of delays ∑Tj Tj=max{Lj,0}

Tj 0 0 2 19
0 12 20 29 44

A B D C

dj 16 26 27 25
Lmax=19 (job C)

∑Uj=2 (jobs C, D)

∑Tj=21

Lj -18 -10 7 28
0 8 17 32 44

B D C A
dj 26 27 25 16 Lmax=28 (job A)

∑Uj=2 (jobs A, C)

∑Tj=35

Lj -4 2 9 17
0 12 27 35 44

A C B D
dj 16 25 26 27 Lmax=17 (job D)

∑Uj=3 (jobs B, C, D)

∑Tj=28

Related Posts