Scheduling for On-line Elevator Problem and Competitive Algorithm
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.
NETL
NSTL
万方数据
维普
