时间表理论中LPT算法在装箱问题中的应用

本文利用二分搜索法和时间表理论中LPT算法求解装箱问题的近似最优解;给出了一个直观性算法,并研究这个算法的最坏情形,最后说明此算法在某些方面优于著名的FFD算法。     

大学考试时间表问题的混合遗传算法求解

考试时间表问题是一类典型的组合优化问题,也是NP难问题.分析了大学考试时间表编排的特点,给出了一种解决考试时间冲突的自动生成考试时间表的可行时段-查找算法.为进一步解决时间间隔问题,将可行时段-查找算法嵌入到遗传算法中形成混合遗传算法.实验结果表明,本文提出的混合遗传算法能快速、有效的解决大学考试时间表问题.     

大学考试时间表问题的混合遗传算法求解

考试时间表问题是一类典型的组合优化问题,也是NP难问题。分析了大学考试时间表编排的特点,给出了一种解决考试时间冲突的自动生成考试时间表的可行时段-查找算法。为进一步解决时间间隔问题,将可行时段-查找算法嵌入到遗传算法中形成混合遗传算法。实验结果表明,本文提出的混合遗传算法能快速、有效的解决大学考试时间表问题。     

考虑维护和可中断工件的混合型平行机调度问题研究

考虑部分机器需要周期维护,其余机器无需维护的混合型平行机调度问题。一组给定的可中断且加工时长均相等的工件需要加工,工件数不超过机器数。目标是将所有工件安排到机器上加工,使得时间表长最小。首先分析一些特殊情况;然后对于一般情况通过建立注水模型给出最优时间表长的一个下界;接着对水位的2种情况分别给出目标值等于下界的多项式时间算法;最后给出了求解该调度问题的一个多项式时间最优算法。     

关于工件组的两机自由作业时间表问题

讨论关于工件组的两机自由作业时间表的加工全长问题，无论是对于成组加工情形还是分组情形，该问题都可以被证明是ＮＰ困难的。对于成组加工情形，设计了一个性能比为５／４的近拟算法，该算法生成的时间表作为分组情形的解，性能比仍能保持为５／４。此外，还讨论了如何最优地求解只有一个工件组的情形。     

利用拉格朗日松弛算法求解三维分配问题

将拉格朗日松弛算法与最优求解算法的复杂性进行了分析比较，并将该算法应用于求解3-D分配问题,分析与算例结果表明，该算法可大幅度降低3-D分配问题的求解计算量，是求解3-D分配问题的一种有效算法．     

带有拒绝工件和学习效应的资源约束排序问题研究

[目的]研究工件加工时间具有学习效应以及工件可拒绝的单机排序问题.在线性和凸资源分配函数的两种模型下,为求得可接受加工的工件集合、可拒绝工件的集合以及确定可接受工件集合中的最优工件排序,使工件的时间表长、总完工时间、资源耗费费用和工件拒绝费用的加权和最小.[方法]对于线性资源分配函数问题,在拒绝工件数给定的情况下,此问题可转化为指派问题.对于凸资源分配函数问题,此问题可以用动态规划算法进行求解.[结果]对于带有拒绝工件和学习效应的资源约束排序问题给出了最优求解算法,且它们的时间复杂度分别为O(n4)和O(n3),其中n为工件的个数.[结论]算法分析和CPU运算时间表明给出的求解算法非常有效.     

m台机器上流水作业时间表问题的复杂性及一种新的启发式算法

研究流水作业时间表问题，在具有延迟时间的条件下证明该问题是强NP-困难的．给出一种新的启发式算法，并证明该算法的最坏性能比是(m 1)/2，且上界是紧的．     

基于人类进化算法的背包问题求解方法

背包问题是计算机算法中的一个NP完备类困难问题,使用传统的优化方法在求解较大规模的背包问题时,都存在计算量大、迭代时间长的缺陷．人类进化算法是模拟人类进化机理而建立的一种智能优化算法,本文阐述了人类进化算法的基本原理和实现方法．为提高背包问题的求解速度和精度,将人类进化算法应用于背包问题的求解,演示了算法的工作过程．试验结果表明,使用该方法求解背包问题是完全可行的和有效的,与众多优化算法相比,人类进化算法具有更高的求解效率．     

基于到期收益率高精度求解的算法优化

