An On-Line Algorithm for Some Uniform Processor Scheduling
An On-Line Algorithm for Some Uniform Processor Scheduling
复制标题
DOI：
10.1137/s0097539799527969
复制
发表时间：
1995-08
期刊：
影响因子：
--
通讯作者：
Rongheng Li;Lijie Shi
中科院分区：
文献类型：
--
作者：
Rongheng Li;Lijie Shi
本文考虑了m台机器(M1，M2，⋯，mm)上的一组独立作业的在线排序问题，其中机器M‘的处理速度为si=1(i=1，⋯，m−1)，且sm=S>；1.列表排序[Yookum Cho and Sartaj Sahni.一致处理器上列表调度的界。暹罗J.计算机。9(1980)，第91-103页。]证明了对于m=2和m=3，这个最坏情况的界不能被改善，并且对于每m个−4，当sm=2，e是固定正数时，给出了一个最坏情况下至多3m−1/m+1−e的算法，并改进了一般的sm=S和gt；1的最坏情况的界.
This paper considers the problem of on-line scheduling a set of independent jobs on m uniform machines (M1, M2,⋯, Mm) in which machine M′is processing speed is si=1(i=1,⋯, m−1) and sm=s>1. List Scheduling [Yookum Cho and Sartaj Sahni. Bounds for list schedules on uniform processors. SIAM J. Compute. 9(1980), pp91–103.] guarantees a worst case performance of 3m−1/m+1(m≥3) and 1+√5/2(m=2) for this problem.We prove that this worst case bound cannot be imporved for m=2 and m=3 and for every m≥4, an algorithm with worst case performance at most 3m−1/m+1−e is presented when sm=2, where e is a fixed positive number, and then we improve the bound for general sm=s>1.