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

摘要

Most traditional optimization theories produce th e optimal solutions for problems at hand on the basis that the known conditions are unchanged, whic h may lost their optimality in most cases with conditions vary. The researches o n on-line problem and competitive algorithm try to explore strategies which can produce solutions that is in a certain range proportional to the optimal solutio n for a given problem even in worst cases. This paper gives two competitive algo rithms for on-line scheduling of k　elevator problem using the position main taini ng occupied strategy, which have k+2 and n-k+1 competitive ratios respec tively, where k is the number of elevators and n is the number of floors of a constructi on.%经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解), 其最优性在条件发生变化时就会失去。局内问题与竞争算法则是针对特定的优化问题来研究这样的方法,它在变化因素的每一个特例中都能给出一个方案,使得这一方案所得到的解离最优方案给出的解总在一定的比例之内。本文首先提出了局内电梯调度问题, 设计了解决该问题的两个不同的竞争算法,并证明了这两个竞争算法的竞争比分别为k+2和n-k+1,其中 k为电梯的个数,n为楼层数。