收稿日期

:2001 - 04 - 18

作者简介

应柏安

(1962 - ) ,

男

讲师

主要研究方向为计算机应用及控制。

局内电梯调度问题与竞争算法

应柏安

徐寅峰

朱　云

(西安工程科技学院 , 陕西西安 710048 ;西安交通大学管理学院 , 陕西西安 710049 ;

西北电业职工大学 ,陕西西安 710054)

摘　要

经典的优化理论大多是在已知条件不变的基础上给

出最优方案

(

即最优解

) ,

其最优性在条件发生变化时就会

失去。局内问题与竞争算法则是针对特定的优化问题来研

究这样的方法

它在变化因素的每一个特例中都能给出一个

方案

使得这一方案所得到的解离最优方案给出的解总在一

定的比例之内。本文首先提出了局内电梯调度问题

设计

了解决该问题的两个不同的竞争算法

并证明了这两个竞争

算法的竞争比分别为

k +

和

n - k +

1 ,

其中

为电梯的个

数

, n

为楼层数。

关键词

局内问题

;

竞争算法

;

竞争比

中图分类号

: TB114. 1

文献标识码

引言

现实生活中的许多经济现象通常都具有非常强

的动态特征 ,一切事物通常都是随着时间的推移而
不断变化的。经典的优化理论大多是站在旁观者的

立场上看问题 ,即首先确定已知条件 ,然后在假设这
些已知条件不变的基础上给出最优方案 (即最优
解) 。条件一旦发生变化 ,这种方法所给出的最优方
案就会失去其最优性。在变化的不确定因素对所考

虑的问题影响很大时 ,经典的优化方法有 :一是将可
变化的因素随机化 ,寻求平均意义上的最优方案 ;二
是考虑可变化因素的最坏情形 ,寻求使最坏情形达
到最优的方案。这两种处理方法对变化因素的一个

特例都可能给出离实际最优解相距甚远的解 ,这显
然是难以满足实际要求的。那么是否存在一种方

法 ,它在变化因素的每一个特例中都能给出一个方
案 ,使得这一方案所得到的解离最优方案给出的解
总在一定的比例之内呢 ? 近年来兴起的局内问题与

竞争算法的研究结果在一定意义上给如上问题一个

肯定的答案

[ 1 —5 ]

。

电梯调度问题的实际背景是一个高层建筑 (宾

馆或写字楼) 在其入口处及各层之间通常有多部电

梯来完成人们上下按所提出的一个接一个的具体服

务要求。假设一共有

部电梯来完成这些服务 ;并

且每个服务响应均由一个电梯控制器调度各部电梯

来完成每个服务要求。考虑如下两个问题 :1) 事先
给定一个要求服务的任务序列 ,如何调动电梯使得
相关的费用最少 ? 2) 如果服务要求是在服务过程中
一个个地接到的 ,这样每一时刻只能知道在此之前
的任务序列与服务过程 ,那么如何调动电梯费用较
少呢 ? 电梯调度问题的优化目标是所有电梯所行驶
的总长度最少 (这个长度同费用成正比) 。问题 1 是
个局外 (off - line) 问题 ,而问题 2 是一个局内 (on -

line) 问题。两者的不同点在于可知的服务要求序列

是全部还是局部。问题 1 的最优解可以用动态规划
方法来求得 ;而问题 2 却难以处理。事实上 ,服务要
求序列对调度方案有着致命的影响 ,随着服务要求
出现的不同 ,最优调度方案也随之发生变化。

局内电梯调度问题是局内

服务器问题的一

个推广。局内

服务器问题是近年来优化理论与

竞争算法领域的一个热点研究项目。在国际上已有

许多这方面的研究成果

[ 1 —5 ]

,国内这方面的研究展

开的并不多 ,主要有堵丁柱教授的一篇介绍性文章
及在局内 k 出租车调度问题上的初步结果

[ 6 ]

。

本文首先建立局内

电梯调度问题的数学模

型 , 给出了局内

服务器问题与局内

电梯调度问

题的内在联系 , 同时给出了

电梯问题竞争算法与

第 31 卷　第 2 期　　　　　　　　　　　

航空计算技术

　　　　　　　　　　　　　2001 年 6 月