电梯调度算法(-)

时间:2022-07-02 14:31:57

     今天我们做的是一个结对编程作业,其实对结对编程,我也有两种看法,第一:提高自己,第二:埋没自己。关键看是如何去利用结对编程,才能达到事半功倍的效果。这次我们做的是一个关于电梯控制调度的程序,这个程序的算法思想做了一天,初步有了电梯调度算法的框架。由于电脑换了,拿到联想服务站维修,只在3月9日,初步了解了一下电梯系统运行的构架。具体安排,暂时还未公布。

    (结对人员苏林东&吴威)

     题目:

     试想一下,我们正在构建一个高大的办公楼,它有大约电梯配置如下:大厦有21层, 4部电梯,很多乘客使用这些电梯的日常(旅客重量:平均70公斤最大120公斤,最小45公斤)。其他常量数据:电梯速度,开/关门时间,乘客的时间要在/走出电梯。

 

  电梯名称

停靠层数

乘客限制

重量限制

     1

所有楼层

10

800 kg

     2

所有楼层

10

800 kg

     3

所有楼层

20

1600 kg

     4

所有楼层

20

2000 kg

     想先来谈一下大概的思路:

     电梯外部是一个总控制台,但它只有上和下的按钮(最底层只有上,最高层只有下)它负责寻找合适的电梯进行调度,找到合适的电梯之后,可以控制这个电梯,并把电梯信息传给内部控制器进行控制。当电梯外部按下楼层上或下键时,相当于同时按下四部(这里有四部电梯)电梯,这个时候从四部电梯中调度一部进行响应,具体算法是,选择当前没有在运行,或者运行方向与按钮方向相同的并且要经过此楼层的电梯,如有一部,便调这个电梯,若有多部,那么就选择在满足上面条件下与所处楼层最接近的一部电梯。如果没有,则选择等待。当电梯内部按下一个楼层按钮的时候,当电梯停止或者同向可以到达的时候,系统把这个楼层设置为要停靠楼层,当电梯不符合条件是,则等待,到达目标后才执行这个任务。(举例:如果乘客在5层,而现行目标是10层,可乘客又按下了3层,那么这个电梯先上10层,再下第三层)。

 (1)需求分析

   ①、模拟21层楼的电梯系统。该楼有一个自动电梯,能在每层停留。楼层由下至上依次称为地下层、第一层至第二十层,其中第一层是大楼的进出层,即是电梯的“本垒层”,电梯“空闲”时,将来该层候命。楼层从下到上的编号为:0-20。除了地下层外,每一层都有一个要求向下的按钮除了第二十层外,每一层都有一个要求向上的按钮。对应的变量为:CallUp[0..19]和CallDown[1..20]。电梯内的21个目标层按钮对应的变量为:CallCar[0..20]。

   ②、电梯一共有七个状态,即正在开门(Opening)、已开门(Opened)、正在关门(Closing)、已关门(Closed)、等待(Waiting)、移动(Moving).

   ③、 乘客可随机地进出于任何层。对每个人来说,他有一个能容忍的最长等待时间,一旦等候电梯时间过长,他将放弃。对于在楼层内等待电梯的乘客,将插入在等候队列里,每一层有两个等候队列,一队要求向上,一队要求向下,用链队列来实现。对于在电梯内的乘客,用四个乘客栈来实现,该乘客要去哪一层,就把他放在相应编号的栈中,对应变量为EleStack[0…3]。

  ④、模拟时钟从0开始,时间单位为0.1秒。人和电梯的各种动作均要耗费一定的时间单位(简记为t):

           有人进出时,电梯每隔40t测试一次,若无人进出,则关门

           关门和开门各需要20t

           每个人进出电梯均需要25t

           电梯加速需要15t

          上升时,每一层需要51t,减速需要14t

          下降时,每一层需要61t,减速需要23t

           如果电梯在某层静止时间超过300t,则驶回1层候命。

  ⑤、按时序显示系统状态的变化过程:发生的全部人和电梯的动作序列。

(2)算法分析   

         我们将电梯分为三种状态,第一种状态,正在向下行使中,第二种状态,正在向上行驶中,第三种状态,处于停止中。由于第一种状态与第二种状态类似,因此,我们下面只讨论第一种和第三种状态是对电梯的调度。

         ①、对于第一种状态(正在向下),分为有人与没人两种情况。

         当第一种状态的电梯里(即正处于向下行使)有人时,那么电梯向着最近的目标驶去,如果此时中途有人(即当前层和目标层之间)有向下的请求且电梯可以到达,那么改变电梯的目标层,使电梯在有人请求层处停止。

        当第一种状态的电梯里(即正处于向下行使)没人时,假设此时的电梯所在的层数为i,那么搜索 i-1到0层间是否有向下的请求,如果有那么将最近的一个请求所在楼层设为目标层,如果没有,那么在搜索0到i-1层间是否向上的请求,如果有将最远的一个请求所在的楼层设为目标。

       第二种情况与第一种类似,所以不再叙述。

       对于第三种情况的电梯即处于开门状态或者处于关门但是没有明确目标的电梯。同样分为有人与没人两种状态,若有人,那么找到这些人想去的最近的目标,若没人将目标设为整个楼层中请求最早的地方。

       这就是算法的大体思路。

(3)结构模块化设计

    暂时还没完成。