근사 작업 스케줄링 문제

그리디 문제에서 봤던 작업 스케줄링과 비교가 되는데

비교하기 위해서 보통 그리디 의 작업 스케줄링은 Job scheduling이라고 하고 근사 작업 스케줄링은 Task schduling이라고 한다.

그리디에서는 머신의 갯수를 최소화 하는 것이목표 였다면 근사 문제에서는 종료시간을 최소로 만들기 위한 그리디포인트트가 문제이다.

근사에서는 머신의 수가 고정되어 있어 끝나는 시간을 저장하고 끝나는 곳에 새로운 Task를 놓는다. 

골고루 배치 할수록 Best하다고 볼 수 있다.

 

현재 근사에서는 가장빨리 끝나는머신에 새 작업을 배정하는 것이다. 

구현 하는 방법으로는 머신수만큼의 index를가진 배열에 시간들을 Task 시간을 적어둔뒤 가장 적은 곳에 새로운 Task시간을 +하는 것이다.

 

수도 코드로 나타내자면

입력: n개의 작업, 각 작업 수행 시간 ti, (i = 1, 2, ⋯, n,), 기계 Mj, j = 1,2, ⋯, m
출력: 모든 작업이 종료된 시간
for j = 1 to m
	L[j] = 0
for i = 1 to n {
	min = 1
	for j = 2 to m {
		if (L[j] < L[min])
		min = j
	}
	작업 i를 기계 Mmin에 배정한다.
	L[min] = L[min] + ti
}
return 가장 늦은 작업 종료 시간

   로 나타 낼 수 있다.