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

超过一部的电梯 ,并且这样移动的总费用一定小于
或等于常数

( n -

1

)

, 这个常数对于竞争比的讨论

没有影响

[ 1 ]

。

对于服务要求序列

R = ( r

1

, r

2

,

…

, r

m

)

,由于

问题 P

1

不存在

a

i

= b

i

的情形 ,给出如下局内电梯

服务问题的调度方案 A

2

,对于当前的服务要求

r

i

=

( a

i

, b

i

) , a

i

≠

b

i

。i) 当

a

i

楼层有电梯 ,

b

i

楼层也有

电梯时 ,

a

i

楼层的电梯载乘客由

a

i

到

b

i

,同时

b

i

楼

层的 电 梯 移 到

a

i

; 此 时 完 成

r

i

的 费 用 为

C =

2

d ( a

i

, b

i

)

,并且仍不存在电梯超过一部的楼层 ;记

为

a

i

→

b

i

→

a

i

;

ii) 当

a

i

楼层有电梯 ,

b

i

楼层没有电梯时 ,

a

i

楼

层的电梯载乘客由

a

i

到

b

i

;此时完成

r

i

的费用为

C

= d ( a

i

, b

i

)

, 并且仍不存在电梯超过一部的楼层 ;

记为

a

i

→

b

i

;

iii) 当

a

i

楼层没有电梯 ,

b

i

楼层有电梯时 ,将

b

i

楼层的电梯移到

a

i

,然后载乘客由

a

i

到

b

i

;此时

完成

r

i

的费用

C =

2

d ( a

i

, b

i

)

, 并且仍不存在电梯

超过一部的楼层 ;记为

b

i

→

a

i

→

b

i

;

iv) 当

a

i

楼层没有出租 ,

b

i

楼层也没有电梯时 ,

此时可调度离

a

i

最近的且有电梯的楼层 (设为

c

i

)

上的电梯到楼层

a

i

,然后载乘客从

a

i

到达

b

i

;记为

c

i

→

a

i

→

b

i

;此种情形下的费用为

C = d ( c

i

, a

i

) +

d ( a

i

, b

i

)

。

定理 5 调度方案

A

2

的竞争比为 1

+ ( n - k)

。

证明 :对于任一服务要求序列

R = ( r

1

, r

2

,

…

,

r

m

)

,完成

R

的任何调度方 A ,其费用

C

A

( R)

显然

满足如下不等式 :

C

A

( R)

Ε

6

m

i =

1

d ( a

i

, b

i

)

因为

6

m

i =

1

d ( a

i

, b

i

)

是电梯载客行驶的总长度 ,这是

完成

R

所必需付出的费用 。

对于方案 A

2

的 i) ,ii) ,iii) 情形 , 完成任一

r

i

的

费用最多为最优费用 (即

d ( a

i

, b

i

) )

的 2 倍 。而对

情形 iv) , 其附加费用为

d ( c

i

, a

i

)

。由于

c

i

是距离

a

i

最近的有车的顶点 , 那么从

c

i

到

a

i

的路径最多经

过 (

n - k -

1 ) 个没有车的顶点 , 所以有

d ( c

i

, a

i

)

≤

n - k

。于是完成任一

r

i

的费用最多为最优费用

即

( d ( a

i

, b

i

) )

的 1

+ ( n - k)

倍 。推导如下 :

C

A2

( R)

≤

6

m

i =

1

{ m ax [ d ( b

i

, a

i

) , d ( c

i

, a

i

) ] + d ( a

i

, b

i

) } +

β

其中β为在接受任务

r

1

之前使每个顶点均有不超

过一部电梯所需要的费用 ,这一费用小于某个常数 。
由于

a

i

≠

b

i

, d ( a

i

, b

i

)

≥1

,

则

C

A

2

( R)

6

m

j =

1

d ( a

i

, b

i

)

≤1

+

6

m

j =

1

m ax [ d ( b

i

, a

i

) , d ( c

i

, a

i

) ]

6

m

j =

1

d ( a

i

, b

i

)

,

由于

d ( c

i

, a

i

)

≤

( n - k) , d ( a

i

, b

i

)

≥1 ,我们有

C

A

2

( R)

6

m

j =

1

d ( a

i

, b

i

)

≤1

+

6

m

j =

1

d ( n - k)

6

m

j =

1

=

1

+ ( n - k)

,

则

C

A2

( R)

≤

[

1

+ ( n - k) ]

・

6

m

j =

1

d ( a

i

, b

i

)

证毕 。

3

　算法

A

1

和

A

2

的比较

在上一节我们给出了局内

k

出租车调度的两

个算法 A1 和 A2 , 其中 A1 对问题

P

成立 , 而 A2

仅对问题 P1 成立 , 考虑问题 P1 时这两个算法孰优
孰劣 , 或者说在何种情况下哪个更优呢 ? 对此我们
可作如下分析 。

局内算法优劣的标准是相应算法的竞争比 ,算

法 A1 和 A2 的竞争比分别为

c

A1

= k +

2

c

A2

=

1

+ ( n - k)

使

c

A1

和

c

A2

相等 , 可以求出算法 A1 和 A2 的竞争

比等价的

k

值 :

k +

2

=

1

+ ( n - k)

所以有 ,

k =

n -

1

2

显而易见 , 我们可得出如下结论 :

定理 6 　对问题 P1 , 在算法竞争比方面 , 当

k

< ( n -

1

) /

2 时 , 算法 A1 比算法 A2 优 ;反之 , 当

k

> ( n -

1

) /

2 时 ,算法 A2 比算法 A1 优 。

4

　结束语

本文所讨论的局内电梯调度问题的优化指标为

电梯所走的总路程 。对于文中所引入的问题 P1 和

P2 有许多有待进一步深入研究的理论问题及一些

未解决的有关猜想

[ 1 —4 ]

。下述问题有待于深入探

讨 :

a. 对于局内电梯调度问题 ,如果换一个角度来

9

4

第 2 期 　　　　　　　　　　　　应柏安等・局内电梯调度问题与竞争算法