加工时间有界的总加权流通时间半在线调
度SWPT规则的竞争比分析∗
陶继平† 席裕庚 巢志俊
上海交通大学自动化系，上海，200240
摘要 本文考虑了最小化总流通时间的单机及并行机调度，并假设任意实例中最大加工时间与最小加工
时间的比值不超过γ，在该半在线假设下，采用了一种基于实例转换思想的的方法分析了最短加权加工时
间(SWPT) 规则的竞争性能，结果显示，对于单机问题，SWPT 的竞争比为γ + 1，并且证明这也是针对
该问题所能取得的最优竞争比；对于多机问题，SWPT的竞争比不超过γ + 3/2− 1/2m。
关键词 算法分析，半在线算法，并行机调度，加权流通时间，竞争分析
中图分类号 90B35
1 引言
在调度系统中，一个工件的绝对完工时间可以作为对用户满意度的一种度量，但从用
户的角度，更加关注的可能是其在系统中耗费的总时间。例如，同样都是在第10个时刻完
工的两个加工时间相同的工件，如果一个是在0时刻到达，而另外一个是在第8个时刻到达，
则后者对服务的满意度显然应该更高。当将工件进入系统的时间考虑到目标函数中，即可
以得到调度系统中一个重要的优化指标—总(加权)流通时间。有时也称工件的流通时间为
响应时间，通常用符号F 表示，其在数字上等于工件的完工时间减去到达时间。在诸如通
信网络及并行计算等系统中[1, 2]，总(加权)流通时间是一项重要的优化指标，其是对调度系
统整体服务质量的一种度量。不难发现，从离线最优解的角度看，最小化总(加权)流通时间
等效于最小化总(加权)完工时间，两个目标对应的最优调度相同且目标值只相差一个常数
项。然而从在线算法的角度，两个对应目标之间存在很大的差异。
尽管针对最小化总(加权)完工时间目标的单机在线调度(1|rj |
∑
Cj、1|rj |
∑
wjCj)都
已经存在具有常数竞争比的最优在线算法[3–6]，针对这两个目标的并行机调度，当前最好算
法的竞争比也分别达到了2[7]及[8]。然而针对总(加权)流通时间目标，不管是单机还是
多机情况，都不存在具有常数竞争比的在线算法。即使对于离线近似算法，最小化总加权
流通时间单机问题的最差竞争比下界也至少是Ω(n
√
1/2−ε)[9]，相应多机问题的下界也至少
是Ω(n
√
1/3−ε)[2]，其中n为实例的工件数。
∗本文受到国家自然科学基金（60934007）和高等学校博士学科点专项科研基金（20070248004）资助.
中国科技论文在线
1
Administrator
Text Box
E-mail:
针对总(加权)流通时间目标，既然在完全在线的情况下不存在具有常数竞争比的在
线算法，一个自然的想法是考虑具有一些额外假设的半在线算法。一个广泛使用的半
在线假设是最大工件与最小工件加工时间的比值不超过某个常数，假设每个实例中最
大加工时间与最小加工时间的比值不超过γ，在此假设下，Bunde [10]已经证明最短加工
时间(SPT)规则对于问题1|rj |
∑
Fj 是最优的半在线算法，其竞争比为(γ + 1)/2。其它的
研究成果主要集中在可抢占的情况。Chekuri等[11]在进一步假设权重有界的情况下研究
了1|rj , pmtn|
∑
wjFj，提出了一个O(log2 γ)竞争的半在线算法。Leonardi及Raz[2]证明了最
短剩余加工时间(SRPT)规则对于问题Pm|rj , pmtn|
∑
wjFj的竞争比为O(log(min( nm , γ)))，
并且指出对于该问题，即使在考虑随机算法情况下，竞争比的下界也至少为Ω(log(min( n
m
, γ)))。
Bansal 及Dhamdhere[12] 针对1|rj , pmtn|
∑
wjFj提出了另外一种半在线假设，他们假设至
多有k个不同的权重，然后提出了一个所谓的平衡SRPT规则，该规则在每个决策时刻具有
相同权重的工件归为为一个子集，并选择平均权重最大的子集按照SRPT规则进行加工，
作者证明了该平衡的SRPT规则的竞争比为k，当k为1时，也即原加权问题退化为非加权问
题，这时平衡的SRPT规则退化为原始的SRPT规则，而SRPT规则就是非加权问题的最优
算法，这也正好与文[12]中的结论相吻合；另外基于文[12]中结论，当1|rj , pmtn|
∑
wjFj中
实例对应的最大权重与最小权重的比值不超过W，可以将工件的权重圆整到2的整数次幂
后再执行平衡的SRPT规则，进而得到一个竞争比为O(logW )的半在线算法。
当考虑目标为最小化总加权流通时间且不可抢占的有界加工时间半在线调度时，尚
未有任何具有有界性能比的成果。本文即在加工时间有界的假设下，考虑了最小化总流
通时间的单机及并行机调度，分别记这两个问题为1|rj , pmaxpmin ≤ γ|
∑
wjFj及Pm|rj , pmaxpmin ≤
γ|∑wjFj，本文采用陶等[13]提出的一种基于实例转换的方法分析了SWPT规则(每当有机
器空闲时，即从尚未开始加工的工件中选择加权加工时间最短的工件进行加工)的竞争性
能，主要结果是，对于单机问题，SWPT 的竞争比为γ + 1，并且证明这也是针对该问题所
能取得的最优竞争比；对于多机问题，SWPT的竞争比不超过γ + 3/2− 1/2m，同时也证明
其下界至少为γ + 1。
2 SWPT调度的块结构
陶等[13]提出了一种基于实例转换的竞争比分析方法，该方法已被成功应用于几个在线
及半在线调度的性能分析[14–16]，其基本思想是在问题的整个实例空间中搜索最差实例，其
基本做法是从问题的一个任意实例出发，通过修改工件的各种参数（包括到达时间、加工
时间、权重）得到一个结构相对原实例更简单规范的实例，且其性能比不小于原实例，换句
话说，实例转换是向着最差实例的方向进行，通过反复执行这种转换，最终得到一个结构
相对简单的实例，其性能比可以直接分析计算，该性能比同时也就是算法竞争比的一个上
界，下面将采用这种思想分析SWPT规则的竞争性能。
对于任意的实例I，记SWPT规则生成的调度为SWPT (I)，相应的最优调度为OPT (I)，
在不引起混淆的情况下也用SWPT (I)及OPT (I)分别表示相应调度对应的目标函数值。记
中国科技论文在线
2
任意工件Ji在SWPT调度及最优调度中的流通时间分别为Fi及F ′i。
从寻找最差实例的角度，可以假设第一个工件是0时刻到达。SWPT (I)在每台机器上
由一个或几个连续加工的时间片段组成。为表示方便，对应任意时刻t，如果存在ε > 0使
得SWPT调度中某台机器在(t− ε, t) 时段处于空闲状态，则称该机器在t时刻空闲；如果存
在ε > 0使得SWPT调度中某台机器在(t− ε, t) 时段处于忙状态，则称该机器在t时刻忙。如
果某个时刻所有机器都处于空闲状态，则表明该时刻前到达的工件都已完工，对于此情形，
可以将该时刻前后到达的工件分别组成两个新实例，则不难证明至少有一个新实例的性能
比不小于原实例。因此从寻找最差实例的角度，下文假设实例对应的SWPT调度在所有机
器都完工前不存在某个时刻使得所有机器都处于空闲状态，为表述方便，称这样的调度为
只包含单块的SWPT调度，记任意一个对应SWPT调度具有这种结构的实例为I1，
假设SWPT (I1)中工件按开工的先后顺序依次为J1, J2, . . . , Jn。则可以进一步将该工
件队列划分为q+1个子队列 J1, J2, . . . , Ji1、Ji1+1, Ji1+2, . . . , Ji2、. . .、Jiq+1, Jiq+2, . . . , Jn，
其中每个子队列内工件按照SWPT的顺序排列，且每个子队列第一个工件的加权加工时间
小于前一个子队列最后一个工件的加权加工时间，即pik/wik > pik+1/wik+1。下面将利用
文[13]所提出的基于实例转换的方法证明，可以在保证性能比不减的条件下将I1变换为另外
一个新实例，该新实例或者由加权加工时间相同的工件组成，或者按照上述子队列的划分
方式，该新实例所对应的SWPT调度队列的最后一个子队列包含几个权重无穷大的工件。
3 实例转换过程
首先给出一个实例转换过程中将反复使用的一个引理，其具体证明可参见文[13]。
引理 1. [13] 如果f(x),g(x)是两个定义在[x1, x2] ∈ R上的正函数，并且f(x)是凸的，g(x)是
凹的，那么函数 f(x)
g(x)
在端点处取到最大值，即 f(x)
g(x)
≤ max
{
f(x1)
g(x1)
, f(x2)
g(x2)
}
。
不难看出上述引理在开区间的情况下，只要 f(x)
g(x)
在相应端点的极限存在，定理仍然成
立。
SWPT规则是以一种单队列的形式选择工件进行加工，因此只要保证工件相互之间的
加权加工时间大小关系不变，可以任意调整工件的权重而保证其调度次序不变，进而保证
工件的开工时间也不变。下面将通过两个引理来展示实例转换过程。
引理 2. 对于问题1|rj , pmaxpmin ≤ γ|
∑
wjFj或者Pm|rj , pmaxpmin ≤ γ|
∑
wjFj，如果实例I1是一个
相应SWPT调度只包含单块的实例，则可以通过缩放工件的权重得到一个新实例I ′满足
SWPT (I1)
OPT (I1)
≤ SWPT (I
′)
OPT (I ′)
(1)
且SWPT (I ′)的最后一个子列中所有工件的加权加工时间都相等。
证明. 为表述方便，记SWPT (I1)的最后一个子列中所有工件构成的工件集为QL，记其中
排在子列第一位的工件为J1，根据子列的划分规则，显然其余工件的加权加工时间都不小
中国科技论文在线
3
于J1。根据加权加工时间的大小，将QL划分为如下的两个子集：
Q′1 = {Jj |Jj ∈ QL,+∞ >
pj
wj
>
p1
w1
} (2)
Q′2 = {Jj |Jj ∈ QL,
pj
wj
=
p1
w1
} (3)
将Q′1中每个工件Jj对应的权重wj修改到δwj，其中δ是一个大于0的参数，记该中间实例
为I ′(δ)。如果定义
δ¯ =
min{ pj
wj
|Jj ∈ Q′′1}
p1/w1
(4)
则当δ ∈ (0, δ¯]时，上述权重的修改不会改变工件的加权加工时间之间的大小关系，因
此SWPT (I ′(δ))中工件的调度次序完全与SWPT (I1) 相同，相应的开工时间及完工时间也
保持不变，这也意味着该调度对应的目标值是一个关于δ递增的线性函数。下面分析最优调
度OPT (I ′(δ))随δ的变化趋势，由于仅有部分工件的权重发生了变化，所以变化前每一个可
行调度在经过权重缩放后仍然保持可行，同时每个工件的开工和完工时间都保持不变，只
是目标函数值由于工件权重的改变而可能增大或减小，既然目标函数关于权重是线性变化
的，因此，对于每一个固定了开工时间的可行调度，当δ改变时，该可行调度对应的目标函
数值都是δ的线性函数。而最优调度是所有可行调度中目标函数值最小的一个，因此，当δ改
变时，OPT (I ′(δ))是多个关于δ的线性函数的最小值，也即是关于δ的分段线性函数，且斜
率随δ的增大保持不变或减小。
根据上述关于SWPT (I ′(δ))和OPT (I ′(δ))的分析并依据引理1，有下述关系：
SWPT (I ′(δ))
OPT (I ′(δ))
≤ max
{
lim
δ→0
SWPT (I ′(δ))
OPT (I ′(δ))
,
SWPT (I ′(δ¯))
OPT (I ′(δ¯))
}
如果最大值符号取第一项，Q′1中所有工件的权重都趋近无穷小，这些工件在SWPT调度及
最优调度的目标函数值中所占的相对比重为无穷小量，从极限意义下，显然直接删除这些
工件将不会改变实例的性能比，这时最后一个子列剩余工件的加权加工时间都等于p1/w1，
该中间实例即为符合引理要求的I ′。如果最大值符号取第二项，根据式(4)，Q′1中至少有一
个工件的加权加工时间被修改到了p1/w1。
按照式(2)及(3)更新子集Q′1及Q′2，如果Q′1中仍然剩余有工件，重新执行上述的实例转
换，不难发现经过反复执行这种转换过程，最终即可以使最后一个子列所有工件的加权加
工时间都等于p1/w1。
引理 3. 对于问题1|rj , pmaxpmin ≤ γ|
∑
wjFj或者Pm|rj , pmaxpmin ≤ γ|
∑
wjFj，如果实例I1是一个
相应SWPT调度只包含单块的实例，则可以通过缩放工件的权重得到一个新实例I2或I3满
足
SWPT (I1)
OPT (I1)
≤ max
{
SWPT (I2)
OPT (I2)
,
SWPT (I3)
OPT (I3)
}
(5)
中国科技论文在线
4
其中I2的所有工件具有相等的加权加工时间；而I3所对应的SWPT调度队列的最后一个子
队列中的工件具有相同的加权加工时间，且权重都趋近于无穷大。
证明. 首先根据引理2，可以在保证性能比不减的条件下得到一个中间实例，且该
中间实例对应的SWPT调度的最后一个子列中所有工件的加权加工时间相等。如
果SWPT (I1)只包含一个子列，则直接完成了引理的证明，该中间实例即为满足引理
条件的I2；当SWPT (I1)包含多个队列时，为表述方便仍然记该中间实例为I1。
假设SWPT (I1)包含q + 1个子队列，且最后一个子列中所有工件的加权加工时间都相
等。下面将在保证性能比不减的前提下修改SWPT (I1)最后一个子列中所有工件的权重而
得到一个中间实例I ′，该中间实例对应的SWPT调度或者只包含q个队列，或者其最后一个
子列的工件具有相同的加权加工时间，且权重都趋近于无穷大。
记SWPT (I1)中倒数第二个子队列的最后一个工件为Jk，并记SWPT (I1)最后一个子
列的工件集合为Q′。根据前面假设，Q′中的所有工件都具有相同的加权加工时间，假设都
等于pˆ/wˆ，按照第2小节中所描述的子队列划分原则可知pˆ/wˆ < pk/wk。
将Q′中每个工件Jj对应的权重wj都修改到δwj，其中δ是一个大于0的参数，记该中间
实例为I ′(δ)。如果定义
δ =
pˆ/wˆ
pk/wk
(6)
则类似于引理2的证明，当δ ∈ [δ,+∞)，SWPT (I ′(δ))是一个关于δ递增的线性函数，OPT (I ′(δ))
是一个关于δ的分段线性函数，且斜率随δ的增大保持不变或减小。依据引理1，有下述关
系：
SWPT (I ′(δ))
OPT (I ′(δ))
≤ max
{
SWPT (I ′(δ))
OPT (I ′(δ))
, lim
δ→+∞
SWPT (I ′(δ))
OPT (I ′(δ))
}
如果最大值符号取第一项，根据式(6)，Q′中所有工件的加权加工时间在I ′(δ)中都被修改
到了pk/wk，这时根据子队列划分原则，Q′中的工件都将归并到原倒数第二个子队列，也
即I ′(δ)只包含q个子队列。如果最大值符号取二项，则Q′中所有工件的权重都趋近+∞。
不难发现，经过反复执行上述的转换过程，最终或者可以得到一个相应SWPT调度只
包含一个子队列且所有工件具有相同加权加工时间的中间实例，或者得到一个中间实例，
其对应的SWPT调度最后一个子列的工件具有相同的加权加工时间，且权重都趋近于无穷
大。这两个中间实例即为满足引理要求的I2及I3。
4 单机情形下SWPT规则的竞争比分析
第二节已经指出WSPT规则的最差实例可以在引理3所构造的I2或I3中取得。下文即通
过分析I2或I3的性能比而导出WSPT规则的竞争比上界，然后再通过构造特殊实例展示该
上界也是对应问题的一个竞争比下界。
中国科技论文在线
5
定理 4. 对于问题1|rj , pmaxpmin ≤ γ|
∑
wjFj，SWPT规则是一个最优的半在线算法，且其对应
的竞争比为γ + 1。
证明. 对于引理3中描述的实例I2，既然所有工件具有相同的加权加工时间规则，由文[17]可
知SWPT调度显然是一个最优调度。
对于引理3中描述的实例I3，其对应的SWPT调度的最后一个子队列包含权重为无穷
大的工件，假设倒数第二个子队列的最后一个工件为Jk。那些权重为无穷大的工件显然是
在Jk开始加工后到达的，否则根据SWPT规则，这些权重为无穷大的工件将在Jk前加工。
在SWPT (I3)中，那些权重为无穷大的工件将在Jk完工后按照SWPT规则连续加工。而最
优调度显然是从到达时刻即开始按照SWPT规则加工这些工件，从计算性能比的角度，只
需要考虑这些工件所对应的加权流通时间之和，因此有：
SWPT (I3)
OPT (I3)
=
∑
wj→+∞wjFj∑
wj→+∞wjF
′
j
≤ max F
′
j + pk
F ′j
≤ 1 + max pk
pj
≤ 1 + γ (7)
因此可以得到SWPT规则的性能比上界为：
ρ ≤ 1 + γ (8)
下面将通过构造特殊实例显示1 + γ也是对应问题的一个竞争比下界。
考虑下述情况。0时刻到达一个加工时间及权重均等于1的工件J1，假设半在线算法
在S时刻开始加工该工件。则在S + ε 时刻到达一个加工时间为1/γ而权重为w2的工件J2，
最优调度既可以选择在0时刻开始J1，也可以选择保持机器空闲而等待到S + ε开始加工J2，
然后再加工J1，因此可以得到一个竞争比下界为：
SWPT (I)
OPT (I)
≥ S + 1 + w2(1 + 1/γ − ε)
S + ε+ 1/γ + 1 + w2(1/γ)
(9)
当ε趋近于0而w2趋近于无穷大时，上述下界趋近于(γ + 1)
综上所述，即可以得到SWPT的竞争比为γ+1，且是对应问题的最优半在线算法。
5 多机情形下SWPT规则的竞争比分析
为了分析SWPT规则在多机情形下的竞争性能，同样只需要分析引理3中构造的实
例I2及I3对应的性能比。为了表述简便，下面通过三个引理来导出SWPT规则在多机情形
下的竞争比上界。
引理 5. 对于问题Pm|rj |
∑
wjFj的一个任意实例I，其第一个工件在0时刻到达，所有工件
具有相同的加权加工时间，如果在对应的SWPT调度中，每台机器在完成其所有加工之前
不存在空闲时刻，则实例I的性能比满足：
SWPT (I)
OPT (I)
≤ 3
2
− 1
2m
(10)
中国科技论文在线
6
证明. 最优解的一个显然的下界为:
OPT (I) ≥ LB1 =
∑
i∈I
wipi (11)
文[18]基于m倍速的单机松弛，为最小化总加权完工时间问题Pm|rj |
∑
wjCj构造了一个下
界，显然该下界可以直接转化到最小化总加权流通时间问题Pm|rj |
∑
wjFj：
OPT (I) ≥ LB2 = Z ′M +
1
2
∑
i∈I
wipi −
∑
i∈I
wiri (12)
其中Z ′M是对应的m倍速单机可抢占问题的最优总加权平均忙时，根据[19]可知该最优总加
权平均忙时可以由LP调度得到，既然所有工件具有相同的加权加工时间，且SWPT调度
中任意一个工件在开工前所有机器都一直处于忙状态，因此按照SWPT调度中工件相同
的开工顺序进行非延时的连续加工对应一个LP调度，记工件Ji在该LP调度中的流通时间
为FLPi ，则
Fi ≤ FLPi + (1−
1
m
)pi (13)
同时可以将式(12)重写为：
OPT (I) ≥ LB2 =
∑
i∈I
wiF
LP
i +
1
2
(1− 1
m
)
∑
i∈I
wipi (14)
不失一般性，可以假设wj = pj，令
∑
i∈I pi = X，则根据式(11)(13)及(14) 得出I的性能比
满足：
SWPT (I)
OPT (I)
≤
∑
i∈I piF
LP
i + (1− 1m)
∑
i∈I p
2
i
max{∑i∈I p2i ,∑i∈I piFLPi + 12(1− 1m)∑i∈I p2i } (15)
根据上式分母中最大值符号的选择分两种情况讨论：
• 如果LB1 ≥ LB2，即∑i∈I piFLPi + 12(1− 1m)∑i∈I p2i ≤∑i∈I p2i，则
SWPT (I)
OPT (I)
≤
∑
i∈I piF
LP
i + (1− 1m)
∑
i∈I p
2
i∑
i∈I p
2
i
≤
∑
i∈I p
2
i +
1
2
(1− 1
m
)
∑
i∈I p
2
i∑
i∈I p
2
i
=
3
2
− 1
2m
• 如果LB1 ≤ LB2，即∑i∈I piFLPi + 12(1− 1m)∑i∈I p2i ≥∑i∈I p2i，另外考虑所有工件都
在0时刻到达可以得到LP流通时间的上界，即∑i∈I piFLPi ≤ X2/2m +∑i∈I p2i /2m，
中国科技论文在线
7
则
SWPT (I)
OPT (I)
≤
∑
i∈I piF
LP
i + (1− 1m)
∑
i∈I p
2
i∑
i∈I piF
LP
i +
1
2
(1− 1
m
)
∑
i∈I p
2
i
≤ max
{∑
i∈I p
2
i +
1
2
(1− 1
m
)
∑
i∈I p
2
i∑
i∈I p
2
i
,
X2/2m+ (1− 1
2m
)X2/m
X2/2m+X2/2m
}
=
3
2
− 1
2m
引理 6. 对于问题Pm|rj , pmaxpmin ≤ γ|
∑
wjFj，如果I2是一个相应SWPT调度只包含单块的实
例，且所有工件具有相同的加权加工时间，则I2的性能比满足：
SWPT (I2)
OPT (I2)
≤ γ + 3
2
− 1
2m
(16)
证明. 不失一般性，假设第一个工件是在0时刻到达，如果相应的SWPT调度中每台机器在
完成其所有加工之前不存在空闲时刻，则直接可以由引理5得出结论。否则假设t是所有机
器上在完成其所有加工之前最后一个空闲时刻，也即在t时刻以后所有机器都一直连续加
工工件。为表示简便，以图1为例，既然SWTP规则是一个非等待的策略，t时刻显然是一个
到达时刻，且此前到达的所有工件在t时刻都已经完工了或正在加工，假设那些正在加工的
工件对应的最晚完工时间为t′，则t′ − t ≤ pmax。下面将证明可以在保证性能比上界不超
过γ + 3/2− 1/2m的条件下删除t时刻及其以后到达的工件。
…...
…...
…...
…...
…...
…...
ᯊࠏࠡࠄ䖒ⱘᎹӊ
0 t tc
t ᯊࠏৢࠄ䖒ⱘᎹӊt
图 1: 实例I2的SWPT调度
Fig 1: The schedule obtained by SWPT for I2
构造一个辅助实例I˜2，其t时刻及其以后到达的所有工件组成，由于t时刻以后所有机器
保持连续加工，类似于引理5证明过程中下界LB2的分析，考虑I˜2所对应的m倍速单机LP调
中国科技论文在线
8
度，可以得到如下关系：
Fi ≤ FLPi + (1−
1
m
)pi + pmax ri ≥ t (17)
OPT (I˜2) ≥
∑
i∈I˜2
wiF
LP
i +
1
2
(1− 1
m
)
∑
i∈I˜2
wipi (18)
其中FLPi 为工件Ji在I˜2所对应的m倍速单机LP调度中的流通时间。
记删除t时刻及其以后到达的工件后的中间实例I ′2，则可以得到I2的性能比上界为：
SWPT (I2)
OPT (I2)
≤ SWPT (I
′
2)+
P
ri≥t wiFi
OPT (I′2)+OPT (I˜2)
≤ max
{
SWPT (I′2)
OPT (I′2)
,
P
i∈I˜2 wiF
LP
i +(1− 1m )
P
i∈I˜2 wipi+pmax
P
i∈I˜2 wi
max{Pi∈I˜2 wipi,Pi∈I˜2 wiFLPi + 12 (1− 1m )Pi∈I˜2 wipi}
}
(19)
类似引理5证明过程中对式(15)的分析有：∑
i∈I˜2 wiF
LP
i + (1− 1m)
∑
i∈I˜2 wipi
max
{∑
i∈I˜2 wipi,
∑
i∈I˜2 wiF
LP
i +
1
2
(1− 1
m
)
∑
i∈I˜2 wipi
} ≤ 3
2
− 1
2m
(20)
同时显然有：
pmax
∑
i∈I˜2 wi∑
i∈I˜2 wipi
≤ max
i∈I˜2
pmax
pi
≤ γ (21)
综上所述即可得I2的性能比上界：
SWPT (I2)
OPT (I2)
≤ max
{
SWPT (I ′2)
OPT (I ′2)
, γ +
3
2
− 1
2m
}
(22)
反复从所有机器上的最后一个空闲时刻执行上面的转换过程，最后即可证明I2的性能比上
界不超过γ + 3/2− 1/2m。
引理 7. 对于问题Pm|rj , pmaxpmin ≤ γ|
∑
wjFj，如果I3所对应的SWPT调度的最后一个子列包
含几个权重趋近无穷大且加权加工时间相等的工件，则I3的性能比满足：
SWPT (I2)
OPT (I2)
≤ γ + 3
2
− 1
2m
(23)
证明. 为表述方便，以图2为例，假设SWPT (I3)中对应权重趋近无穷大的工件最早的开工
时刻为t，t′是t时刻之前所有机器上开工最晚的工件所对应的开工时间，而t′′是t时刻之前所
有机器上开工的工件所对应的最晚完工时间，则不难发现，对应权重趋近无穷大的工件是
在t′时刻以后到达，且t′ < t ≤ t′′、t′′ − t′ ≤ pmax，为了分析I3的性能比，只需要考虑这些权
重趋近无穷大的工件，完全类似引理6证明过程中式(20)及(21) 的分析，可以导出I3的性能
比同样不超过γ + 3
2
− 1
2m
，详细的证明过程已省略。
中国科技论文在线
9
…...
…...
…...
…...
…...
…...
ঞ݊ҹৢࠄ䖒ⱘᴗ䞡䍟䖥᮴かⱘᎹӊࠡࠄ䖒ⱘᎹӊ
0 tccttc
t t
图 2: 实例I3的SWPT调度
Fig 2: The schedule obtained by SWPT for I3
定理 8. 对于问题Pm|rj , pmaxpmin ≤ γ|
∑
wjFj，SWPT规则的竞争比至少为γ + 1，且不超
过γ + 3
2
− 1
2m
，
证明. 其中竞争比上界直接由引理3、6及7导出，而下界可由如下实例取得，该实例在0时刻
到达m个权重及加工时间都为1的工件，在ε(ε → 0)时刻到达m个权重趋近无穷大而加工时
间为1/γ的工件，显然最优解应该保持所有机器空闲到ε时刻再开始加工权重趋近无穷大的
工件，由此得到的性能比即为γ + 1。
6 本文小结
本文研究了最小化总加权流通时间的单机及同速并行机半在线调度。在最大加工时间
与最小加工时间的比值不超过γ的半在线假设下，证明了SWPT规则在单机情形下是最优
的，对应的的竞争比为γ + 1；在多机情形下，SWPT规则的竞争比位于[γ + 1, γ + 3/2 −
1/2m]区间内。
中国科技论文在线
10
WSPT’s Competitive Performance for the
total flow times parallel machines semi-online
scheduling with bounded processing times
Ji-Ping Tao Yu-Geng Xi Zhi-Jun Chao
Department of Automation, Shanghai Jiao Tong University, Shanghai 200240
Abstract We consider the classical online scheduling problem over the parallel machines with the
objective of minimizing total weighted flow time. We employ an intuitive and systematic analysis
method and show that the Shortest Weighted Processing Time (SWPT) is an optimal online algorithm
with the competitive ratio of γ+1 for the case of single machine, and it is (γ+3/2−1/2m)-competitive
for the case of parallel machines (m > 1), where γ is the ratio of the longest to the shortest processing
time.
Key words analysis of algorithms，seim-online algorithms，parallel machine scheduling，total weighted
flow time，competitive analysis
参考文献
[1] S. Leonardi. A simpler proof of preemptive total flow time approximation on parallel
machines. Lecture Notes in Computer Science (including subseries Lecture Notes in
Artificial Intelligence and Lecture Notes in Bioinformatics), 3484:203–212, 2006.
[2] S. Leonardi and D. Raz. Approximating total flow time on parallel machines. Journal
of Computer and System Sciences, 73(6):875–891, 2007.
[3] J. A. Hoogeveen and A. P. A. Vestjens. Optimal on-line algorithms for single-machine
scheduling. Lecture Notes in Computer Science, 1084:404–414, 1996.
[4] C. Phillips, C. Stein, and . Minimizing average completion time in the presence
of release dates. Mathematical Programming, 82(1):199–223, 1998.
[5] X. Lu, RA Sitters, and L. Stougie. A class of on-line scheduling algorithms to minimize
total completion time. Operations Research Letters, 31(3):232–236, 2003.
[6] E. J. Anderson and C. N. Potts. Online scheduling of a single machine to minimize
total weighted completion time. Mathematics of Operations Research, 29(3):686–697,
2004.
[7] 刘培海. 平行机上的在线排序问题研究. PhD thesis, 华东理工大学, 上海,中国, 2008.
[8] J. R. Correa and M. R. Wagner. Lp-based online scheduling: From single to parallel
machines. Lecture Notes in Computer Science, 3509:196–209, 2005.
[9] H. Kellerer, T. Tautenhahn, and G. Woeginger. Approximability and nonapproxima-
bility results for minimizing total flow time on a single machine. SIAM Journal on
Computing, 28(4):1155–1166, 1999.
中国科技论文在线
11
[10] D. P. Bunde. SPT is optimally competitive for uniprocessor flow. Information Pro-
cessing Letters, 90(5):233–238, 2004.
[11] C. Chekuri, S. Khanna, and A. Zhu. Algorithms for minimizing weighted flow time.
In Conference Proceedings of the Annual ACM Symposium on Theory of Computing,
pages 84–93, 2001.
[12] N. Bansal and K. Dhamdhere. Minimizing weighted flow time. ACM Transactions on
Algorithms, 3(4), 2007.
[13] 席裕庚. 陶继平. 一种新的在线调度算法竞争比分析方法—于实例转换的方法. 系统科
学与数学, 29(10):1381–1389, 2009.
[14] J. Tao, Z. Chao, Y. Xi, and Y. Tao. An optimal semi-online algorithm for a single
machine scheduling problem with bounded processing time. Information Processing
Letters, 110(8-9):325–330, 2010.
[15] J. Tao, Z. Chao, and Y. Xi. A semi-online algorithm and its competitive analysis
for a single machine scheduling problem with bounded processing times. Journal of
Industrial and Management Optimization, 6(2):269–282, 2010.
[16] 陶冶, 陶继平, 巢志骏, and 席裕庚. 折扣加权总完工时间问题的半在线排序算法. 运筹
学学报, (3):58–66, 2009.
[17] W. Smith. Various optimizers for single-stage production problem. Naval Research
Logist. Quart, 3:59–66.
[18] M. C. Chou, M. Queyranne, and D. Simchi-Levi. The asymptotic performance ratio
of an on-line algorithm for uniform parallel machine scheduling with release dates.
Mathematical Programming, 106(1):137–157, 2006.
[19] . Goemans. Improved approximation algorithms for scheduling with release dates.
In Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms,
pages 591–598, 1997.
中国科技论文在线
12
1 引言
2 SWPT调度的块结构
3 实例转换过程
4 单机情形下SWPT规则的竞争比分析
5 多机情形下SWPT规则的竞争比分析
6 本文小结
