Quasi-Online Algorithm for Scheduling Non-Increasing Processing-Time Jobs with Processor Cost
-
摘要: 对大多数调度问题来说,处理器集往往是事先给定的,而且在算法进行过程中,它是不 变的.Imreh和Noga第一次提出了在调度中考虑处理器有费用的模型.他们研究了所谓的List Model问题,给出了竞争比为1.618的在线算法,同时证明了任意在线算法的竞争比至少是 4/3.该文研究List Model问题的一个半在线情形,即假设工件是从大到小到达的,给出一个竞 争比为3/2的半在线算法.同时证明对该问题的这一半在线情形,任意半在线算法的竞争比至 少是4/3.Abstract: For most scheduling problems the set of processors is fixed initially and remains unchanged for the duration of the problem. Imreh and Noga recently proposed adding the concept of processor cost to the scheduling problem and considered the socalled List Model problem. An online algorithm of a competitive ratio 1. 618 was given with a lower bound of 4/3. In this paper, we investigate a quasi-online version of the List Model by supposing that jobs arrive in the non-increasing order of their processing times. We present a quasi-online algorithm with the competitive ratio being 3/2 and the lower bound 4/3.
-
Key words:
- Semi online /
- algorithm /
- competitive ratio /
- scheduling /
- machine cost
-
点击查看大图
计量
- 文章访问数: 2745
- HTML全文浏览量: 116
- PDF下载量: 917
- 被引次数: 0
下载:
