电梯调度算法的实现与测试之需求分析与算法设计
结对编程题目：电梯调度 现有一新建办公大厦，共有21层，共有四部电梯，所有电梯基本参数如下表所示：
其使用规定如下： 1、楼层号为0~20，其中0号为地下一层； 2、有楼层限制的电梯不在响应楼层停靠，如单双层； 3、所有电梯采用统一按钮控制 请根据上述要求设计并实现一个电梯控制程序，如果有图形显示更好了。 需求分析 四部电梯采用统一的外部按钮进行控制。 电梯内部按钮按下事件优先级高于外部按钮。 单层电梯仅在单层停靠，不在双层停靠。双层电梯仅在双层停靠，包括0层（地下一层）。 当电梯闲置时，电梯停靠在后运动到的楼层。 合理调度电梯上下行以及对内外部消息的响应。 用图形界面对程序进行展示。 我们对于合理的电梯调度行为描述如下： 电梯优先响应内部按钮事件。 对于外部事件，每次只响应与电梯运动方向的外部事件。即电梯上行时，响应电梯所在层之上的外部事件；电梯下行时，响应电梯所在层之下的外部事件。 响应内部事件时，优先响应与电梯运动方向的内部事件。即电梯上行时，响应电梯所在层之上的内部事件；电梯下行时，响应电梯所在层之下的内部事件。 同一个外部事件可以有多个电梯同时响应，也可以是单部电梯进行相应。这是由当前4部电梯具体的运动状态所决定的。 算法设计 每个电梯独立运行，用消息队列InReqList存储电梯的停靠消息。每部电梯的消息队列相互独立。 在电梯内部按钮按下时，将消息放入此电梯的InReqList队列队列。因为内部按钮按下的楼层是电梯必须停靠的楼层，所以每次从InReqList队列中找出合适的楼层，并停靠。 在电梯外部按钮按下时，进消息放入每部InReqList队列。因为外部按钮按下的楼层不一定是每部电梯都要停靠的楼层，所以要根据此电梯具体的InReqList队列找出适当的时候响应此外部事件。 先从单部电梯的调度里流程开始讨论，电梯的初始状态为闲置状态，在外部按钮事件的响应下唤醒电梯，电梯开始运动，调度图如下：
图1 单部电梯调度图
在进行多部电梯的调度时，因为每部电梯的内部事件相互独立，所以只需要修改外部事件的响应规则即可。 在外部按钮按下时，遍历4部电梯的本层消息属性，若本层已有内部消息，则放弃写入；否则，在本层写入外部消息。 在电梯停靠时，清除停靠电梯本层的消息，然后遍历其他电梯的消息属性，若其他电梯本层为外部属性，则清除消息；否则，不进行任何处理。
图2 多部电梯调度图
到此，电梯调度问题的核心是如何在消息队列中寻找适楼层。这个问题很容易解决： 由于电梯楼层固定为21层，可以用一维数组InReqList[21]保存一部电梯消息队列。当数组值为InReqList[i]=0时，表示第i层没有停靠消息，电梯不需要再此层停靠；当数组值为InReqList[i]=1时，表示第i层有一个内部按钮按下消息，电梯需要在此层停靠；当数组值为InReqList[i]=2时，表示第i层有一个外部按钮按下消息，电梯需要在此层停靠； 若当前楼层为 now_floor，电梯上行时，从InReqList数组的第now_floor+1项到第20项中，第一个数值不为0的项，其数组下标值即为消息队列中的适楼层值。 若当前楼层为 now_floor，电梯下行时，从InReqList数组的第0项到第now_floor-1项中，第一个数值不为0的项，其数组下标值即为消息队列中的适楼层值。 当上行时，本层之上消息队列为空，之下队列不为空，则将电梯运动状态改为下行。下行则反之。 当消息队列全为空时，电梯闲置。
