机器在一段时间不可用条件下的单机调度问题

文章对机器在一段给定时间内不可用情况下部分可恢复模式的单机调度问题进行了研究,当目标函数是最小化调度长度时,首先证明了LPT规则的误差上限是α/2,并举例说明该界限是紧的;同理可证该规则对不可恢复模式调度问题的误差上限是1/2,而不是有关文献所证明的1/3,同时上例也是1/3误差上限的反例;其次提出了一个启发式算法,该算法以LPT规则得到的解作为初始解,并结合基于成对交换技术的邻域搜索对解进行改进;当目标函数是最小化加权完成时间之和时,首先证明了最优调度的一个性质,并据此提出了动态规划算法。

资源受限下森林火灾应急救援多目标调度优化

许多森林火灾由于救援资源受限而不能在第一时间扑灭,导致火灾扩大蔓延,进而造成更大的森林资源损失。因此,在救援资源受限情形下,如何对消防救援车辆进行合理的调度安排以快速和低成本地扑灭火灾已成为亟待解决的现实问题。本文研究了一类资源受限下森林火灾应急救援多目标调度优化问题,为该问题构建了多目标混合整数非线性规划模型,优化目标为同时最小化总灭火救援时间和救援车辆总行驶距离。为有效求解该问题,首先将上述非线性模型等价转化为线性模型。然后提出ε-约束法和模糊逻辑相结合的算法对问题进行求解。最后,以大兴安岭山发生的火灾案例和随机生成仿真算例对模型和算法有效性进行验证,结果表明所提出的模型和算法能够有效解决资源受限下森林火灾应急救援问题,并为决策者提供最优的消防调度方案。

供应商选择模型与方法综述

供应商选择问题是学术界和工业界十分关注的优化决策问题,许多研究者进行了并且还在继续进行相关的研究工作。本文采用分类的方法归纳了供应商选择问题的研究进展,深入分析了在不同采购策略下供应商评价准则、供应商选择模型和优化方法。本文指出了各种研究方法的优缺点、适用范围、存在的问题,并且进一步指出未来研究的方向。

分布式供应链中基于准时制的原油采购计划方法

本文研究了分布式供应链多供应商/多炼油厂的原油采购计划问题,建立了在有限资源约束下的准时制多目标采购优化数学模型,以实现总采购费用和供应链循环时间最小。然后,本文将非线性规划模型转化为线性规划模型,并利用层次分析法(AnalyticHierarchyProcess,AHP)与多目标规划相结合的方法求解模型得到采购计划方案。数值仿真结果表明本文所提出的原油采购方法的有效性和实用性。

无限制背包问题的爬山算法

给出了一种求解整数背包问题的爬山解法 ,并对该算法的计算复杂度及最坏情形进行了理论分析 .通过与经典的求解背包问题方法的对比研究 ,给出了该算法的适用范围并展示其优越性 .数值实验表明 ,该算法简便易行 ,在其适用范围内具有计算复杂度低 ,近优程度高等优点 .

带不可用时间段的部分可续型单机最大完工时间调度

研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需部分进行重新加工.文中简单说明了此问题为NP-难问题,并证明了最大加工时间优先LPT规则的误差上限是α/2(其中α为重加工系数),进而提出了一个基于LPT规则的启发式算法.实验结果证明了此算法的高效性,此外对不同参数对此算法性能的影响也进行了分析.

带不可用时间段的部分可续型单机加权完工时间和调度

研究了机器带有一个不可用时间段的单机最小化加权完工时间和调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需进行部分重新加工.文中简单说明此问题为NP-难问题,并提出了一种动态规划算法和一种分枝定界算法来求得此问题的最优解.实验结果证实了这两种算法的正确性及有效性,且表明分枝定界算法要优于动态规划算法.

考虑乘客分流的异质车型通勤定制公交网络优化

定制公交作为城市需求响应交通的重要组成部分,其线网规划的优劣直接影响乘客满意度和系统运营成本.针对一类新的考虑乘客分流和异质车型的早晚高峰时期通勤定制公交网络规划向题,以最小化乘客旅行成本和公交系统运营成本为目标,同时优化异质车队路线、车型选择、行车时刻及乘客分配,构建了一个混合整数非线性规划模型.为有效求解该模型,提出了一种融合问题特征的改进自适应大邻域搜索算法,设计了基于问题特征的乘客分流破坏算子,以提升算法寻优能力.最后,大量算例结果验证了模型的正确性和算法的有效性.实验结果表明:求解小规模算例时,改进自适应大邻域搜索算法能在12秒以内获得距离最优解平均差距为0.24%的满意解;求解大规模算例时,与文献中大邻域搜索算法和遗传算法相比,所提出算法能获得更高质量解,平均成本节约分别为1.20%和2.27%;此外,与未考虑乘客分流和同质车型情形相比,考虑乘客分流和异质车型,得到的方案成本降低11.46%,提高了资源利用率.

资源受限下考虑救援优先级的森林火灾应急资源调度

在资源受限情况下,最大限度地减少森林火灾造成的资源损失,实施快速高效的森林消防应急救援成为亟待解决的现实问题.针对森林火灾救援问题的特点,根据不同火灾点的严重程度和火势蔓延速度对火灾救援优先级进行划分;在此基础上,以消防车辆救援时间最小化作为优化目标,建立消防救援车辆路径优化的混合整数线性规划模型.为解决资源受限下森林火灾应急资源调度问题,提出一种基于实数编码的改进人工蜂群算法.具体包括根据问题特点设计基于启发式思想的种群初始化,提出一种均匀策略提升解码质量,并设计高效的交叉算子提升雇佣蜂和跟随蜂的寻优搜索能力,避免算法陷入局部最优.最后,基准算例和大量随机生成算例对比测试结果验证了算法的有效性.