[알고리즘] 탐욕법 - 스케쥴링 (Greedy Approach - Scheduling)

1. 스케쥴링이란?

 

The time in the system이란 기다리고, 수행하는 시간을 합친 시간이다.

시스템에서의 중요한 점은 이러한 시간의 합인 total time을 minimize 하는 것이 목표이다.

 

만약 deadline이 있는 스케쥴링이고, 각 작업은 동일한 complete time을 가진다고 가정합니다.

또한 데드라인 안에 끝내는 작업은 이익을 얻습니다.

만약 어떤 작업을 해당 작업의 데드라인 이후에 스케쥴링된다면 이 스케줄을 impossible이라고 합니다.

이때 impossible한 스케줄은 고려하지 않는데, 이유는 데드라인 이후에 실행되는 작업에 대해서는 이익을 얻지 못하기 때문입니다.

 

따라서 목표는 이익의 총합이 극대화되게 하는 것입니다.

 

Job	Deadline	Profit
1	2	30
2	1	35
3	2	25
4	1	40

이렇게 작업의 형태가 정해져있을 때 impossible하지 않는 모든 스케줄을 알아본다면,

Schedule	Total Profit
1, 3	55
2, 1	65
2, 3	60
3, 1	55
4, 1	70
4, 3	65

이때, [4, 1]이 최적의 스케쥴이란 걸 알 수 있습니다.

 

하지만 이렇게 모든 경우의 수를 세서 최적의 스케줄을 찾아내는 것이 최선일까요?

이렇게 찾아낸다면, factorial time이 걸리고, 최악의 경우 exponential time이 걸리게 됩니다.

 

DP도 고려는 해봐야하지만 이때는 탐욕법이 더 효율적이기 때문에 탐욕법을 이용해서 문제를 해결하겠습니다.

---

2. 탐욕법을 이용한 문제 해결

 

직관적으로 생각을 해도, 보상이 큰 작업이 먼저 스케줄에 들어갈 것을 알 수 있습니다.

왜냐면 모두 1이라는 작업 시간을 가지기 때문에, 데드라인만 된다면 보상이 큰 작업이 더 큰 이익을 가져다줍니다.

 

따라서 탐욕법을 적용하기 위해서는 

1. 보상을 내림차순으로 정렬한다.
2. 작업을 추가했을 때, 작업이 적절하다면 스케줄에 작업을 추가한다.
3. 추가할 작업이 없을 때까지 반복한다.

 

이때 실행 가능한 순서를 feasible sequence라고 합니다.

위의 경우에서 [4, 1]은 feasible sequence이지만, [1, 4]는 feasible sequence가 아닙니다.

만약 작업의 집합이 있을 때, 이 작업의 집합의 조합으로 적어도 하나의 feasible sequence를 만들 수 있다면, 이 집합을 feasible set이라고 합니다.

 

우리의 목표는 최적의 순서를 찾는 것이고, 최적의 순서는 total profit을 최대화하는 feasible sequence입니다.

 

슈도 코드)

sort the jobs in non-increasing order by profit
S = 0
while the instance is not solved:
	select next job
    if S is feasible with this job added:
    	add this job to S
    if there are no more jobs:
    	the instance is solved

 

이때 만약 어떤 집합 set이 feasible 하다는 것을 어떻게 증명할까요?

 

증명)

• 집합 S가 feasible하다는 것과
• 집합 S에 속한 작업을 데드라인의 오름차순으로 정렬했을 때 feasible 하다는 것은
• if and only if관계이다.

따라서 집합 S가 feasible 하다는 것을 알기 위해서는 S에 속한 작업을 데드라인 기준으로 오름차순 정렬해서 feasible 한 지 알아보면 됩니다.

 

즉 deadline[i] >= i이면 되겠네요.

 

 

시간 복잡도는 n^2 - 1이므로 \(\theta(n^2)\)이 되겠네요.

 

왜냐면 n - 1번의 반복 동안, n번의 feasible 한 지 비교가 일어나기 때문입니다.

 

 

감사합니다.

 

 

지적 환영합니다.