작업 선택 문제

가동가능한 기계가 하나있고, 수행시간이 정해진 작업이 쌓여있다고 가정합니다.

 

이때 최적의 순서를 통해서 최대한의 일을 수행하는 방법을 작업선택 문제라고 합니다.

5개의 작업 중 최적의 3개의 작업을 고르는 방법

위 경우를 살펴보면, 작업1과 3 사이의 빈 시간이 발생하지만, 최종적으로는 3개의 작업을 수행할 수 있기 때문에

 

최적의 작업 선택이라고 할 수 있습니다.(물론 손으로 구하면 작업 2, 4, 5도 가능합니다)

 

알고리즘을 살펴보면

1. 작업중 종료시간이 가장 빠른 Job을 찾는다

2. 해당Job이 이전Job과 충돌이 없는지 확인한다.

(그림에서 보듯, 이전 Job의 종료시간보다 새로할 Job의 시작시간이 빠른경우 충돌이라 합니다)

2_1. 충돌이 있을경우 1로 돌아가서 나머지 Job에서 1~2를 반복한다.

3. 해당 Job을 스케쥴표에 집어넣고, 더이상 선택할 Job이 없을때까지 반복

 

알고리즘은 매우 간단합니다.

 

 

다만, 해당 알고리즘으로 구해지는 작업스케쥴이 유일한 해는 아니란것을 위 예제로 알 수 있습니다 :)

 

Python으로 구현된 작업선택문제 소스코드입니다.

import random
import copy
test = []
#시작시간와 종료시간이 존재하는 작업을 Random하게 생성합니다
for i in range(100):
    #시작시간은 1~100 사이
    temp = random.randint(1,100)
    #작업에 걸리는 시간은 1~10 사이입니다.
    temp2 = temp + random.randint(1,10)
    #이제 [작업시작시간, 작업종료시간] 형태로 Data를 저장합니다
    test = test + [[temp, temp2]]

def work_select(DT_list):
    #완성된 스케쥴표를 저장할 List선언
    schedule_list = []
    #초기 시작 Job을 시작0, 소요시간0으로 설정합니다.
    start_job = [0,0]        
    while True:
        #추가할 Job중 End Time이 가장 작은 Job을 선택하기 위한 초기값을 선정합니다
        this_job = [9999,9999]            
        for i in range(len(DT_list)):
            #이전 작업종료시간과 같거나 크고(충돌X), 종료시간이 가장 빠른 Job을 선택합니다
            if DT_list[i][1] < this_job[1] and DT_list[i][0] >= start_job[1]:                
                this_job = DT_list[i]
                selected_index = i        
        #만약 this job이 선택되지 않았다면(위 조건을 통과하는 Job이 없을경우) 알고리즘 종료
        #모든 Element가 순서가 정해졌으면 역시 알고리즘 종료
        if this_job == [9999,9999] or len(DT_list)==0:
            break                
        else:
            #this job이 최신화 되었을 경우 해당값을 스케쥴 List에 넣어주고, 기존 List에서 제거해줍니다.
            schedule_list = schedule_list + [DT_list.pop(selected_index)]
        #Start_job을 이번에 선택된 Job으로 변경해주고 다시 반복
        start_job = this_job                
    return schedule_list
        
work_select(test)        
Out[10]: 
[[9, 10],
 [10, 13],
 [13, 18],
 [18, 22],
 [22, 27],
 [34, 36],
 [37, 38],
 [40, 44],
 [44, 45],
 [51, 52],
 [53, 55],
 [55, 57],
 [57, 60],
 [60, 68],
 [68, 69],
 [69, 70],
 [73, 75],
 [76, 77],
 [82, 84],
 [88, 89],
 [90, 92],
 [93, 94],
 [94, 96],
 [96, 97],
 [98, 100]]