具有服务等级的三台平行机排序问题

考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过54+12k,其中k是算法中预先给定的迭代次数.已有的算法仅为32.

一种独立任务的同型机调度快速算法

如何将n个独立任务调度到m台同型机上加工,使总完成时间最短,是一个复杂问题.通过分析Bound Fit预备算法的性质,结合MULTIFIT和Bound Fit提出QUICKFIT算法;对相同机器数和任务数,QUICKFIT能用比MULTIFIT和Bound Fit都少的迭代次数得到相同的总完成时间.实验结果表明,任务机器比越大,QUICKFIT算法的性能就越优于MULTIFIT和Bound Fit.绝大多数情况下,总完成时间等于MULTIFIT和Bound Fit中的最小者.该算法适用于大规模同型机调度.

非同起点加工的多机调度合成算法

针对调度 n个独立任务到初始时刻并非都空闲的 m台机器上加工 ,使得机器最长加工时间 (m akespan)最短的问题 ,改进 ML PT算法以减少运行时间 ,改进 MU L TIFIT算法以减少迭代次数 ,提出以改进的 ML PT算法结果为改进的 MU L TIFIT算法的初始上界的合成算法—— CMM,从理论上对 ML PT,MUL TIFIT和 CMM等算法的时间复杂度和调度结果进行了分析和比较 .实验结果表明 :改进的 MUL TIFIT比 MUL TIFIT的平均迭代次数少 ;CMM在平均迭代次数方面甚至比改进的 MUL TIFIT还少得多且调度结果不次于 MUL TIFIT和 ML PT的优者 .

天然气管道多部件设备成组维修模型

针对天然气管道系统多部件设备维修不合理的现象,为了有效降低系统的维修费用和改善系统的可用度,引入多部件设备成组维修策略,并以此为基础判断各部件是否需要进行预防性维修或更换。根据界限滚动方法,以节约的系统总维修成本最大化为目标,考虑维修环境的变化,以有限的维修人力资源为约束条件,在保证系统运行最低可利用率的基础上,建立了天然气管道系统多部件设备成组维修模型,从而为确定最佳的成组维修策略提供了理论依据。结合具体应用实例,整合Multifit算法和遗传算法进行仿真,求解得到天然气管道系统压缩机中各部件的最优成组维修计划。结果显示:所构建的模型能够最大限度地节约维修成本、合理地进行维修分组及确定最佳维修时间。