지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2012.10
- 수록면
- 2,303 - 2,308 (6page)
이용수
초록· 키워드
오류제보하기
본 논문은 마감시간을 가지는 병렬 태스크들을 스케줄하는 문제를 다룬다. 특히, 가단성 태스크, 다시 말해서, 수행시간이 수행 머신들의 개수의 함수로 주어지는 태스크를 다룬다. 스케줄링 알고리즘의 목표는 마감시간 안에 수행을 끝마친 태스크들의 작업량의 합을 최대화하는 것이다. 이 문제는 NP-hard 문제로 알려져 있다. 따라서, 근사 알고리즘을 찾으려하고, 알고리즘의 성능은 최적 알고리즘 성능과의 비, 다시 말해서, 근사비를 구해서 분석한다. 특히, 본 논문에서는 알고리즘이 최적 알고리즘보다 많은 자원, 즉, 보다 많은 머신들을 가지는 경우에 근사비를 구할 것이다. 이것은 자원추가분석이라고 불린다. 본 논문은 최적 알고리즘보다 1.5배의 머신들을 사용해서 3.67의 근사비를 보장하는 스케줄링 알고리즘을 제안한다.
목차
요약
ABSTRACT
Ⅰ. 서론
Ⅱ. 관련 연구
Ⅲ. 알고리즘 설명
Ⅳ. 성능 분석
Ⅴ. 결론
참고문헌
참고문헌 (4)
참고문헌 신청
1. [학술대회논문] - C. Phillips / 1997 / Optimal time-critical scheduling via resource augmentation / Proc. of the 29th Ann. ACM Symp. on Theory of Computing : 140 ~ 149
2. [학술지(정기간행물)] - 좌경룡 / 199901 / Scheduling Parallel Tasks with Individual Deadlines / THEORETICAL COMPUTER SCIENCE 215 (1) : 209 ~ 223
3. [학술지(정기간행물)] - M. Drozdowski / 1996 / Scheduling multiprocessor tasks - an overview / European Journal of Operational Research 94 (2) : 215 ~ 230
4. [학술지(정기간행물)] - Jae-Hoon Kim / 2011 / Approximation algorithms for scheduling parallel jobs with more machines 9 (4) : 471 ~ 474
2. [학술지(정기간행물)] - 좌경룡 / 199901 / Scheduling Parallel Tasks with Individual Deadlines / THEORETICAL COMPUTER SCIENCE 215 (1) : 209 ~ 223
3. [학술지(정기간행물)] - M. Drozdowski / 1996 / Scheduling multiprocessor tasks - an overview / European Journal of Operational Research 94 (2) : 215 ~ 230
4. [학술지(정기간행물)] - Jae-Hoon Kim / 2011 / Approximation algorithms for scheduling parallel jobs with more machines 9 (4) : 471 ~ 474
이 논문의 저자 정보
최근 본 자료
댓글(0)
0