수업 Note_250414

프로젝트 설명

작업 할당 문제랑 유사
Metric 몇 개 있지만 가장 중요한 것은 Task Completion Rate (assumed energy limited case)
그 다음에 2순위가 Total Energy Consumption

Task 할당 문제 지속

	m0	m1	m2
t0	5	15	8
t1	6	18	20
t2	20	14	16
t3	8	10	13
t4	22	8	11
t5	15	9	12

Sufferage Algorithm
- Min-min과 유사함
- 모든 Task의 MTC(Minimum Completion Time)와 2번째 MCT를 찾고, 그 차이를 계산해서 가장 차이가 큰 task를 먼저 배정 (sufferage ; 손해)
- 먼저 task별 |MTC - MTC_2nd| 값을 구해보자
  
  1st iteration
  
  t0 t1 t2 t3 t4 t5
  
  Sufferage 3 12 2 2 3 3
  
  allocation m0
  - 실행시간 m0:6(t1), m1:0, m2:0
  2nd iteration (여기서부턴 누적시간)
  
  m0 m1 m2
  
  t0 5 + 6 15 8
  
  t2 20 + 6 14 16
  
  t3 8 + 6 10 13
  
  t4 22 + 6 8 11
  
  t5 15 + 6 9 12
  
  t0 t2 t3 t4 t5
  
  Sufferage 3 2 3 3 3
  
  allocation m2
  - 실행시간 m0:6(t1), m1:0, m2:8(t0)
  3rd iteration
  
  m0 m1 m2
  
  t2 20 + 6 14 16 + 8
  
  t3 8 + 6 10 13 + 8
  
  t4 22 + 6 8 11 + 8
  
  t5 15 + 6 9 12 + 8
  
  t2 t3 t4 t5
  
  Sufferage 8 4 11 11
  
  allocation m1
  - 실행시간 m0:6(t1), m1:8(t4), m2:8(t0)
  4th iteration
  
  m0 m1 m2
  
  t2 20 + 6 14 + 8 16 + 8
  
  t3 8 + 6 10 + 8 13 + 8
  
  t5 15 + 6 9 + 8 12 + 8
  
  t2 t3 t5
  
  Sufferage 2 4 3
  
  allocation m0
  - 실행시간 m0:14(t1,t3), m1:8(t4), m2:8(t0)
  5th iteration
  
  m0 m1 m2
  
  t2 20 + 6 + 8 14 + 8 16 + 8
  
  t5 15 + 6 + 8 9 + 8 12 + 8
  
  t2 t5
  
  Sufferage 2 3
  
  allocation m2
  - 실행시간 m0:14(t1,t3), m1:9(t4), m2:24(t0,t2)
  6th iteration
  
  m0 m1 m2
  
  t5 15 + 6 + 8 9 + 8 12 + 8 + 16
  
  t5
  
  Sufferage 12
  
  allocation m1
  - 실행시간 m0:14(t1,t3), m1:18(t4,t5), m2:24(t0,t2)
  Total execution time : 24

	t0	t1	t2	t3	t4	t5
Sufferage	3	12	2	2	3	3
allocation		m0

	m0	m1	m2
t0	5 + 6	15	8
t2	20 + 6	14	16
t3	8 + 6	10	13
t4	22 + 6	8	11
t5	15 + 6	9	12

	t0	t2	t3	t4	t5
Sufferage	3	2	3	3	3
allocation	m2

	m0	m1	m2
t2	20 + 6	14	16 + 8
t3	8 + 6	10	13 + 8
t4	22 + 6	8	11 + 8
t5	15 + 6	9	12 + 8

	t2	t3	t4	t5
Sufferage	8	4	11	11
allocation			m1

	m0	m1	m2
t2	20 + 6	14 + 8	16 + 8
t3	8 + 6	10 + 8	13 + 8
t5	15 + 6	9 + 8	12 + 8

	t2	t3	t5
Sufferage	2	4	3
allocation		m0

	m0	m1	m2
t2	20 + 6 + 8	14 + 8	16 + 8
t5	15 + 6 + 8	9 + 8	12 + 8

	t2	t5
Sufferage	2	3
allocation	m2

	m0	m1	m2
t5	15 + 6 + 8	9 + 8	12 + 8 + 16

	t5
Sufferage	12
allocation	m1

A star

일반적으로 Graph의 path-finding에 자주 활용. Djikstra는 shortest를 계속 구해나가지만, A star는 어느 순간 부터는 대략적인 shortest path를 알려줌
f(n) = g(n) + h(n)
- g(n)은 현재가지의 performance (실제)
- h(n)은 이후 performance에 대한 function (예측)
- 즉 f(n)은 실제결과 + 예측결과의 합
예측하는 h(n)이 포인트인데, h(n)가 정밀할수록 f(n)이 정확해지는 것

※ Tabu Search (Taboo)

일종의 branch of bound
Combinatorial Optimization(조합 최적화) 문제를 푸는 Metaheuristic 기법 중 하나로 greedy나 local search의 local optimum 함정 회피용

Random Search

Simulated Annealing (SA)
Genetic Algorithm (GA)