关于公交车调度问题的研究

公交车的调度问题是现代城市交通中的一个突出问题，本文通过对一条线路上各时段、各站点的上下乘客数的调查统计．根据一些合理假设．并在优先考虑公交公司利益同时兼顾乘客利益的基础上建立了一个公交车调度的数学模型。再针对一条实际的公交线路．利用计算机语言编程的方法对模型进行了验证。     

流水作业问题的一个启发式算法

讨论具有延迟时间的流水作业问题,并提出了解决该问题的一种启发算法,证明了其最坏性能比是（m 1）/2,并且上界是紧的,特别当m=2,即两台机器上具有延迟时间的流水作业问题时,其最坏性能比是3/2,最后将所得结论推广到FmID2问题,即加工时间相等且延迟时间只取两上值的流水作业问题,其最坏性能比也是m 1/2。     

机器具有不可用时间间隔的两机无等待流水车间调度问题的求解性质

研究工件具有无等待约束,并且只有一台机器具有不可用时间间隔的两机流水车间调度问题.文中给出使用GGA算法得到问题最优解的条件,并证明问题的复杂性,分析将GGA算法作为问题启发式算法的最坏性能比范围.     

考虑贷款的资金调度问题

本文讨论一般的资金调度问题，给出它们的数学模型。     

基于预测表的容错实时调度算法

为了更精确地预测软件容错模型中的容错实时调度算法主部分可否执行，提出了基于预测袁的容错调度算法（PTBA）．该算法充分考虑了当前时间至替代部分通知时间之间的任务执行状况，以该时间段内通知时间的先后顺序精确地预测主部分的执行情况，并为待执行主部分构建预测表．当主部分不发生错误时，算法将依照预测表进行任务调度．模拟结果表明，利用PTBA可获得更多的主部分执行时间，降低了CPU消耗．PTBA适用于软件错误率较低的应用环境，特别是当任务的周期较短时，能够以较小的调度开销获得较高的调度性能．     

关于公交车调度的数学模型

根据典型的一个工作日两个运行方向各站上下车的乘客数量统计,首先探讨了如何利用平滑法来确定一个有价值并且效率高的车辆运行时刻表,使其满足乘客的舒适性和公交公司低成本的服务;接着,又利用最优化的基本思想,对此问题进行了进一步的讨论,得到了最小配车辆的数量,然后针对满意度的评价水平问题,建立了几个良好刻画公司以及乘客满意度的满意度函数并求出了乘客与公交公司双方的满意度.最后,我们对新提出的模型进行了模型评价和模型改进方向的讨论,并对如何采集公交车客运量的数据,提出了几个中肯的建议,完成了对关于公交车调度问题的较为详细而合理的讨论.     

两台机在线均衡调度算法的改进

研究两台平行同型机的在线均衡调度问题，利用两个不同的部分信息分别设计出两个算法，这两个算法比可能有的最好的在线算法在性能上都要好。同时还证明，就这两个部分信息来说，给出的算法是可能有的最好的算法。     

钢卷仓库中的吊机调度问题

研究了钢铁企业冷轧原料库中的吊机调度问题.将吊机的运输和倒垛操作集成考虑,目标函数为将全部需求板卷运输到指定位置的时间最小化.对于该问题,首先提出了一个混合整规划模型,进一步证明了该问题是强NP难的.基于对问题性质的分析,针对无倒垛操作的特殊情况,提出了多项式时间可解的最优算法.对于问题的一般情况,提出了一个启发式算法并分析了它的最坏情况.     

具有优先权的自由作业时间表问题研究

研究了具有优先权的自由作业时间表问题，在工件具有准备时间的条件下，给出一种新的启发式算法，其最坏性能比不超过2，猜想该算法的紧界是2—2／(m 1)，其中m是机器的台数，证明在3台机器的情况下，该算法的最坏性能比为3／2，且上界是紧的。     

一类生产调度问题的解算

本文把生产实践中的一类调度问题用计算机算法理论加以讨论以期 得到问题的最优解。     

