반응형
이번 2024 KSIAM 학회 포스터 제출 관련
Job Scheduling 작업 스케줄링 문제
- 기계에서 수행되는 n개의 작업들을 수행 시간이 중복되지 않도록 가장 적은 수의 기계에 배정하는 문제이다.
- 각 작업은 시작시간과 종료시간이 정해져있다.
- = 발표 시간이 정해진 학술대회에서 발표자들을 강의실에 배정하는 문제
Job Scheduling 주어진 문제 요소
- 작업의 크기
- 각 작업의 시작시간과 종료시간
- 작업의 길이 (작업의 시작시간과 종료시간으로 길이 구함)
알고리즘
- 그리디 알고리즘:
- 빠른 시작 시간 작업 우선 (Earliest Start Time First)
- 빠른 종료 시간 작업 우선 (Earliest Finish Time First)
- 짧은 작업 우선 (Shortest Job First)
- 긴 작업 우선 (Longest Job First)
- 여기서는 최적해를 찾기 위해 첫 번째 방법을 선택한다.
- 그리디 알고리즘을 적용하기 위해서는 Earliest start time first 방법을 제외하고는 최적해를 찾을 수 없다.
- 빠른 시작 시간 작업 우선 (Earliest Start Time First)
Pseudo Code
JobScheduling
입력: n개의 작업 t_1,t_2,...,t_n
출력: 각 기계에 배정된 작업 순서
1. 시작시간으로 정렬한 작업 리스트: L
2. while L != NULL
3. L에서 가장 이른 시작 시간 작업 t_i를 가져온다.
4. if t_i를 수행할 기계가 있으면 # 현재 처리중인 기계의 작업 종료시간보다 t_i의 시작시간이 더 늦다면 배정이 가능하므로 기계에 배정
5. t_i를 수행할 수 있는 기계에 배정
6. else
7. 새 기계에 t_i를 배정
8. t_i를 L에서 제거
9. return 각 기계에 배정된 작업 순서수행 과정
- 시작 시간과 종료 시간을 [start time, end time]이라고 표기
- 시작 시간을 기준으로 오름차순 정렬하여 list에 저장하면 다음과 같다.
- list = { [0, 2], [1, 5], [1, 6], [3, 7], [5, 9], [6, 8], [7, 8] }
t1 = [7, 8]
t2 = [3, 7]
t3 = [1, 5]
t4 = [5, 9]
t5 = [0, 2]
t6 = [6, 8]
t7 = [1, 6]
시간 복잡도
- 배열 정렬 시간 : O(nlogn)시간 걸림
- while 루프:
사용된 기계의 수를 m이라고 하면
루프 내부에서 기계를 찾을 때의 시간 복잡도 : 작업량을 순회하므로 m번 소요 -> O(m)
그리고 내부에서 기계의 리스트를 또 탐색하므로 n번 소요(루프가 n번 반복)된다. -> O(mn)orO(n2) - 최종 시간복잡도: O(mn(or n2))+O(nlogn)
반응형