© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.    http://www.cnki.net

竞争比的几个结果 。在结束语中提出了有待进一步
深入研究的问题 。

1

　数学模型

假设有

k

部电梯在一个层数为

n

的建筑物内各

楼层间进行服务 ,楼层序号集合为

V

。一个服务要

求

r = ( a , b) , a , b

∈

V

(其实际意义为在楼层

a

有一顾客要求从楼层

a

乘电梯到楼层 b) 。一个服

务要求序列

R

由一些服务要求按先后顺序组成 ,即

R = ( r

1

, r

2

,

…

, r

m

)

, 其 中

r

i

=

( a

i

, b

i

) , a

i

,

b

i

∈

V

。局内电梯问题是要求在每一个服务要求出

现后就决定派哪一部电梯来完成这一服务 ,而假设
对后面可能出现的服务要求都一无所知 。

以下的所有讨论都基于如下基本假设 ;

i) 相邻楼层间的距离相等且为 1 ;

ii) 当新的服务要求出现时 ,

k

部电梯均处于闲

置状态 ;

对于

R = ( r

1

, r

2

,

…

, r

m

)

,令

C

opt

( R)

为已知

服务要求序列

R

的情况下最优调度方案完成

R

中

所有服务要求后 ,电梯所行驶的总长度 。如果调度
方案 A 对于每一个新到来的服务要求

r

i

可以不依

赖于

r

i

以后的服务要求序列来进行调度 ,那么称 A

为局内调度方案 。对于局内调度方案 A ,如果存在
与服务要求序列

R

无关的常数α和β满足

C

A

( R)

≤α

C

opt

( R) +

β

对任意可能出现的服务要求序列

r

都成立 ,则称 A

为竞争算法 ,其中

C

A

( R)

为完成服务要求序列

R

后 ,调度方案 A 的总费用 (即电梯行驶的总长度) 。

对于服务要求

r

i

= ( a

i

, b

i

)

,调度一部电梯到

达

a

i

的过程称为空载 ;电梯由

a

i

到

b

i

的过程称为实

载 ;若

a

i

= b

i

,则称服务要求

r

i

= ( a

i

, b

i

)

为退化

服务要求 。若对所提出的服务要求序列

R

无限制 ,

那么所对应的局内

k

电梯问题为 P ;若假设对任一

可能出现的服务要求

r

i

= ( a

i

, b

i

)

都有

d ( a

i

, b

i

)

> 0 ,那么所对应的局内

k

电梯问题为 P1 ;若假设对

任一服务要求

r

i

= ( a

i

, b

i

)

都有

d ( a

i

, b

i

) =

0 , 即

a

i

= b

i

,那么它对应的

k

电梯问题为 P2 (此情形

下 ,所有的服务要求都是退化服务要求 ;问题 P2 亦
称为直线上的

k

服务器问题) 。

2

　竞争算法与竞争比的几个结果

2. 1

　

k

服务器问题

直线上

k

服务器问题作为局内

k

电梯调度问题

的一个特例已有很好的研究结果

[ 5 ]

。正是关于

k

服务器问题的许多具有启发性和构造性新结果的出
现 ,近年来在国际上关于局内问题与竞争算法的研
究已成为最优化与算法领域里一个越来越热的新方

向 。由于下面局内

k

电梯调度问题的研究结果要

揭示

k

服务器问题与一般

k

电梯问题之间的内在联

系 ,这里首先介绍一个关于直线上

k

服务器问题 ,

即问题 P2 的一个研究结果 ,其证明可参见[ 5 ] 。

引理 1

[ 5 ]

直线上局内

k

服务器问题存在竞争比

为

k

的竞争算法 。

2. 2

　复位策略

复位策略 : 对于当前服务要求

r

i

= ( a

i

, b

i

)

,

当调度一部电梯移到

a

i

后 ,此电梯载客由

a

i

到

b

i

完

成服务要求

r

i

, 在下一个服务要求

r

i +

1

到来之前 ,

先将在

b

i

的电梯移回

a

i

,然后再对

r

i

进行服务 。

复位策略的基本思想是在任何服务请求到来之

前始终保持系统处于一个稳定状态 。以上的复位策

略可以使我们能够很好地对局内电梯问题与直线上
的局内服务器问题进行比较研究 。先看如下引理 。

引理 2

[ 7 ]

　令

R = ( r

1

, r

2

,

…

, r

m

)

为任一已知

服务要求序列 ,

r

i

= ( a

i

, b

i

) ,

σ

= ( a

1

, a

2

,

…

, am ) ,

C

opt

( R)

为 完 成 局 外 服 务 要 求

R

的 最 优 费 用 ,

C

opt

(

σ

)

为完成局外服务要求σ的最优费用 ,其中 σ

为服 务 要 求 序 列

R = ( ( a

1

, a

1

) , ( a

2

, a

2

) ,

…

,

( a

m

, a

m

) ) ,

那 么 如 下 不 等 式 成 立 :

C

opt

( R)

≤

C

opt

(

σ

) (

3

)

引理 3

[ 7 ]

　直线上的局内

k

服务器问题存在

c

竞争算法 , 那么直线上的局内

k

电梯问题存在竞争

比为

c +

2 的竞争算法 。上面两个引理的证明可参

见[ 7 ] , 由此可得出如下结论 :

推论 4 　局内

k

电梯调度问题存在竞争比为

k

+

2 的竞争算法 。将对应于推论 4 的竞争算法记为

算法

A

1

。

2. 3

　情形

k = n - t , t >

0

如下讨论

k = n - t ( n > t >

0

)

时局内电梯

调度问题 P1 的竞争算法设计 。

假设每个楼层均不会有超过一部的电梯 (若这

k 部电梯的初始位置是某些楼层有超过一部的电

梯 ,那么可以经过有限次移动使得每个楼层不会有

8

4

　　　　　　　　　　　　　　　　　　　　航空计算技术 　　　　　　　　　　　　　　2001 年 6 月