English

应用科学学报 ›› 2007, Vol. 25 ›› Issue (5): 535-535 .

• 论文 • 上一篇    下一篇

半在线模型的松弛

罗润梓1 ,孙世杰2   

  1. 1．南昌大学 数学系，江西 南昌 330031；

    2.上海大学 数学系，上海 200444

  • 收稿日期:2006-06-22 修回日期:2007-01-30 出版日期:2007-09-30 发布日期:2007-09-30

Relaxation of Semi-online Model

LUO Run-zi1, SUN Shi-jie2   

  1. 1. Department of Mathematics,Nanchang University,Nanchang 330031,China;
    2. Department of Mathmatics,Shanghai University,Shanghai 200444,China
  • Received:2006-06-22 Revised:2007-01-30 Online:2007-09-30 Published:2007-09-30

被引次数

3

摘要： 研究半在线模型的松弛，讨论以下半在线松弛模型：已知工件最大加工时间在某一区域内（known largest job interval）, 分别讨论了该模型下2台同型机的极小化Cmax问题和极大化Cmin问题。对这两个问题构造pInteval算法，给出其竞争比并证明它是紧的，还分析了上述两个问题的特征和LS算法的竞争比。

关键词: 半在线, 同型机, 竞争比, 松弛

Abstract: In this paper, we introduce relaxation of a semi-online model and discuss a new semi-online relaxation model: known largest job interval. We investigate P2|known largest job interval| Cmax problem and P2|known largest job interval| Cmin problem, respectively. For these two problems, we present an algorithm called PInterval, and derive its tight competitive ratios. We also discuss characteristics of these two problems and competitive ratio of the LS algorithm.

Key words: semi-online, identical machine, competitive ratio, relaxation