介绍了债券到期收益率计算中的算法分析过程，将非线性到期收益率的求解转换为多项式求解问题，试验比较多种算法间差异，选择最优算法，满足应用系统性能要求．围绕多项式求解具有运算更加稳定、求导方便的优点，将复杂的有理分式求解转换为多项式求解．通过算法分析，论证了算法的精确性和严密性，最大化地实现了算法的优化；还通过具体的PL／SQL程序比较了算法间的差异。     

基于人工智能原理的大学课表编排模型

针对涉及因素多、结构复杂的大学课表编排问题,文章采用人工智能及专家系统的知识,成功地构造出大学课表编排的数学模型及有关编排算法。对排课的死锁问题进行了有效的处理,并用Ｆｏｘｐｒｏ实现了课表的自动编排,运行效果良好。     

一种求解TTP问题的SAGA算法

分析了高校课程表编排中涉及的各种约束条件和特殊要求,给出了一种求解TTP问题的模拟退火遗传算法(SAGA),并且对遗传算法中的交叉、变异操作采用自适应方式进行了改进,提高了算法在解空间中的探索能力和效率.数值实验证明了该方法的有效性和可行性.     

时间规划中D_时刻表的改进算法及应用

对既存在时间关系约束又存在时间宽度约束的n个事件,用时间规划的D_时刻表算法,可以求得2n个端点集的一个有序划分,该划分满足所有的约束条件.我们在应用中对算法进行了一些改进,增加了矩阵化简过程中的合并链和空事件,提高了算法的实用性.     

案例注入式遗传算法在大学课程表问题中的应用

遗传算法在解决大学课程表问题过程中往往采用随机方式来初始化种群,这就造成了运算量变大和复杂度增加等情况,从而影响了算法的性能.提出了一种改进的遗传算法——案例注入式遗传算法,该算法利用基于案例的推理对遗传算法进行初始化,以此加快算法的收敛速度.     

基于随机需求的接运公交时刻表的鲁棒性优化方法研究

接运公交需求的随机性会对接运公交时刻表的编制与投入运营产生扰动影响. 为降低此不利影响,基于鲁棒性思想研究了随机需求下接运公交时刻表的优化方法. 随机接运公交需求的每一组实现为一个情景,情景目标值综合考虑乘客成本与运营成本的最小化. 以接运公交需求为随机变量,建立了接运公交时刻表的鲁棒性优化模型,模型综合考虑情景的期望值与偏差期望值最小化. 模型具有组合优化与随机规划特性,选用遗传算法进行求解. 最后给出算例验证了模型与算法的有效性. 算例结果表明随着偏差权重系数的提高,鲁棒性模型更倾向于降低随机需求带来的扰动.     

课程表自动编排系统的设计与开发

给出了课程表自动编排系统的设计与开发过程,并着重讨论了自动编排算法中的动态优先、复合条件搜索及有限回溯问题．     

利用遗传算法求解大学课表问题

课表问题是一个多因素的优化决策问题，在分析大学课表问题的基础上，设计了一种全新的、基于三维数组的二进制编码方式及几个优化目标评价函数，用遗传算法求解，并通过实验证明这种方法大大提高了遗传算法的效率。     

基于矩阵行搜索求解排课表问题的算法

讨论了排课表问题的一种矩阵解法,提出了一种基于矩阵行搜索变换求解该问题的新方法,并给出了软件实现的详细步骤.不仅给出了算法的理论基础,还给出了程序实现时的一些技巧,算法的时间复杂度为O（n2e）,具有较高的效率和实用性.     

考虑延误与班期限制的多商品流多式联运方案优化

针对不确定时间影响的多商品流多式联运方案优化问题,以空铁联运为主,将运输时间转化为确定运输时间和不确定延误时间,同时考虑班期限制影响,以收货时间窗限制、准时率、运力等为约束条件,以所有订单总运输成本、运输时间和碳排放最小为目标,构建多商品流多式联运方案优化模型,并基于改进的非支配排序遗传算法Ⅱ(non-dominated sorting genetic algorithmⅡ,NSGA-Ⅱ)进行模型求解。实证分析表明：相对于无延误和班期限制,延误和班期限制均导致各目标值呈现不同程度增加;随着延误程度增加,总运输时间逐渐增加,而总运输成本还受到班期限制的耦合影响,呈现先减小后增加的周期性变化;碳排放量与运输成本呈现一致变化趋势;最后采用多属性决策方法获得考虑综合满意度的最优运输方案。研究结果可为实际中多式联运方案设计与优化提供参考。