Chap4-6. 작업스케줄링(Job scheduling)

작업 스케줄링 문제

• 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계(프로세서)에 배정하는 문제
  • *여기서 기계는 프로세서이며 문제마다 다르다. 하지만 이를 가장 적게 사용하는 방법을 고안하는 것이다.
• 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다.
  • 발표 = ‘작업’, 강의실 = ‘기계’

 

작업 스케줄링 문제에 주어진 문제 요소

1. 작업의 수

   입력의 크기이므로 알고리즘을 고안하기 위해 고려되어야하는 직접적인 요소는 아니다.

2. 각 작업의 시작시간과 종료 시간

3. 작업의 길이

 

 

- 작업의 시작 시간과 종료시간은 정해져 있으므로 작업의 길이도 주어진 것

- 주어지는 조건에 따라서 작업 스케줄링 문제가 다양하다.

- 여러 가지 작업들이 있고 그 작업들마다 시작시간과 종료 시간이 다 다르다. 이럴 경우 이 작업들을 어떻게 스케줄링을 했을 때 최적의 결과가 나오는지 알아보기 위해서는 그리디 알고리즘으로 한다.

 

작업 스케줄링은 크게 1) 구간 스케줄링과 2) 구간 분할 문제로 나뉜다.

1) 구간 스케줄링에서는 a) 여러 가지 작업 중에 여러 스케줄 중에 처리를 안해도 된다라고 하고 진행하는 알고리즘도 있고 b)무조건 주어진 작업은 전부 다 처리해야한다고 하는 알고리즘도 있다.

각각의 문제마다 그리디 알고리즘을 이용하면 최적해가 나온다는 것은 이미 증명이 되어 있다. (모순 증명법과 바엘 증명법이 있다. )

 

시작 시간, 종료 시간, 작업 길이에 대한 그리디 알고리즘

[정답을 도출해내는 기준들]

• (1) 빠른 시작 시간 작업 우선 배정(Earliest start time first)
  • 교재에서는 구간 분할 배정 방식을 선택하는데 이때 4가지 중에서 이 방법이 최적해를 구하는 방법이다. 그 외에는 최적해를 얻지 못한다.
• (2) 빠른 종료 시간 작업 우선 배정 (Earliest finish time first)
  • 구간 스케줄링 문제일 경우 이 방식이 최적해가 나온다고 증명됨(미팅을 모두 안실행해도 된다)
• (3) 짧은 작업 우선 배정(Shortest job first)

미용실 같은 경우는 미용사가 한 명인데 손님은 파마 손님, 커트 손님 등 다양하게 있다.이때 손님을 한 명도 버릴 수 없고 전부 수용해야하는 경우 이 방법이 최적해를 구할 수 있다.

예를 들어 t1 = 5시간, t2 = 10시간, t3 = 4시간이 있다고 하자
1, 2, 3 순이라면 => 5 + (5 + 10) + (5 + 10 + 4)이다.
하지만 시간이 짧은 순으로 정렬한다면 3, 1, 2이고 3 + (3 + 1) + (3 + 1 + 2)이다.

• (4) 긴 작업 우선 배정(Longest job first)

 

 

---

구간 스케줄링(interval Scheduling)

작업 스케줄링 중에서 interval Scheduling(구간 스케줄링)에 해당한다.

• n개의 테스크와 1개의 프로세서가 있을 때, 수행 시간이 겹치지 않게 어떤 테스크들을 선택하면 가장 많은 테스크들을 수행할 수 있을까? (단, 각 테스크는 시작과 종료 시각을 가진다.)

구간 스케줄링 문제는 작업은 n개가 있고 작업을 처리하는 머신 혹은 프로세서는 1개이다. 그랬을 때 가장 많은 작업을 수행할 수 있게 배정하는 것이다. 이 경우는 어떤 작업이 수행되지 못할 수도 있다.(즉, 모든 작업이 수행되지 못할 수도 있다는 것이다. )

 

[문제]
어느 대학교 동아리들이 중앙 도서관의 미팅룸을 사용하기 위해 도서관에 신청했다.
각 동아리는 미팅의 시작과 종료 시각을 제출하였고 도서관에서는 가장 많은 동아리들이 미팅룸을 사용하도록 시간표를 작성하려고 한다.

 

 

#구간 스케줄링 알고리즘 

(1) 종료 시각을 기준으로 정렬한다. 
(2) 가장 일찍 종료하는 동아리를 선택한다. 
(3) 다음 동아리의 시작 시각이 직전에 선택된 동아리의 종료 시각 이전이면 다음 동아리를 포기하고 
    이후이면 다음 동아리를 선택한다. 

 

 

[코드]

meeting = [['C1', 8.0, 13.0], ['C2', 9.0, 11.0], ['C3', 10.5, 11.5], ['C4', 11.0, 14.0],['C5', 13.0, 16.0], ['C6', 14.0, 15.0], ['C7', 15.0, 17.0]]
#동아리 이름, 시작 시간, 종료 시간

