작업 스케쥴링 문제

이전 Post에선 하나의 장비가 존재할때, 최대한 많은 작업을 하는 작업 선택문제에 대해서 이야기했습니다.

 

그럼, 하나 이상의 장비가 있을때는 어떻게 될까요?

 

이번 포스트는 하나이상의 장비가 있을 때, 장비의 가동률을 최대로 올리는 작업 스케쥴링 문제입니다.

 

다수의 작업을 N개의 장비에 배정하는 문제

이때, 이번 문제는 장비의 가동률(장비가 쉬는 시간을 최소화)해서 작업을 진행하는 문제입니다.

 

이러한 조합을 찾기 위해서, 다음과 같은 알고리즘으로 작업을 배분합니다.

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

2. 해당 작업을 장비 1부터 충돌이 있는지 확인 후, 장비N번째까지 모두 충돌이면 Pass

3. 충돌이 없으면 장비 1번분터 순차적으로 배분

4. 모든 장비에 배분할 Job이 없으면 알고리즘 종료

작업 시작시간이 빠른 Job을 장비 1번부터 우선적으로 배정할 경우 장비별 작업 스케쥴

기존의 작업 선택 문제와의 찾이점은, 시작시간이 가장 빠른 작업을 찾는다는 점 입니다.

(시작시간이 빠르면 장비의 노는시간이 줄고, 종료시간이 빠르면 작업수행 개수가 증가합니다)

 

해당 알고리즘 역시 유일한 해가 문제의 유일해가 아니기 때문에, 결과 이외에 다른 정답이 있을수 있습니다 :)

 

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_schedule(DT_list, machine_count):
    #완성된 스케쥴표를 저장할 List선언
    schedule_list = [["%d machine"%i] for i in range(machine_count)]
    selected_index = [[None] for i in range(machine_count)]
    #초기 시작 Job을 시작0, 소요시간0으로 설정합니다.
    start_job = [[0,0] for i in range(machine_count)]
    while True:
        #추가할 Job중 End Time이 가장 작은 Job을 선택하기 위한 초기값을 선정합니다
        this_job = [[9999,9999] for i in range(machine_count)]           
        for i in range(len(DT_list)):            
            #이때 각 장비별로 일을 분배하기 때문에 Maachine Count만큼 추가 반복을 진행합니다.
            for j in range(machine_count):                
                #이전 작업종료시간과 같거나 크고(충돌X), 시작시간이 가장 빠른 Job을 장비마다 선택합니다       
                if DT_list[i][0] < this_job[j][0] and DT_list[i][0] >= start_job[j][1]:                
                    #이때 가장 첫번째 장비에 Job을 우선 배정하고, 다른 장비와 Job이 겹치지 않도록 합니다.
                    if i in selected_index[0:j]:                                                
                        pass
                    #다른 장비와 Job이 겹치지 않으면 해당 Job의 Index와 작업정보를 저장합니다.
                    else:
                        this_job[j] = DT_list[i]                    
                        selected_index[j] = i                       
        if this_job == [[9999,9999] for i in range(machine_count)]:
            break
        else:
            #아니면 다음 start_job을 최신화 후 반복을 진행합니다.
            start_job = this_job   
        #Update된 최적의 Job을 해당 장비마다의 스케쥴표에 입력합니다.
        for j in range(machine_count):
            schedule_list[j] = schedule_list[j] + [DT_list[selected_index[j]]]
        #만약 선택된 Job이 모두 존재하지 않으면, 알고리즘을 종료하고 작업 스케쥴을 반환합니다.                         
    return schedule_list
        
work_schedule(test,4)    
Out[69]: 
[['0 machine',
  [1, 9],
  [10, 13],
  [15, 20],
  [20, 21],
  [21, 23],
  [24, 32],
  [34, 37],
  [38, 39],
  [40, 48],
  [48, 49],
  [49, 57],
  [57, 67],
  [67, 69],
  [69, 74],
  [75, 78],
  [78, 85],
  [85, 87],
  [92, 93],
  [93, 95],
  [95, 100],
  [100, 104]],
 ['1 machine',
  [3, 10],
  [11, 21],
  [21, 28],
  [28, 32],
  [34, 37],
  [38, 39],
  [40, 43],
  [43, 53],
  [55, 62],
  [63, 69],
  [69, 74],
  [75, 78],
  [78, 85],
  [85, 87],
  [92, 93],
  [93, 95],
  [95, 100],
  [100, 104], #여기까지 이후는 의미없는 값
  [100, 104],
  [100, 104],
  [100, 104]],
 ['2 machine',
  [3, 6],
  [6, 16],
  [22, 26],
  [26, 30],
  [30, 39],
  [40, 43],
  [43, 53],
  [55, 62],
  [63, 69],
  [69, 74],
  [75, 78],
  [78, 85],
  [85, 89],
  [93, 103], #여기까지 이후는 의미없는 값
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103]],
 ['3 machine',
  [6, 16],
  [20, 21],
  [26, 30],
  [31, 32],
  [34, 44],
  [44, 50],
  [52, 53],
  [56, 58],
  [59, 69],
  [71, 81],
  [81, 87],
  [93, 103], #여기까지 이후는 의미없는 값
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103],
  [93, 103]]]