1 of 43

Simple Approximation Algorithm

344176

Sungjoo Ryu

2 of 43

Consents

  • Concept of scheduling problems(single machine, identical parallel machines)
  • Algorithm(based on linear programming)
  • Algorithm(based on network flow-Sidney decomposition)
  • Algorithm(round robin)-suggested
  • Preliminaries and notation
  • Non-clairvoyant scheduling on a single machine
  • Non-clairvoyant scheduling on identical parallel machines
  • Clairvoyant approximation algorithms(on a single machine)
  • Clairvoyant approximation algorithms(on identical parallel machines)
  • Conclusion

2

3 of 43

Scheduling problem�: single machine

  •  

3

4 of 43

Scheduling problem�: identical parallel machines

  •  

4

5 of 43

Algorithm�: based on a linear programming (A)

  •  

5

6 of 43

Algorithm�: based on a linear programming (B)

  • consider special LP relexation with only two variables in each constraints
  • each constraints can be solved by minimum capacity cut computation
  • apply list scheduling to the resulting LP completion times

6

7 of 43

Algorithm�: based on network flow (C), (D), (E)

  •  

7

8 of 43

Algorithm�: based on round-robin rule

  •  

8

9 of 43

Algorithm�: based on round-robin rule

  • results�1. get simpler and faster algorithm for clairvoyant precedence-constrained scheduling�2. get improved competitive ratios for non-clairvoyant scheduling with precedence constraints�3. generalize the algorithm for single and identical parallel machines(each algorithms were improved by 8-competitiveness, which has previously 4 and 6-competitiveness)

​

​

​

​

9

old new

 

 

 

 

weekly polynomial�(LP-based)

 

10 of 43

Algorithm�: based on round-robin rule

  • results�1. provide the old and new performance guarantees for non-clairvoyant scheduling�2. simple analysis� - single machine: not use any basis of theory� - identical parallel machines: only use network flow�

​

​

​

10

old new

 

 

2

4 2

8 2

​

2

6 3

8 3

​

11 of 43

Further related results

  •  

11

12 of 43

Further related results

  • For integral processing times, preemptive scheduling with precedence constraints is related to non-preemptive scheduling of precedence-constrained jobs with unit processing times.

​

12

13 of 43

Preliminaries and notation

  •  

13

14 of 43

Non-clairvoyant scheduling�: on a single machine

  • can let a tentative schedule, which can be updated whenever a job is completed in non-clairvoyant scheduling
  • tentative schedules process every job as a constant rate,�the rate is computed by algorithm 1
  • Algorithm 1 iterates all available jobs and assign to every jobs of its unassigned successors, each available job is processed at a rate proportional to the total weight of its assigned jobs

14

15 of 43

Non-clairvoyant scheduling�: on a single machine

  •  

15

16 of 43

Non-clairvoyant scheduling�: on a single machine

  •  

16

1

2

3

4

2

4

4

 

 

 

17 of 43

Non-clairvoyant scheduling�: on a single machine

  •  

17

18 of 43

Non-clairvoyant scheduling�: on a single machine

  •  

18

19 of 43

Non-clairvoyant scheduling�: on a single machine

19

20 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  • problem on identical machines: the total processing power of m cannot be divided among jobs(no job can be processed by more than one machine at the same time)
  • computing a parametric maximum flow in an extended network to solve

20

21 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  •  

21

22 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  •  

22

23 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  • Example 2

​

23

capacities

flows

minimum capacity cuts

processing rates

unavailable jobs

 

24 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  •  

24

1

2

3

5

4

4

3

5

6

▲the schedule for the instance 4 in example 2

25 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  •  

25

26 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  •  

26

27 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  •  

27

28 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  • Proof�

28

(6)

29 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  • Proof�

29

30 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  • Proof�

30

31 of 43

Non-clairvoyant scheduling�: on identical parallel machines

  • Proof�

31

32 of 43

Clairvoyant approximation algorithms�: on a single machine

  • Non-preemptive scheduling�can imply perform list scheduling in the order of the virtual completion times after computing the virtual preemptive schedule�compute completion time of preemptive schedule because it is not executed

🡪algorithm can be found on the next page

32

33 of 43

Clairvoyant approximation algorithms�: on a single machine

  •  

33

 

 

 

 

34 of 43

Clairvoyant approximation algorithms�: on a single machine

  •  

34

1

3

2

4

35 of 43

Clairvoyant approximation algorithms�: on a single machine

  •  

35

36 of 43

Clairvoyant approximation algorithms�: identical parallel machines

  •  

36

1

2

3

5

2

4

4

3

4

3

5

6

▲the schedule from algorithm 4 for example 2

37 of 43

Clairvoyant approximation algorithms�: identical parallel machines

  •  

37

38 of 43

Clairvoyant approximation algorithms�: identical parallel machines

  •  

38

 

 

 

 

 

39 of 43

Clairvoyant approximation algorithms�: identical parallel machines

  •  

39

 

 

40 of 43

A. Polynomial encoding Length

  • If algorithm 2 is applied to a single machine, it returns the same processing rate as algorithm 1.�Thus, also the virtual schedules computed in algorithms 3 and 4 coincide on a single machine.�It shows that the encoding length of numbers occurring in algorithm 4 is polynomially bounded.

40

41 of 43

A. Polynomial encoding Length

  •  

41

42 of 43

Conclusion

  • single machine scheduling�if precedence constraints exist, there is no approximation ratio that is less than 2.�else, same.�🡪It shows that there is 2-competitive non-clairvoyant algorithm.
  • identical parallel machines scheduling�The presented algorithm has the best known performance guarantee, but no matching lower bounds exist.�🡪remaining problem

42

43 of 43

Thank you

43