公交车调度问题的优化设计

评价公交调度方案的优劣,对各时段调度进行优化,用数值分析方法建立公交车调度的数学模型,模拟仿真调度过程,得出了不同满意度下车辆调度的最佳方案。     

运输与倒垛集成的多吊机调度问题

考虑了钢铁企业仓库管理中经常出现的多吊机调度问题．根据实际存储的需求,每个板卷已经被放在了预先指定的按两层摆放的位置上．当给定一些需求板卷时,如果一个需求板卷在上层或无板卷阻碍的下层,它可以被直接运输到指定位置（运输操作）;否则,阻碍板卷需要首先被运到另外的位置（倒垛操作）．所研究的问题为由吊机协调调度运输和倒垛操作．在以前研究的文献中,这两种操作都是分开研究的．目标为最小化最后一个运输到指定位置的板卷完成时间,这与最后结束操作的吊机的最早可能完工时间一致．为了更清楚地描述问题,提出了一个混合整线性规划模型（MILP）．由于证明了所研究问题的特殊情况是强NP难的,这意味着所研究的问题也是强NP难的,因此提出了问题的启发式算法,给出了下界并进一步分析了算法的最坏性能．     

带约束的平行机排序问题

讨论了带资源约束和机器准备时间的平行机排序问题，资源约束是指每个机器最多加工κ个工件．首先对一般情况下的同型机的PLPT排序进行了讨论；并首次对同类机排序进行了研究，给出了一个FLPT近似算法，同时对m=2时证明了PLPT排序的最坏情况紧界是2．     

关于柔性制造系统调度问题的研究

在综述各种调度方法的基础上,采用优先规则的方法给出一种柔性制造系统调度方案.该方案利用产品加工工艺树为柔性制造系统问题的调度模型,基于贪心规则、长路径、设备均衡策略规则进行调度,对解决柔性制造系统调度问题具有一定的理论和实用价值.     

具有准备时间的流水作业时间表问题启发式算法与最坏性能比分析

本文研究具有准备时间的流水作业时间表问题，给了一个简单的启发式算法，证明了一个简单的启发式算法的最坏性能比是m 1/2(其中m是机器的台数)，且关于上界是紧的，特别当m=2时，该启发式算法的最坏性能比是3／2，此结果要好于Potts在1985年所给出的算法。     

公交车调度的优化模型

以公交车线路运营系统为背景,提出了各站上、下车人数分布的数学模型,并以此模型为基础,为公交车线路运营的调度问题,提供了一种较好的解决方法。本文以公交公司运营的总车辆数最小为目标,以运营过程中满足各方需求的车辆数为约束条件建立了优化模型,模型实现了对线路运营进行评估和优化公交车配置.既考虑了乘客等车的社会成本又兼顾了公交公司的利益,方法易于操作,具有较大的实际应用价值。     

具有延迟时间的自由作业排序问题——最坏性能比分析

研究一类具有延迟时间的自由作业问题，证明在机器台数任意的情况下，一个简单的贪婪算法的最坏性能比不超过2。特别当m＝2时，证明了该算法的最坏性能比为3／2，其中m为机器的台数。     

带核元的带拒绝装箱问题

讨论了如下定义的带核元带拒绝装箱问题:设有许多等长的箱子,给定一个带核元的物品集,每个非核元有2个参数:大小和罚值.非核元物品可以放入箱子也可被拒绝放入箱子.如果某物品被拒绝放入箱中,则产生惩罚值,同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1,问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景.提出了一个求解该问题的局外近似算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.     

一类解决作业车间调度问题的遗传退火算法

将遗传算法与模拟退火相结合,提出了一种新调度算法,算法分成两步,首先利用遗传算法快速搜索一组较好解,然后利用模拟退火进行群体寻优,这样,既能克服遗传算法过早收敛的弱点,又能加快模拟退火的收敛速度,实验表明,该算法具有较高的求解质量和效率。