Greedy 알고리즘-Job Scheduling

greedy 알고리즘의 여섯 번째 문제

6. 작업 스케줄링(Job Scheduling)

-작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제. 

-machine의 수가 무제한이지만 최소로 쓰게 풀어라.

-Input :  작업의 수 n개, 각 작업의 시작 시간과 종료시간(길이)

-각자 시작 시간과 마치는 시간이 다른 강의자들을 어떻게 강의실에 배치시킬 것인가?

 

 

ex)

Task=(t1=[7,8],t2=[3,7],t3=[1,5],t4=[5,9],t5=[0,2],t7=[1,6])

단, [s,f]에서 s는 작업의 시작 시간, f는 작업의 종료 시간

 

-방법

1.시작 시간의 오름차순으로 정렬한다.

L={[0,2],[1,6],[1,5],[3,7],[5,9],[6,8],[7,8]}

2.가장 먼저 시작하는 task부터 선택. Machine1 사용

3.다음으로 먼저 시작하는 task선택. Machine1이 사용중이면(비어 있는 Machine이 없으면) Machine2 사용

4. 모든 task를 처리할때까지 반복

 

-Psedo Code

Input  : T ={t1,t2,...,tn}, 시작 시간, 종료시간

Output : Task Schedule for Each Machine

L=Sorted T in the ascending order of starting time
M={}//선택된 Machine의 개수
while(L!=0){//모든 task가 수행될때까지 반복
ti=L[0]//가장 앞에 있는 task부터 선택
if(isRunnable(ti,m)for m in M)
   m= m U {ti}//기존 Machine에 가능하면 수행
else  
   m'= m U {ti}//새로운 머신 추가
   M= M U m'
L=L/ti
return M}

-Time Complexity

1. 정렬 O(nlong)

2. while문 순환 L번 O(|L|)

3. 사용가능한 Machine 체크 M번 순환 O(|M|)

 

Time Complexity=O(nlong)+O(|L|)+O(|M|)

결론: task 수와 machine 수에 따라 달라진다.