가중치 작업들의 온라인 비선점 마감시한 스케줄링 = Online Non-preemptive Deadline Scheduling for Weighted Jobs

다국어 초록 (Multilingual Abstract)

In deadline scheduling, jobs have deadlines by which they are completed. The scheduling algorithm determines which jobs are executed at each time. Then only the completed jobs contribute to the throughput or gain of the algorithm. The jobs have arbitrary weights and the gain of the algorithm is given as the sum of weights of the completed jobs. The goal of the scheduling algorithm is to maximize its gain.In this paper, we consider online non-preemptive scheduling, where jobs arrive online and the scheduling algorithm has no information about jobs arriving ahead. Also the jobs cannot be preempted or rejected while they are executed. For this problem, we obtain lower bounds for any online algorithms and also we propose an optimal online algorithm meeting the lower bounds.

국문 초록 (Abstract)

마감시한 스케줄링에서 작업들은 수행을 완료해야 하는 마감시한을 가진다. 스케줄링 알고리즘은 각 시간에 어떠한 작업이 수행되어야 하는 지 결정한다. 수행이 마감시한 안에 완료된 작업들만이 알고리즘의 처리량 또는 이익에 포함된다. 작업들은 임의의 가중치를 가지고 알고리즘의 이익은 완료된 작업들의 가중치의 합으로 주어진다. 스케줄링 알고리즘의 목표는 이익을 최대화하는 것이다.본 논문에서 우리는 온라인 비선점 스케줄링을 생각한다. 여기서 작업들은 온라인으로 도착하고, 스케줄링 알고리즘은 앞으로 도착할 작업들의 정보를 미리 알 수 없다. 작업들은 스케줄 되고 나서 수행 도중에 멈출 수 없다. 이 문제에 대해서, 우리는 임의의 온라인 알고리즘의 성능의 하한을 구한다. 또한 이 하한과 일치하는 성능을 가지는 최적의 온라인 알고리즘을 제안하다.

참고문헌 (Reference)

1 "Speed is as powerful as clairvoyance" 617-643, 2000.

2 "Performance guarantee for online deadline scheduling in the presence of overload" 755-764, 2001.

3 "Patience is a virtue; The effect of slack on competitiveness for admission control" 396-405, 1999.

4 "Optimal time-critical scheduling via resource augmentation" 140-149, 1997.

5 "Online interval scheduling" 302-311, 1994.

6 "On-line scheduling with hard deadlines" 258-271, 1997.

7 "On-line scheduling in the presence of overload" 101-110, 1991.

8 "On-line admission control and packet scheduling with interleaving In Proc. of IEEE INFOCOM" 2002.

9 "On the competitiveness of on-line task real-time task scheduling" 124-144, 1992.

10 "Minimizing the maximum starting time on-line" 449-460, 2002.

11 "Dover : An optimal on-line scheduling algorithm for overloaded real- time systems" 318-339, 1995.

12 "Applying extra-resource analysis to load balancing" 560-561, 2000.

13 "A multiprocessor on-line competitive algorithm for real-time system scheduling In Proc. of 14th Real-Time Systems Symposium" 172-181, 1993.

14 "A Guide to the Theory of NP- Completeness" 1979.