电梯调度问题分析
题目 电梯调度问题分析
摘要
当前随着建筑物的使用功能与客流状况的不断变化，对电梯的服务要求越来越高，电梯配置问题也变得日益复杂，对电梯的垂直交通流预测，可对电梯的拥挤程度做出预测，对电梯群的优化设计产生的经济效益与社会效益也受到全社会极大的关注。
对于问题一，由于要对电梯垂直交通流分析，所以我们考虑利用拟合方式建立函数模型，同时考虑乘客等待时间的长短、乘电梯时间的长短、把所有人运上去的总时间、电梯响应呼梯的快慢、召唤厅站客流量的大小、电厢内乘客人数的多少、电梯运送完所有乘客的总时间，最后对新取的六个点进行拟合，用SPSS 进行三次函数拟合。通过函数：
312677.76816.65713017.808Y x x =-- 得出从7:00-7:30上班人数对电梯的需求量呈递增趋势，并在7:25左右达到最大。
对于问题二，为了直观描述居民楼内买早饭期间电梯的拥挤程度，仍然采用拟合方法，采用深圳某大厦的人流量作为类比对象，每隔六分钟取一值，对所取的值处理后用SPSS 进行函数拟合，再把上行与下行的函数整合后得出早点期间电梯的拥挤程度图。通过对图像的分析，得出最拥挤的时间点出现在6:40左右。
对于问题三，从电梯的角度来说，要使拥挤程度最小即为电梯的运行效率最大。因此，为使电梯的运行效率最高，我们针对存在问题提出了电梯调度的选择性方案。
对于问题四，要建立具有普适性的电梯配置方案，针对电梯的优化调度使用，我们采用基于人工免疫算法的动态分区优化模型的两种方法进行建立模型求解。根据电梯运行时间与运行距离之间的关系()k θ和电梯往返运行时间和电梯搭乘人数的关系：
()()()()T E X E Y E Z E S =+++
从而确立目标函数以及约束条件，建立具有普适性的电梯配置方案。通过求解，发现动态分区控制法对电梯优化是有效可行的方法，并求出结果：1号电梯负责1到18层，2号电梯负责19到36层。
关键词 拟合函数 动态分区优化模型 整数非线性规划模型
一、问题背景和重述
1.1问题背景
电梯是一种以电动机为动力的垂直升降机，亦称垂直电梯，可以定义为在垂直方向运送人或货物的运输工具。电梯的使用，大大方便了人们的生活。繁华的都市里，人口的高度集中，也越来越使得电梯成为人们生活工作中不可或缺的交通工具。与此同时，电梯的安全性和运送速度也是人们主要关注的问题。日常生活中，随着人们生活节奏的加快，高楼中电梯的拥挤问题也日趋严重，尤其是在早晚人们上下班的时候，拥挤问题更甚。特别当高楼在遭遇紧急状况的时候，往往会因为垂直交通拥挤而造成大量的损失。为实现电梯的合理选型配置，须对大楼内电梯交通流做出准确预测，以此来达到合理分配客流的目的。因此对电梯这一垂直交通进行交通流预测，分析电梯在几个较为拥堵的时间段的拥挤程度显得尤为重要。
1.2问题重述
假设一栋居民楼为36层，只有一台电梯。每层有两户人家，每天早晨6:30到7:00之间每户都有人外出买早点（半个小时之内来回，又上又下），在7:00到7:30之间，每户至少有三人外出上班（只有下）。
1、请查找相关资料，预测早晨上班期间的电梯垂直交通流。（7:00-7:30）
2、请描述买早点期间电梯的拥挤程度。（6:30-7:00）
3、请从电梯的角度出发，给出电梯合理的响应方案，使得电梯的拥挤程度最小。
4、利用已有的垂直交通流理论，结合我国当前垂直交通现状，建立具有普适性的电梯
配置方案，给出物业部门一份合理的管理方案。
二、问题分析
2.1问题一的分析
要预测早晨上班期间的电梯垂直交通流，就要考虑乘客等待时间的长短、乘电梯时间的长短、把所有人运上去的总时间、电梯响应呼梯的快慢、召唤厅站客流量的大小、电厢内乘客人数的多少、电梯运送完所有乘客的总时间。首先，我们借用深圳某大厦的客流量图统计数据，我们假设从居民楼到上班时间为一小时，将客流量图中8:00-8:30的数据代替居民楼7:00-7:30的数据，然后进行每隔六分钟取一值，接着我们对所取的值计算出在六点总和中的比率。主要考虑到观测数据受随机误差的影响,为寻求整体误差最小、较好反映观测数据的近似函数，因此我们用六个点的比率分别乘以72?3，最后对新取的六个点进行拟合，拟合方法为用SPSS进行三次函数拟合。
2.2问题二的分析
根据题意，要描述买早点期间电梯的拥挤程度，我们要考虑停梯次数、乘客的平均等待时间、乘客的平均乘梯时间，考虑到观测数据受随机误差的影响,为寻求整体误差最小、较好反映观测数据的近似函数。同问题一，我们用中午12:00-12:30的客流量代替早餐7:00-7:30客流量，然后进行每隔六分钟取一值接着我们对所取的值计算出在六点总和中的比率。然后我们用六个点的比率分别乘以72?3，最后对新取的六个点进行拟合，拟合方法为用SPSS进行三次函数拟合。
2.3问题三的分析
题目要求从电梯的角度出发，给出电梯合理的响应方案，使得电梯的拥挤程度最小。要使电梯的拥挤程度最小，也就是要求电梯的运行效率达到最高。因此，我们针对实际情况，从电梯角度出发，给出建议方案。
2.3问题四的分析
要利用已有的垂直交通流理论，结合我国当前垂直交通现状，建立具有普适性的电梯配置方案，就要研究考虑垂直交通流分析和电梯群控制论是电梯配置问题中的两个方面。目前提高电梯智能化的方法主要包括：专家系统决策、遗传算法优化法、人工神经网络、模糊逻辑控制等。因此，我们对上下行高峰模式的调控模式进行研究，针对电梯的优化调度使用基于人工免疫算法的动态分区优化模型进行建立求解。
三、模型假设
1、假设各层乘客只在本层等候电梯，所有下行乘客直达底楼，上行乘客直达各自所在
层；
2、假设排除意外情况的干扰，如电梯故障、乘客空叫电梯问题等；
3、假设乘客全部按照本文优化电梯群控调度模型所设计的方案乘坐；
4、假设忽略进入电梯的乘客存在的个体差异，并且进入的乘客不超过额定得承载人数；
5、假设乘客只有使用电梯出行，此外就不再考虑其他性质的交通流。
四、符号说明
五、模型建立与求解
5.1问题一模型的建立与求解
根据题意，我们要分析预测早晨上班期间的电梯垂直交通流，即分析上班期间居民楼内下楼的人流量。对此，我们采用深圳某办公楼大厦的电梯日人流量作为参照对象，通过类比的方式获得统计数据。接着,为了描述上班时间的垂直交通流，采用SPSS进行函数拟合。最后，通过函数图像分析求解。
由于居民楼内上班时间为7:00-7:30，为联系实际，使得所求结果更具意义。我们假定人们上班途中花费1小时，所以采用深圳某办公楼大厦的电梯日人流量图中8:00-8:30的数据，为使结果精确，每隔六分钟取一组数据，得到如下结果:
时间X 7:00 7:06 7:12 7:18 7:24 7:30 总需求量y
24
36
64
78
78
84
居民楼内人流总量最少为216。先算出8:00-8:30内六个点分别占六点总需求人数的百分比，然后算出居民楼总需求人数的百分比，也是六个点。因此，居民楼人流量类比的结果为：
216A a =?
同样地，通过类比，计算出抽取的六个点的总需求量的结果：
时间X 7:00 7:06 7:12 7:18 7:24 7:30 总需求量y
15
21
39
45
45
51
据进行函数拟合。 5.1.2模型的求解
通过分析深圳大厦人需求总数的图像，决定对六个点进行三次函数拟合，软件输出函数方程为：
312677.76816.65713017.808Y x x =-- 函数的图像为：
图1 电梯需求量总数
由函数图像分析，我们发现从7:00-7:30上班人数对电梯的需求量呈递增趋势，并在7:25左右达到最大。
为了确保结果的可靠性，我们对问题一的模型进行检验。首先，我们对问题一SPSS 的输出结果进行分析：
我们发现，对于三次模拟函数来说0.9541
R=<恒成立。,因此模型与数据相关性良好，建立的三次函数模型是符合要求的。
5.2问题二模型的建立与求解
根据题意，要描述买早点期间电梯的拥挤程度，同问题一，我们采用深圳某办公楼大厦的电梯日人流量作为参照对象，通过类比的方式获得统计数据。接着,为了描述买早点期间电梯的拥挤程度，我们采用SPSS进行函数拟合。最后，通过拟合函数图像进行分析求解。
5.2.1模型的建立
由于买早餐时的拥挤程度与买午餐时相似，于是我们采用深圳某大厦的12:00-12:30的人流量作为类比对象，数据的采集采取与问题一相似的方式每隔六分钟取一点，共六点，得到如下结果：
趋势。因为与第一题相似，所以仍然决定对数据进行拟合。但为了确保结果的准确性，我们决定用多种拟合方式，并将结果进行比较。下面我们对这六组数据与居民楼进行类比，数据处理方式与第一题相似。由于买早点人数为每户至少一人，所以我们对人数的计算公式为：
272
Y a
=?
接着我们用Excel对数据进行处理，得到如下结果：
拟合，并借此得到函数模型。因此，利用相似的方法，我们对午饭时间大厦下楼的需求人数进行取点，得到如下结果：
分别得到上楼和下楼电梯需求量的函数模型。不同于问题一的是，时间的六十进制与数
字的十进制在拟合时会产生冲突，所以我们这样处理时间：
时间=原时间-0.30
5.2.2模型的求解
我们用SPSS对处理过的上楼人数的数据进行分析，得到了上楼时电梯需求量的函数模型：
等式样方 F Df1 Df2 sig 常量B1 B2 B3 函数901 13.727 2 3 0.031 -887.243 192.518 0 -1.126 承受力915 43.023 1 4 0.003 2.046E-8 11.689
指数914 42.587 1 4 0.003 0 1.900
得到上楼时模拟函数的图像和公式：
图2 上楼时模拟函数的图像
接着我们对下楼人流量数据进行同样的处理，得到：
等式样方 F Df1 Df2 sig 常量B1 B2 B3 函数869 9.968 2 3 0.047 -15488.373 3843.418 0 -34.832 承受力717 10.130 1 4 0.033 1.351E17 -19.729
指数722 10.411 1 4 0.032 1.483E10 -3.221
：
3
2
34.8323843.41815488.373
Y x x
=-+-
因此对于最终的拥挤程度，我们可以利用这样一个函数模型进行描述：
12
33
3
(Y)
1.126192887.243(34.8323843.41815488.373)
35.9584035.41816375.616
Y Y abs
x x x x
x
=+
=-+-+-+-
=-+-
由SPSS 软件绘出函数图像：
图3 上楼时模拟函数的图像
由此模拟出早饭期间的人流量在六点十二左右达到最大值，同时也是拥挤程度最大的时候。
5.3问题三电梯合理的响应方案
通过对题目的分析，我们发现电梯的拥挤程度最小也就是电梯的运行效率最高。因此为使电梯的运行效率最高，采取的方案为：
1、当电梯在运行过程中，没有到达目的地，如在中途遇到一个同向的请求，且此地点未到达，则电梯在未满员的情况下响应要求，满员则不相响应要求。
2、当电梯在运行过程中，没有到达目的地，如如在中途遇到一个同向的请求，且此地点未已经过，则电梯在到达目的地后返回途中未满员的情况下响应要求，满员则不相响应要求。 5.4问题四模型的建立与求解
根据题意，要利用已有的垂直交通流理论，结合我国当前垂直交通现状，建立具有普适性的电梯配置方案，就要研究考虑垂直交通流分析和电梯群控制论是电梯配置问题中的两个方面。因此我们对上下行高峰模式的调控模式进行研究，针对电梯的优化调度，使用基于人工免疫算法的动态分区优化模型来对问题进行解答。 5.4.1模型一的建立
为建立具有普适性的电梯配置方案，现假设一建筑楼层数n ，第i 层的人员数为(1i n)i p ≤≤，电梯的开关门时间为d ，最大加速度为a ，而且加速度的变化率为q ，实际经验证明一组电梯的数量定为偶数是优于奇数的。电梯往返时间是电梯服务区最底层d ，每个电梯承载的人数M 之间的函数关系。设往返时间函数为(),,T f d n M =。 电梯不分区进行调度时，乘客的平均往返时间为：
()01,,Pf N M T QM
=
为将所配置电梯把能否以尽量少的时间把乘客运送完毕作为确定电梯调度方案优劣的标准，当对电梯进行分区调度时，设可以分成(1)I i I =个区域。每个区域的最底
层为(1
)i d i I =，含有的电梯数目(1)I i I =。则运算完去区域I 的乘客的时间为：
()
,,i i i i i
Pn f d n M T NMq =
各个区域中运送时间最长的那个时间即为运送完所有乘客的时间：
()
1,,i i i m i q i
Pn f d n M T Max
NMq ≤≤= 所以确定最优调度方案就是确定使得()
1,,i i i i q i
Pn f d n M Max NMq ≤≤最小时的I ，i b ，i l ，i n 值，
而()1,,i i i i q i
Pn f d n M Max NMq ≤≤最小对应的I ，i b ，i l ，i n 便是最优调度方案，即: Min ()
1,,i
i i i q i
Pn f d n M Max NMq ≤≤ 5.4.2模型一的求解
对于模型的求解考虑到枚举法只适用于分区少的情况，而当分区较多时，将会有很
多种很配方案，变量难以控制，再用枚举法将会有很大的计算量，显然是行不通的。通过蒙特卡罗法进行计算，我们分析用随机取样取610个点，用概率理论计算一下可信度。假设目标函数落在高值区的概率分别为0.01和0.00001，则当计算610个点后，有任何一个点落在高值区的概率为：
9...99.099.01100000=-， 10000010.99999=0.999954602-
则可以说明，用蒙特卡罗发进行计算的可信度非常高。最后我们求出的结果是：1号电梯负责1到18层，2号电梯负责19到36层。 5.4.3模型二的建立
通过思维拓展，我们同样运用动态分区优化法来求解此题。为了简化模型，这里可以约定，开、关门及上下乘客的时间为5秒。本文采用匀加速的计算方法，设楼层高为4米，最大速度为2/m s ，加速度为1.52/m s ，这样可以大概估计出每一层楼的运行时间为3.33s ，高峰时段设为十五分钟。
上班高峰时，等待乘电梯的到达人数符合泊松概率分布：
0,1,2......x k n = ()()/!k P x k e k λλ-==?
我们求得电梯新增的平均等待人数是7人/分钟，本文假定高层（19~36）作息时间比低层（1~18）的作息时间早五分钟。
用Matlab仿真，实现电梯上行高峰的模拟算法，做10次独立的模拟，求出四个指
5.4.5管理方案的制定
1、经过查询相关资料和某些运行实例，对于物业可以考虑将楼分为高低层分管模式，
例如本题在现行电梯用于低层运行（2~18）的基础上，再增设一台电梯分管高层（19~36）。
2、电梯对于不同的时间段实行不同的控制策略，群控控制策略，经查阅资料了解到，
当前电梯多实行动态策略来应对复杂多变的任务，根据当前交通模式来确定合理的群系统控制策略，即不同的时段电梯有不同的响应方式。例如，上行高峰交通时段，群控系统控制电梯在一楼等待，缩短电梯的运行时间间隔提高运输效率。
3、优化电梯自身的硬件设施配置，提高电梯的运行速度，经过仿真模拟电梯的运行速
度提高。
4、在电梯运行高峰时间段，电梯待客区应该安排值班人员，保证乘客有序使用电梯，
杜绝不必要的电梯空叫和安全问题的出现，从而提高电梯的使用效率。
六、模型评价和改进
6.1模型的评价
6.1.1模型的优点
1、文中对乘客侯梯情况进行了假设，，假设乘客处于等待条件下，既不脱离实际又使模
型得到了简化，对问题的分析和处理提供了方便。
2、本文用到的所有理论和算法都是建立在前人研究和实际情况的基础上，有理有据，
使得到的结果更具有现实意义。
3、模型运用的方法简单，适用性强，具有可推广性便于人们接受，且能把多目标、多
准则又难以全部量化处理的决策问题化为多层次单目标问题，使得计算简便，并且所得结果简单明确。
4、模型考虑的因素比较全面，具有可靠性。
1、在对电梯调控方案进行改善时，只考虑电梯停靠次数、平均等待时间、平均乘梯时
间使得结果与真正的最优值可能有一些误差，实际情况下，还应考虑其它因素，如其它交通流等，因此该方案有待进一步的研究。
2、模型的数据相对片面，结果过于理想化。
6.2模型的改进
在模型的分析与建立过程中，忽略了一些因素，在模型改进的时候，可以将上述过程中忽略的因素加以考虑。可以对每个因素间的联系进行深入的探索，使考虑问题更全面，分析更加合理符合实际情况，预测就更加准确。模型的数据存在偶然性，使得模型的准确度不是特别高，在改进的时候，可以获得更多更全面的数据，这样可以使得模型更加具有说服力。
七、模型推广
拟合函数主要考虑到观测数据受随机误差的影响,为寻求整体误差最小、较好反映观测数据的近似函数。对于处理资源资源分配问题有很大的实际意义，可以进行全面的推广，只需要在模型中做稍许的更改，就可以解决任意楼高，任意电梯数，任意人数，的模拟。另外本模型在社会的很多领域都可以用到，例如解决库存问题、乘梯问题、排序问题等，用整数规划来进行求解，可以是问题得到简化。
人工免疫算法的动态分析模型对于交通流分析和电梯群控制论效果较为显著，该模型还可用于物流运输、公交站点等公共设施的优化选址、高峰模式的人流量预测与控制等。同时考虑将模型向智能化方向推广同时结合当前新兴科学，如：模式识别、计算机智能识别、最优控制等，从而实现人工智能化控制及优化更新。
八、参考文献
[1]罗俊明，《概率论与数理统计》（第一版），2006，28-36页
[2]李东.王伟.邵诚电梯群智能控制系统与智能控制方法[期刊论文]—控制与决策，2001，
4-7页。
[3]李中华，毛宗源，游林儒，《垂直交通客流分析与电梯群控制优化研究》华南理工大
学，2005，55-57页。
[4]宗群，牙淑红，王振世. 《基于排队论的上高峰电梯群控调度的研究》[A],统工程
与电子技术，2003，37-54页。
附录I
在问题一中，采用深圳某办公楼大厦的电梯日人流量图作为数据依据展开讨论，下图为深圳某大厦日电梯人流量图:
图4 深圳某大厦日电梯人流量
附录II
问题一中，采用深圳某办公楼大厦的电梯日人流量图中6:00-6:30的数据，为使结果精确，每隔六分钟取一组数据，所得的时间转换后早饭期间需求量如下表：
时间6:00 6:06 6:12 6:18 6:24 6:30
需求量69.964 76.7434 78.816 76.1353 68.6546 56.3274
群控电梯调度算法
一）、弄清群控电梯调度算法的评价指标 由于乘客心理等待时间的长短、电梯响应呼梯的快慢、召唤厅站客流量的大小、轿厢内乘客人数的多少等均是一些模糊的概念，很难用确切的数量关系定义，也难以用普通的逻辑规则综合描述。 近年来，人们借助于模糊数学中的隶属函数来表述，将复杂的模糊问题转化为简单清晰的形式进行求解和控制.模糊控制通过模糊逻辑进行推理，有效地对电梯运行状况作出判断，但对于非常复杂的多变量系统，要建立正确的模糊规则和隶属函数是非常困难的，而且通过大量实验建立的隶属函数和规则有时也很难保证十分精确与合理。此外，其隶属函数中的加权系数是确定的，不能根据客流改变而相应改变。 为了解决模糊控制中存在的某些问题，新发明将神经网络控制方法应用于电梯控制中，无需建立精确数学模型，可以提供准确的控制策略，以减少候梯时间，降低乘客的焦急等待心理，节约能源，合理有效地调度电梯最佳运行。 （二）、理解上行高峰模式、下行高峰模式、双路运行模式等概念，并找出根据一系列输入手段间接算出运行模式的算法： 上行高峰交通模式：当主要的客流是上行方向，即全部或者大多数乘客从建筑物的门厅进入电梯且上行，这种状况被定义为上行高峰交通状况。 下行高峰交通模式：当主要的客流是下行方向，即全部或者大多数乘客乘电梯下行到门厅离开电梯，这种状况被定义为下行高峰交通状况。 二路交通模式：当主要的客流是朝着某一层或从某一层而来，而该层不是门厅，这种状况被定义为二路交通状况。二路交通状况多是由于在大楼的某一层设有茶点部或会议室，在一天的某一时刻该层吸引了相当多的到达和离开呼梯信号。所以二路交通状况发生在上午和下午休息期间或会议期间。 四路交通模式：当主要的客流是朝着某两个特定的楼层而来，而其中的一个楼层可能是门厅，这种交通状况被定义为四路交通状况。当中午休息期间，会出现客流上行和下行两个方向的高峰状况。午饭时客流主要是下行，朝门厅和餐厅。午休快结束时，主要是从门厅和餐厅上行。所以四路交通多发生在午休期间。四路交通又可分为午饭前交通和午饭后交通模式。此两类交通模式和早晨与晚上发生的上行、下行高峰不同，虽然主要客流都为上行和下行模式，但此两类交通模式同时还有相当比例的层间交通和相反方向的交通。各交通量的比例还与午休时间的长短，餐厅的位置和大楼的使用情况有关。四路交通时不但要考虑主要交通客流，还要考虑其他客流，与单纯的上、下行高峰期不同。 平衡的层间交通模式：当上行和下行乘客数量大致相同，并且各层之间的交通需求基本平衡时，此时的交通模式是处于一种普通的双向层间交通状况，它存在于一天中的大部分时间，乘客通常要求最小的候梯时间和乘梯时间。 空闲交通模式：空闲交通模式通常发生在假日、深夜、黎明等情况下，此时大楼的客流稀少、乘客的到达间隔很长，在这种状况下群控系统中仅仅有部分电梯进行工作，而其余电梯轿厢则空闲等候。 基于神经网络的交通模式识别 基于统计规律的交通模式识别 （三）、不同的运行模式各自适用什么样的调度算法？ 1、基于专家系统的电梯群控调度算法[8] 电梯群控系统是一个具有大量不确定和不完整信息的复杂的非线性系统。这样一个复杂的系
第三版操作系统第3章习题
操作系统第三章总复习题 一、单选题 1、进程调度又称低级调度，其主要功能是（ D ）。 A．选择一个作业调入内存B．选择一个主存中的进程调出到外存 C．选择一个外存中的进程调入到主存D．将一个就绪的进程投入到运行 2、若进程P 一旦被唤醒就能够投入运行，系统可能为（ D ）。 A．分时系统，进程P 的优先级最高 B．抢占调度方式，就绪队列上的所有进程的优先级皆比P 的低 C．就绪队列为空队列 D．抢占调度方式，P 的优先级高于当期运行的进程。 3、一个进程P 被唤醒后,（ D ）。 A．P 就占有了CPU。B．P 的PCB 被移到就绪队列的队首。 C．P 的优先级肯定最高D．P 的状态变成就绪 4、若当前运行进程（）后，系统将会执行进程调度原语。 A 执行了一个转移指令 B 要求增加主存空间，经系统调用银行家算法进行测算认为是安全的。 C 执行了一条I/O 指令要求输入数据。 D 执行程序期间发生了I/O 完成中断。 5、当系统中（）时，系统将不会执行进程调度原语。 A．一个新进程被创建B．当前进程执行了P 操作。C．在非抢占调度中，进程A 正在运行而进程B 恰好被唤醒。D．分时系统中时间片用完。 6、在分时系统中，若当期运行的进程连续获得了两个时间片，原因可能是（）。 A 该进程的优先级最高 B 就绪队列为空 C 该进程最早进入就绪队列 D 该进程是一个短进程 7、实时系统中采用的调度算法可以有如下几种： 1、非抢占优先权调度算法 2、立即抢占优先权调度算法 3、时间片轮转调度算法 4、基于时钟中断抢占的优先权调度算法 按实时要求的严格程度由低到高的顺序（）。 A 1-3-2-4 B 3-1-4-2 C 3-1-2-4 D 1-3-4-2 8、三种主要类型的OS 中都必须配置的调度（）。 A 作业调度 B 中级调度 C 低级调度 D I/O 调度 9、设系统中n 个进程并发，共同竞争资源X，且每个进程都需要m 个X 资源，为使该系统不会发生死锁，资源X 最少要有（ C ）个。 A m*n+1 B n*m+n C n*m+1-n D 无法预计 10、死锁的预防方法中，不太可能的一种方法使（）。
数学建模电梯调度问题
电梯调度问题
电梯调度问题 摘要： 本题为一个电梯调度的优化问题，在一栋特定的写字楼内，利用现有的电梯资源，如何使用电梯能提高它的最大运输量，在人流密度十分大的情况下，如何更快的疏通人流成为一个备受关注的问题。为了评价一个电梯群系统的运作效率，及运载能力，在第一问中，我们用层次分析发，从效益、成本两大方面给出了六个分立的小指标，一同构成电梯群运载效率的指标体系。对第二问，本文根据题目情况的特殊性，定义忙期作为目标函数，对该电梯调度问题建立非线性规划模型，最后用遗传算法对模型求解。第三问中，本文将模型回归实际，分析假设对模型结果的影响，给出改进方案。 对于问题一，本文用评价方法中的层次分析法对电梯群系统的运作效率及运载能力进行分析。经分析，本文最终确定平均候梯时间、最长候车时间、平均行程时间、平均运营人数（服务强度）、平均服务时间及停站次数这六个指标作为电梯调度的指标体系。在这些评价指标的基础上，本文细化评价过程，给出完整的评价方案：首先，采用极差变换法对评价指标做无量纲化处理。然后，采用综合评价法对模型进行评价。在这个过程中，本文采用受人主观影响较小的夹角余弦法来确定权重系数。 对于第二问，本文建立非线性优化模型。借鉴排队论的思想，本文定义忙期，构造了针对本题中特定情形的简单数学表达式，作为目标函数。利用matlab软件，采用遗传算法对模型求解。多次运行可得到多个结果，然后用第一问中的评价模型进行评价，最终选出较优方案。最得到如下方案： 第一个电梯可停层数为：1,2,3,4,5,6,7,10,14,15,16,19,20,22 第二个电梯可停层数：1,4,5,7,10,13,16,18,19,20,21 第三个电梯可停层数：1,2,3,4,6,8,10,11,12,15,16,20,22 第四个电梯可停层数：1,2,3,4,7,10,11,17,18,19,21,22 第五个电梯可停层数：1,2,4,7,8,9,17,18,19,20,21 第六个电梯可停层数：1,4,5,6,7,8,9,11,13,18,19,20 此方案平均忙期为：15.3分钟。 对于第三问，本文是从每分钟到达人群数的分布角度改进模型的。第二问中
电梯调度算法
课程设计报告 电梯调度算法 学院医药信息工程学院 专业 年级 2008 学生姓名 学号 指导教师 2011-7-12 电梯调度算法设计报告
一．LOOK（查找）调度（电梯）电梯算法，操作系统学术名为SCAN算法。磁臂仅移动到请求的最外道就回转。反方向查找服务。 1.问题描述： 说明：电梯调度算法的基本原则就是如果在电梯运行方向上有人要使用电梯则继续往那个方向运动，如果电梯中的人还没有到达目的地则继续向原方向运动。具体而言，如果电梯现在朝上运动， *如果当前楼层的上方和下方都有请求，则先响应所有上方的请求，然后才向下响应下方的请求；如果电梯向下运动，则刚好相反。 *设计要求：模拟多人在不同楼层同时要求到各自目的地时电梯的响应顺序，要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。 * 设计提示：可以用一个结构体表示乘电梯的人，其中内容包括人的姓名、起始楼层、目的楼层；建立一个结构体的数组模拟当前所有需要乘电梯的人。把这个结构体数组作为程序的输入，*通过对数组中每个人的起始楼层和目的楼层进行分析，确定每个人进出电梯的顺序，并打印输出。 2.算法设计： 本程序用java语言、eclipse平台编写。 （1）算法思想：本算法只设计了一辆电梯，通过往返寻找方法，即先查询电梯运行方向的楼层是否存在有其他键被按下，有就继续往该方向运行，如果没有就查询电梯运行反方向的楼层是否有按键被按下，如果有电梯就改变方向，反方向运行。如果没有电梯就停止在该楼层，30秒后如果没有任何键被按下，电梯就自动返回1楼驻停。同时，电梯乘客所去的楼层方向与电梯当前方向一致的话，则电梯优先搭载该乘客。随后再搭载去反方向的乘客。实现电梯的升降操作。 二．1.总程序流程图如下
处理器调度习题
处理器调度 选择题 当CPU执行操作系统代码时，则处理机处于( )。 A．执行态 B．目态 C．管态 D．就绪态 ( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 A．系统调用 B．操作系统 C．内核 D．特权指令 操作系统提供给程序员的接口是( )。 A．进程 B．系统调用 C．库函数 D．B和C 用户程序向系统提出使用外设的请求方式是( )。 A．作业申请 B．原语 C．系统调用 D．I／O指令 当作业正常完成进入完成状态时，操作系统( )。 A．将输出该作业的结果并删除内存中的作业 B．将收回该作业的所占资源并输出结果 C．将收回该作业的所占资源及输出结果，并删除该作业 D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 B．作业是比进程低一级的概念。 C．一个作业至少由一个进程组成。 D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 作业从后备作业到被调度程序选中的时间称为( )。 周转时间B．响应时间C．等待调度时间D．运行时间 设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 A．T1+T2+T3 B．1／3(T1+T2+T3) C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 从作业提交给系统到作业完成的时间间隔称为作业的( )。 A．中断时间 B．等待时间 C．周转时间 D．响应时间 设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 A．1 h B．5 h C．2．5 h D．8 h FCFS调度算法有利于( )。 A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 下列哪种说法不是SJ(P)F调度算法的缺点( )。 A．对于长作业(进程)不利 B．未考虑作业(进程)的紧迫程度 C．不能有效降低作业(进程)的平均等待时间 D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 A．先来先服务调度算法B．短进程优先调度算法 C．优先权调度算法D．高响应比优先调度算法 在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。
操作系统之调度算法和死锁中的银行家算法习题答案
操作系统之调度算法和死锁中的银行家算法习 题答案 集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY-
1. 有三个批处理作业，第一个作业 10:00 到达，需要执行 2 小时；第二个作业在10:10到达，需要执行 1 小时；第三个作业在 10:25 到达，需要执行 25 分钟。分别采用先来先服 务，短作业优先和最高响应比优先三种调度算法，各自的平均周转时间是多少？解： 先来先服务： （结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间） 按到达先后，执行顺序：1->2->3 短作业优先： 1)初始只有作业1，所以先执行作业1，结束时间是12:00，此时有作业2和3； 2)作业3需要时间短，所以先执行； 3)最后执行作业2 最高响应比优先：
高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达，所以先执行作业1； 2)12:00时有作业2和3， 作业2：等待时间=12:00-10:10=110m;响应比=1+110/60=2.8； 作业3：等待时间=12:00-10:25=95m，响应比=1+95/25=4.8； 所以先执行作业3 3)执行作业2 2. 在一单道批处理系统中，一组作业的提交时刻和运行时间如下表所示。试计算一下三种 作业调度算法的平均周转时间 T 和平均带权周转时间 W。 （ 1）先来先服务；（ 2）短作业优先（ 3）高响应比优先 解： 先来先服务： 作业顺序：1,2,3,4 短作业优先： 作业顺序：
电梯调控问题的数学模型
作者：孟凡宝胡梦露陈立博 群控电梯调度方案优化的建模研究 摘要 随着城市中高层建筑的不断增多, 作为垂直运输工具的电梯得到了越来越广泛的应用。为满足楼内交通的需要，一座大楼往往安装多台电梯；尽管如此，上下班高峰时期的电梯仍然异常拥挤，且乘梯人员的侯梯时间往往较长；而大楼的物业管理方考虑到自己的成本问题，并不会增加电梯数量。因此，设计一个合理的最优电梯调配方案，对于改善乘梯人员的乘梯环境，降低物业方的管理成本均具有极其重要的意义。 本文针对某商业中心写字楼早晚上下班高峰期的电梯调度问题建立数学模型，以获得合理的优化方案。 主要分为三个问题解决： 第一个问题：确定合理的模型评价指标； 第二个问题：在不考虑写字楼地下部分等前提下，建立早晚高峰期的电梯调度的优化模型，并利用所提出的评价指标对各种方案进行比较，找出最优方案； 第三个问题：将第二个问题中建立的简化模型进一步实际化，以得到尽量符合实际的电梯调度方案。 对于第一个问题，本文分别从乘梯人群和写字楼物业管理两方面的利益出发，选择每台电梯的平均载客量和电梯的总运行时间作为评价指标，并运用层次分析法确定二者权重，建立了综合的评价函数；很多研究高峰时期电梯调度问题的论文使用乘梯人员的等待时间和乘梯时间作为衡量电梯效率的标准，这样虽然通俗易懂，但他们在计算等待时间时为了简化计算，往往假设乘梯人群同时到达，这与实际不符，且误差较大；本文在假设高峰期内乘梯人群以一定的到达率到达乘梯起点前提下，采用电梯的平均载客量作为衡量标准。 对于第二个问题，本文采用分区调度的方法，将可能的方案按楼层分区的多少（分区数：1~6）分为六类，综合运用各种规划方法计算出每个分区方案中最优的调度方案，再利用综合评价函数对这六个最优的调度方案进行评价，从而得出最终的最优调度方案；在计算各类分区方案中最优的调度方案时，本文糅合了理想点法、线性加权法和最大最小法，并采用层次分析法计算出的权重将多目标规划问题转化为单目标规划；在逐步分区讨论的过程中，本文采用动态规划的方法，在计算出第k类的最优方案的基础上再计算第k+1类的最优方案；结果发现，在该简化模型的前提下，最优的调度方案是分为六区（具体分区见正文）对于第三个问题，本文去掉了简化模型中“不考虑地下两层”这一假设，并考虑到“应优先满足高层的乘梯人员的乘梯需求”这一实际情况，将简化模型解决的单起点多终点（或多起点单终点）问题扩展为多起点多终点问题，并且在评价指标中加入了“优先满足高层的乘梯人员的乘梯需求”这一标准；为解出这一复杂模型的最优解，本文在简化模型的最优解的基础上，进一步确定各电梯在地下一、二层和地上一层的停靠情况，从而得出更加符合实际情况的最优解；结果发现，最优方案为仍分为六个区，每个电梯在一楼和地下一、二层均停。 最后，本文对该模型进行了评价，并提出了改进方案。 关键词：群控电梯；分区调度；多目标规划；层次分析法；优化模型；遍历搜索；最大最小原则；动态规划；0-1规划
计算机操作系统课后习题答案第三章(第四版)
第三章处理机调度与死锁 1，高级调度与低级调度的主要任务是什么？为什么要引入中级调度？ 【解】（1）高级调度主要任务是用于决定把外存上处于后备队列中的那些作业调入内存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。（2）低级调度主要任务是决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。（3）引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件，且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上，等待进程调度。 3、何谓作业、作业步和作业流？ 【解】作业包含通常的程序和数据，还配有作业说明书。系统根据该说明书对程序的运行进行控制。批处理系统中是以作业为基本单位从外存调入内存。作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。 作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流；在操作系统的控制下，逐个作业进程处理，于是形成了处理作业流。 4、在什么情冴下需要使用作业控制块JCB？其中包含了哪些内容？ 【解】每当作业进入系统时，系统便为每个作业建立一个作业控制块JCB，根据作业类型将它插入到相应的后备队列中。 JCB 包含的内容通常有：1) 作业标识2)用户名称3)用户账户4)作业类型（CPU 繁忙型、I/O芳名型、批量型、终端型）5)作业状态6)调度信息（优先级、作业已运行）7)资源要求8)进入系统时间9) 开始处理时间10) 作业完成时间11) 作业退出时间12) 资源使用情况等 5．在作业调度中应如何确定接纳多少个作业和接纳哪些作业？ 【解】作业调度每次接纳进入内存的作业数，取决于多道程序度。应将哪些作业从外存调入内存，取决于采用的调度算法。最简单的是先来服务调度算法，较常用的是短作业优先调度算法和基于作业优先级的调度算法。 7．试说明低级调度的主要功能。 【解】（1）保存处理机的现场信息（2）按某种算法选取进程（3）把处理机分配给进程。 8、在抢占调度方式中，抢占的原则是什么？ 【解】剥夺原则有：（1）时间片原则各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数实时系统，以及要求较高的批处理系统。（2）优先权原则通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行。（3）短作业（进程）优先原则当新到达的作业（进程）比正在执行的作业（进程）明显地短时，将剥夺长作业（进程）的执行，将处理机分配给短作业（进程），使之优先执行。 9、选择调度方式和调度算法时，应遵循的准则是什么？ 【解】应遵循的准则有（1）面向用户的准则：周转时间短，响应时间快，截止时间的保证，优先权准则。（2）面向系统的准则：系统吞吐量高，处理机利用率好，各类资源的平衡利用。 10、在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？ 【解】 批处理系统：FCFS算法、最小优先数优先算法、抢占式最小优先数优先算法 2 分时系统：可剥夺调度、轮转调度 实时系统：时间片轮转调度算法、非抢占优先权调度算法、基于时钟中断抢占的优先权调度算法、立即抢占的优先权调度。 11、何谓静态和动态优先权？确定静态优先权的依据是什么？ 【解】静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。确定静态优先权的依据是：（1）进程类型，通常系统进程的优先权高于一般用户进程的优先权。（2）进程对资源的需要。（3）用户要求，用户进程的紧迫程度及用户所付费用的多少来确定优先权的。 12、试比较FCFS和SPF两种进程调度算法。 【解】FCFS算法按照作业提交或进程变为就绪状态的先后次序，分派CPU。当前作业或进程占有CPU，直到执行完或阻塞，才让出CPU。在作业或进程唤醒后，并不立即恢复执行，通常等到当前作业或进程让出CPU。FCFS比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。SPF有利于短进程调度，是从就绪队列中选出一估计运行时间最短的进
磁盘移臂调度过程模拟设计-电梯算法最短寻道时间优先
学号： 课程设计 题目 磁盘移臂调度过程模拟设计 --电梯算法、最短寻道时间优先算法 学院计算机科学与技术学院专业 班级 姓名 指导教师吴利军
2013 年 1 月15 日 课程设计任务书 学生姓名： 指导教师：吴利军工作单位：计算机科学与技术学院 题目: 磁盘移臂调度过程模拟设计——电梯算法、最短寻道时间优先算法初始条件： 1．预备内容：阅读操作系统的文件管理章节内容，理解有关文件组织形式、存储设备的概念。 2．实践准备：掌握一种计算机高级语言的使用。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．编程序模拟磁盘调度的过程，采用指定算法，模拟并输出存取臂的移动顺序，并计算存取臂移动的磁道总数。能够处理以下的情形： ⑴可根据需要输入当前磁头的位置，磁头移动方向； ⑵能够输入柱面数，磁道访问序列等参数，并能够显示调度结果（磁盘访问请求的磁道号 以及磁头移动的总磁道数）。 2．设计报告内容应说明： ⑴课程设计目的与功能； ⑵需求分析，数据结构或模块说明(功能与框图)；
⑶源程序的主要部分； ⑷测试用例，运行结果与运行情况分析； ⑸自我评价与总结： i）你认为你完成的设计哪些地方做得比较好或比较出色； ii）什么地方做得不太好，以后如何改正； iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）； iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）； v）对实验题的评价和改进意见，请你推荐设计题目。 时间安排： 设计安排一周：周1、周2：完成程序分析及设计。 周2、周3：完成程序调试及测试。 周4、周5：验收，撰写课程设计报告。 （注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记） 指导教师签名：年月日 系主任（或责任教师）签名：年月日 磁盘移臂调度过程模拟设计 ——电梯算法、最短寻道时间优先算法1 课程设计目的与功能
电梯调度论文完整版
群控电梯调度方案优化的建模研究 摘要 随着城市中高层建筑的不断增多, 作为垂直运输工具的电梯得到了越来越广泛的应用。为满足楼内交通的需要，一座大楼往往安装多台电梯；尽管如此，上下班高峰时期的电梯仍然异常拥挤，且乘梯人员的侯梯时间往往较长；而大楼的物业管理方考虑到自己的成本问题，并不会增加电梯数量。因此，设计一个合理的最优电梯调配方案，对于改善乘梯人员的乘梯环境，降低物业方的管理成本均具有极其重要的意义。 本文针对某商业中心写字楼早晚上下班高峰期的电梯调度问题建立数学模型，以获得合理的优化方案。 主要分为三个问题解决： 第一个问题：确定合理的模型评价指标； 第二个问题：在不考虑写字楼地下部分等前提下，建立早晚高峰期的电梯调度的优化模型，并利用所提出的评价指标对各种方案进行比较，找出最优方案； 第三个问题：将第二个问题中建立的简化模型进一步实际化，以得到尽量符合实际的电梯调度方案。 对于第一个问题，本文分别从乘梯人群和写字楼物业管理两方面的利益出发，选择每台电梯的平均载客量和电梯的总运行时间作为评价指标，并运用层次分析法确定二者权重，建立了综合的评价函数；很多研究高峰时期电梯调度问题的论文使用乘梯人员的等待时间和乘梯时间作为衡量电梯效率的标准，这样虽然通俗易懂，但他们在计算等待时间时为了简化计算，往往假设乘梯人群同时到达，这与实际不符，且误差较大；本文在假设高峰期内乘梯人群以一定的到达率到达乘梯起点前提下，采用电梯的平均载客量作为衡量标准。 对于第二个问题，本文采用分区调度的方法，将可能的方案按楼层分区的多少（分区数：1~6）分为六类，综合运用各种规划方法计算出每个分区方案中最优的调度方案，再利用综合评价函数对这六个最优的调度方案进行评价，从而得出最终的最优调度方案；在计算各类分区方案中最优的调度方案时，本文糅合了理想点法、线性加权法和最大最小法，并采用层次分析法计算出的权重将多目标规划问题转化为单目标规划；在逐步分区讨论的过程中，本文采用动态规划的方法，在计算出第k类的最优方案的基础上再计算第k+1类的最优方案；结果发现，在该简化模型的前提下，最优的调度方案是分为六区（具体分区见正文）对于第三个问题，本文去掉了简化模型中“不考虑地下两层”这一假设，并考虑到“应优先满足高层的乘梯人员的乘梯需求”这一实际情况，将简化模型解决的单起点多终点（或多起点单终点）问题扩展为多起点多终点问题，并且在评价指标中加入了“优先满足高层的乘梯人员的乘梯需求”这一标准；为解出这一复杂模型的最优解，本文在简化模型的最优解的基础上，进一步确定各电梯在地下一、二层和地上一层的停靠情况，从而得出更加符合实际情况的最优解；结果发现，最优方案为仍分为六个区，每个电梯在一楼和地下一、二层均停。 最后，本文对该模型进行了评价，并提出了改进方案。 关键词：群控电梯；分区调度；多目标规划；层次分析法；优化模型；遍历搜索；最大最小原则；动态规划；0-1规划
模拟电梯调度算法,实现对磁盘的驱动调度。
操作系统实验 （第三次） 一、实验内容 模拟电梯调度算法，实现对磁盘的驱动调度。 二、实验目的
磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅 助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。 三、实验题目 模拟电梯调度算法，对磁盘进行移臂和旋转调度。 [提示]： （1）磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。 当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。 由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理 器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。 “驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信 号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断四、处理和处理器调度选择的过程。因而，程序的结构可参考图3—1
高峰模式下高层办公楼电梯调度改善方案(A较严谨)
高峰模式下高层办公楼电梯调度改善方案 田震李文鹏李媖 摘要 电梯调度方案是指在特定的交通状况下，电梯系统应遵循的一组确定控制策略的规则。对于配有多台电梯的现代高层办公楼，如何建立合适的电梯运行方式至关重要。本文的目的就是建立合理的调度方案，主要运用概率，运筹学等理论对问题建立相关的数学模型，用matlab 等软件对问题进行求解，最终得出最合理的安排及优化方案，已解决高层办公楼电梯拥挤的情况。 本题的评价指标有三个，一是排队等待时间，二是电梯运行时乘客在电梯内等待的时间，三是6部电梯将全部员工运送到指定楼层所用的时间，三个评价指标中，排队等待时间与电梯运行时乘客在电梯内等待的时间可以综合为乘客的满意度。 对于问题一，首先考虑最简单的情形建立模型一，采用极端假设的方法，不考虑乘客到来的随机性，不考虑乘客的等待时间，在规定的时间内，电梯每次都是满载的，且运送的都是同一层的员工。这样得到一个简化模型，此模型运送完员工所花费的时间是最短的，同时求解出在确定的电梯数量确定的办公人数分布前提下电梯调度的最大运载能力。将所有的人都运到的最短的时间为：1955.5秒。 接着对于理想模型实际化建立模型二，以“最后被运送的乘客的等待时间最短”为评价标准，以“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”云则为依据，对几种常见电梯运行方案建立数学模型，比较其运行效率，得出分段运行方案是符合要求的最优方案。 在极端假设条件下的模型的基础上进行改进建立模型三，对所有的楼层进行分段，每个电梯负责特定的楼层，以概率的方法，得出非线性规划方程组，求得最优的分段数，并求出一些表征参数如：总运行时间及运载能力。 确定方案的基本分段数后，对于分段运行方案的具体分段方式进行优化计算，建立模型四。由模型三的结果将楼层分为六段为最优，通过模型四可找出了各个区的具体分区点，以电梯运行一次的往返时间为目标函数，建立模型，通过matlab软件对于分段模型分段方法进行模拟运行，以枚举法求解，最终得出多组最优分区，但是各组分区方式的差别并不是很大。 问题二要求将数学模型进一步实际化首先应考虑电梯上行下行时的加速度最大速度、乘客上下电梯所用时间和开关电梯门的平均时间。运用物理基础在模型四的基础上，对模型进行了进一步优化。 关键字：电梯分段运行方案；计算机模拟电梯运行；非线性规划；matlab软件 一、问题重述 1.问题背景： 随着社会经济的发展，电梯在人们的日常生活工作中的作用越来越大，特别在人口高度集中的城市，电梯成为人们生活中不可或缺的一种交通工具。然而，与此同时，在办公场所每天早晚高峰时期，拥挤的人潮中总能听到对电梯运行速度和调度安排的抱怨，也就是说人们对电梯的服务质量要求越来越高。对于配套有多台电梯的商务楼，如何安排好各
操作系统课程设计--模拟实现磁盘的调度
课 程 设 计设计题目：模拟实现磁盘的调度
一、课题设计目的 a、观察、体会操作系统的磁盘调度方法，并通过一个简单的磁盘调度模拟程序的实现，加深对磁盘调度的理解。 b、提高实际动手编程能力，为日后从事软件开发工作打下坚实基础。 c、通过对磁盘调度算法的设计，深入理解提高磁盘访问速度的原理。 二、课题实现环境 VC++6.0 MFC 三、课题设计思路 算法描述： 1.服务算法（FCFS） 先来先服务（FCFS）调度:按先来后到次序服务，未作优化。 最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。 2.算法（SCAN） SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。 “电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。 我们仍用前述的同一例子来讨论采用“电梯调度”算法的情况。由于磁盘移动臂的初始方向有两个，而该算法是与移动臂方向有关，所以分成两种情况来讨论。 〈1〉.移动臂由里向外移动 开始时，，在50号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向32号柱面的位置，因此，当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是32号柱面。所以应先为32号柱面的访问者服务，然后是为15号柱面的访问者服务。之后，由于在向外移方向已无访问等待者，故改变移动臂的方向，由外向里依次为各访问者服务。在这种情况下为等待访问者服务的次序是61、99、130、148、159、199。
操作系统原理第四章 处理机调度习题
第四章处理机调度 4.3 习题 4.3.1 选择最合适的答案 1．某系统采用了银行家算法，则下列叙述正确的是（）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4．在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5．在下列选项中，属于检测死锁的方法是（）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则
电梯调度算法
江西师范大学计算机信息工程学院学生实验报告 专业_ 计算机科学与技术姓名___马化梁学号____1308092042 日期__2015.6.5_ 课程名称操作系统实验室名称X4313 实验名称设备管理-电梯调度算法 指导教师朱明华成绩 1、实验目的 本实验要求学生设计一个电梯调度算法来模拟实现磁盘移臂调度过程。 2、实验原理和内容 任何一个对磁盘的访问请求，应给出访问磁盘的存储空间地址：柱面号、磁头号和扇区号。在启动磁盘执行I/O操作时，应先把移动臂移动到指定的柱面，再等待指定的扇区旋转到磁头位置下，最后让指定的磁头进行读/写，完成信息传送。移臂调度是根据访问者指定的柱面位置来决定执行次序的调度。 3、实验步骤 （1）弄清实验要求及目的； （2）想清思路； （3）设计代码； （4）实现代码。
4、程序及运行结果（或实验数据记录及分析） #include 保证调度算法 基本思想:向用户做出明确的性能保证,然后去实现它.如你工作时有n个用户的登录,则你将获得cpu处理能力的1/n 算法实现:跟踪计算各个进程已经使用的cpu时间和应该获得的cpu时间,调度将转向两者之比最低的进程 五,保证调度算法 思想:向用户做出明确的性能保证,然后去实现它. 算法:容易实现的一种保证是:当工作时己有n个用户登录在系统,则将获得CPU处理能力的1/n.类似的,如果在一个有n个进程运行的用户系统中,每个进程将获得CPU处理能力的1/n. 实现方法:OS应记录及计算,各个进程在一定时间段内,已经使用的CPU时间和应该得到的CPU时间,二者之比小者优先级高. 5. 保证调度 一种完全不同的调度算法是向用户作出明确的性能保证，然后去实现它。一种很实际并很容易实现的保证是：若用户工作时有n个用户登录，则用户将获得CPU处理能力的1/n。类似地，在一个有n个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得1/n的CPU时间。看上去足够公平了。 为了实现所做的保证，系统必须跟踪各个进程自创建以来已使用了多少CPU时间。然后它计算各个进程应获得的CPU时间，即自创建以来的时间除以n。由于各个进程实际获得的CPU时间是已知的，所以很容易计算出真正获得的CPU时间和应获得的CPU时间之比。比率为0.5说明一个进程只获得了应得时间的一半，而比率为2.0则说明它获得了应得时间的2倍。于是该算法随后转向比率最低的进程，直到该进程的比率超过它的最接近竞争者为止。 彩票调度算法 基本思想:为进程发放针对系统各种资源(如cpu时间)的彩票;当调度程序需要做出决策时,随机选择一张彩票,持有该彩票的进程将获得系统资源 合作进程之间的彩票交换 六,彩票调度算法 彩票调度算法: 为进程发放针对各种资源(如CPU时间)的彩票.调度程序随机选择一张彩票,持有该彩票的进程获得系统资源. 彩票调度算法的特点: 平等且体现优先级:进程都是平等的,有相同的运行机会.如果某些进程需要更多的机会,可被给予更多彩票,增加其中奖机会. 易计算CPU的占有几率:某进程占用CPU的几率,与所持有的彩票数成正比例.该算法可实现各进程占用CPU的几率. 响应迅速 各个进程可以合作,相互交换彩票. 容易实现按比例分配如图象传输率,10帧/s,15帧/s,25帧/s UML程序设计实例 —电梯调度模拟器— 本章通过电梯调度模拟器的例子详细介绍了如何利用UML进行一个实际系统的开发。这个系统的实现过程，遵循Rational统一软件开发过程，最后用Vc++编码实现。 问题描述 在开发任何一个系统之前，开发人员对所要开发的系统的初步理解首先是从用户的问题描述开始的。问题描述的内容包括系统的基本功能需求，用户对系统的性能，外观等特性的要求。这种描述根据开发项目的规模不同，呈现不同的形式。对于大的项目，问题描述可能是长达几页（几十页）的需求规格说明；对于小的项目，可能只是口头上的几句陈述。通过问题描述，开发人员对要开发的系统产生一个大概的印象。 此实例的问题描述如下： 有一座8层楼房，每层提供一组按钮（“上”或“下”），用于请求电梯的到达；每部电梯内部提供一个控制面板，提供用户对目标楼层的选择，并显示电梯当前所处楼层、运行方向。两部电梯由一个调度器统一调度。如果没有请求，并超过一定时限，电梯回到一楼。希望开发人员能实现一个电梯调度模拟器来模拟如上所述的一切，对电梯的调度准则没有做特别要求。 此外，用户还可能会对系统的性能，外观等特性提出要求，这些都需要在开发过程中加以考虑。 需求分析 拟订侯选需求 在系统开发启动之前，首先要对项目做一些可行性分析。在Rational统一软件开发过程中，称这个阶段为初始阶段。 在初始阶段主要是跟各方进行交流，广泛收集信息，听取客户和专家的建议。并对这些信息和建议进行记录，整理得到一个后选需求列表。 后选需求列表中应包括如下各项 1．名称 2．简要说明 3．状态（建议的、批准的、并入的或证实的） 4．实现成本估算（人小时，人月） 5．优先级（关键的、重要的或辅助的) 6．实现风险的级别(关键的、重要的或一般的) 表1 后选需求列表 电梯调度问题 商业中心某写字楼有二十二层地上建筑楼层和两层地下停车场，6部电梯，每部电梯最大载重是20个正常成人的体重总和。工作日里每天早晚高峰时期均是非常拥挤，而且等待电梯的时间明显增加。请你针对早晚高峰期的电梯调度问题建立数学模型，以期获得合理的优化方案。 1）请给出若干合理的模型评价指标。 2）暂不考虑该写字楼的地下部分，每层楼层的平均办公人数经过调查已知（见表1）。假设每层楼之间电梯的平均运行时间是3秒，最底层(地上一层)平均停留时间是20秒，其他各层若停留，则平均停留时间为10秒，电梯在各层的相应的停留时间内乘梯人员能够完成出入电梯。 表1：该写字楼各层办公人数 楼层人数楼层人数楼层人数 1无9236 617200 2 3 4 5 6 7 8208 52 177 222 5 130 181 191 236 7 10 11 12 13 14 15 16 139 272 272 272 270 300 264 18 19 20 2l 22 200 200 200 207 207 请你针对这样的简化情况，建立你的数学模型（列明你的假设），给出一个尽量最优的电梯调度方案，并利用所提评价指标进行比较。 3）将你在第2问中所建立的数学模型进一步实际化，以期能够尽量适用于实际情况，用于解决现实的电梯调度问题。 问题备注： 本题的评分标准按照以下先后顺序：逻辑的严谨程度-行文与模型描述的条理程度-模型和现实问题的接近程度-以及所用数学工具的理论程度。 摘要 随着科技的发展，人们逐步加快了自己的步伐，高节奏的生活，对于时间的要求，越来越高，写字楼里的人来也匆匆去也匆匆，在高峰期时段对电梯的使用最多，电梯的合理化应用在此显得尤为重要，没有合理的优化方案，不仅影响了乘客的上班时间，同时，电梯的多次停顿也造成了一定程度的能源浪费，所以在此提出得到优化方案，并作出计算分析其优化程度。 本文首先根据电梯群控模型评价指标体系，从乘客者的候梯时间和乘梯时间和能耗三个角度考虑。最初选定方案一 电梯编号负责楼层 1—2 2-10 3—4 11-17 5—6 18-22 方案二 电梯编号负责楼层 1 2 3 4 5 6 2 7 8 9 10 3 11 12 13 4 14 1 5 16 5 17 18 19 6 20 21 22 我们将建立一个多目标规划模型，对该模型的建立，分三个目标：乘客的平均候梯时间要短，乘客的平均乘梯时间要短，能源耗损要少。利用这三个指标来综合评价电梯群控方案的优劣。并采用模糊评价和多目标优化群控和借助实现蒙特卡罗模拟的思想，建立了全面合理的电梯调度方案的评价体系。并将模拟出的数据代入评价函数，从而帮助确定电梯调度的最佳策略。 根据建模得到的结果，最终得到的最佳方案为方案二。最后本文还根据使用的算法，结合实际情况，对模型的优缺点进行了详细的分析与评价，并提出了改进和模型推广方向。最后本文就所建立的模型在实际运用中的作用进行了分析，并提出了改进方向。结合实际，加入重要因素的考虑，比如考虑其他交通流，考虑个别人群满意度。几种操作系统调度算法
应用实例电梯调度模拟器
数学建模 电梯调度问题16