meeting.sort(key = lambda t : t[1]) #람다식으로 정렬할 것임 t는 변수이고 어떤 값을 기준으로 정렬할 것인지는 다음에 온다. t[1]은 시작 시간을 기준으로 정렬하겠다는 의미
#가장 이른 시작 시간 먼저하는 방법 

schedule = [meeting[0]] #미팅의 0번 인덱스를 처음 배정했다.
i = 0
for j in range(1. len(meeting)): # 이 반복이 전부다 돌면 스케줄이 완성될 것이다. 
    if meeting[j][i] == meeting[i][2]: #다음 번의 시작시간과 현재의 종료 시간을 보자 같다는 것은 이어지는 것이다.
        schedule.append(meeting[j])
        i = j

print("Meeting schedule: ", schedule)
#빠른 시간부터 배정을 해주자

meeting.sort(key = lambda t : t[2] - t[1]) #가장 짧은 미팅시간을 기준으로 정렬

 

최적해를 찾는 방법 = 빠른 종료 시간 작업 우선 배정 (Earliest finish time first)

 

 

---

구간 분할(interval Partitioning)

• n개의 테스크가 있을 때, 최소의 프로세서를 사용하여 수행 시간이 겹치지 않게 모든 태스크를 프로세서에 배정하는 문제

(단, 각 태스크는 시작과 종료 시각을 가진다)

 

[문제]
교내의 동아리들이 토요일에 도서관 회의실을 예약하려고 각 동아리 미팅의 시작과 종료 시각을 도서관에 제출하였다.
도서관은 모든 동아리의 미팅을 위해 최소의 회의실을 사용하여 미팅 스케줄을 정하려고 한다.

구간분할문제 알고리즘 
(1) 동아리들을 시작 시각으로 정렬한다. 
(2) 정렬된 동아리들에서 첫 동아리를 미팅룸 1에 배정한다. 
(3) 배정된 동아리의 다음 동아리를 기존의 미팅룸에 배정할 수 있다면 그 미팅룸에 배정하고, 
    배정할 수 없으면 새 미팅룸에 배정한다. 

[코드]

meeting = [['C1', 8.0, 13.0], ['C2', 9.0, 11.0], ['C3', 10.5, 11.5], ['C4', 11.0, 14.0],['C5', 13.0, 16.0], ['C6', 14.0, 15.0], ['C7', 15.0, 17.0]]
#동아리 이름, 시작 시간, 종료 시간

meeting.sort(key = lambda t : t[1]) #람다식으로 정렬할 것임 t는 변수이고 어떤 값을 기준으로 정렬할 것인지는 다음에 온다. t[1]은 시작 시간을 기준으로 정렬하겠다는 의미
schedule = [[meeting(0)]] #schedule이라는 배열에 배열이 들어간 것이다.
finishTime = [meeting[0][2]] #미팅의 0번째 요소의 2번째인 종료 시간을 의미한다.

k = 0 #미팅룸의 값

for i in range(1, len(meeting)): # 미팅의 1번 인덱스부터 9번인덱스까지(전체)하나씩 다 보겠다
    
    flag = False #새로운 미팅룸 만들지 말지에 대한 여부
    for j in range(k+1): #방을 0번부터 k까지 하나하나 살펴본다.
        if meeting[i][1] >= finishTime[j]: #지금 선택한 회의의 종료시간이 미팅룸의 종료시간보다 같거나 길다면 그 회의실에 들어갈 수 있음
            schedule[j].append(meeting[i]) # 해당 스케줄을 추가한다.
            finishTime[j] = meeting[i][2] # 종료 시간 업데이트
            flag = True # 이미 방에 들어갔기 때문에 방을 더 이상 만들지 않아도 된다는 의
            break # 방을 순차적으로 도는 것 끝

    if not flag:
        k += 1 #방하나 증가
        schedule.append([meeting(i)]) #해당 미팅을 스케줄에 넣는다.
        finishTime.append(meeting[i][2])#방이 추가되고 이 방에 미팅이 추가되어서 종료 시간을 수정한다.
        
        
for i in range(k+1): # 0번방 부터 돌면서 출력
    print("Room", i+1, ":", schedule[i]) #행별로 출력

최적해를 찾는 방법 = 빠른 시작 시간 작업 우선 배정(Earliest start time first)

---

Job scheduling
입력: n개의 작업 t1, t2, ⋯, tn
출력: 각 기계에 배정된 작업 순서

1. 시작 시간으로 정렬한 작업 리스트: L
2. while L ≠ ∅
3.     L에서 가장 이른 시작 시간 작업 ti를 가져온다.
4.        if ti를 수행할 기계가 있으면
5.           ti를 수행할 수 있는 기계에 배정
6.        else
7.           새 기계에 ti를 배정
8.       ti를 L에서 제거
9. return 각 기계에 배정된 작업 순서

 

시간복잡도

Line 1: 정렬 시간  = O(nlogn)

while-루프

    작업을 L에서 가져다 수행 가능한 기계를 찾아서 배정하므로 O(m) 시간 소요, 단, m은 사용된 기계의 수

    while-루프가 수행된 총 횟수는 n번이므로, line 2~9까지는 O(m) x n = O(mn) 시간 소요

시간 복잡도: O(nlogn)+O(mn)