1)需求描述
机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器分配，使得：
(1) 一台机器在同一时间内只能处理一个作业；
(2) 一个作业不能同时在两台机器上处理；
(3) 作业i一旦运行，则需要ti个连续时间单位。
设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间最短。
2) 基本要求
(1) 建立问题模型，设计数据结构；
(2) 设计调度算法，为每个作业分配一台可用机器；
(3) 给出分配方案。
2022-02-10 15:38:25
374KB
1
摘 要
公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。
本题要求我们得出一个最优的公交车调度方案，通过分析题中所给数据与要求，得出此题为多目标线性规划问题。由于涉及到多目标，为了便于求解要将多目标转化为单目标规划模型，由于题中所给目标具有抽象性，因此需要先根据所给资料对目标进行定量化分析，即选择合适的参数表示目标函数，本文采用等车时间与乘车时拥挤程度表示乘客的利益，平均载客率表示公交公司的利益，显然这两者的关系是互斥的，即公交车数量越少，虽公交公司利益最大化，但等车时间越长，拥挤程度更大，造成乘客抱怨度更高。由此，本文建立了两个模型，关于模型Ⅰ，将公交公司的利益作为目标函数，为了照顾乘客的满意度，考虑在早高峰时间将等车时间尽量缩短至少于5分钟，其他时间段都控制在5到10分钟之内，建立单目标的最小车次线性规划模型并运用LINGO软件求得公交车的调度车次。最终得到最优方案中需要62辆公交车，具体调度方案见附录中表5-1。关于模型Ⅱ，我们主要利用模糊数学及层次分析法设置加权因子将其转化为单目标优化问题，并判断在模型Ⅰ的情况下该放宽还是加紧约束条件才可得到最优解，在其他时段则优先考虑公交车公司的满意度，并用MATLAB拟合公交公司与乘客的满意度。最终得到最优方案中需要64辆公交车，具体调度方案见附录中表5-2。
最后，我们对两个模型进行了误差分析与稳定性分析，通过误差分析得到本文模型仍存在误差，误差与提供的数据本身以及模型的假设均有关。因此为了减少误差，使结果更加准确，我们需要更加准确的各时间段客流量数据，且时间间隔越短可以使结果更加精确，更有实用价值。通过稳定性分析发现在对最大满载率及乘客在一般时间内的等待时间做微小变动时，模型Ⅰ、Ⅱ 结果都没有太大变化，由此可知两个模型的稳定性都比较好。
本文中的模型通俗易懂，易于用软件得到确切结果，具有实际意义，但考虑因素还不够全面，应当结合实际多方面的情况，设计出更加优化的调度方案，模型较稳定，具有推广意义。
2022-01-12 20:10:10
380KB
1