两台等级平行机上部分处理时间已知的半在线调度

工作环境为两台处理速度相同的平行机M1,M2,工件具有两种不同的等级gj=1或2,等级gj=1的工件只能在第1台机器上处理,等级gj=2的工件两台机都能处理.已知等级gj=1的工件的处理时间之和,目标是最小化最大完工时间.主要思路为第一台机器预留出等级gj=1的工件的总处理时间,分析过程中只对等级gj=2的工件进行讨论.文章的三种半在线等级调度问题分别为已知最优处理时间,即已知C opt的情况,可得竞争比大于等于4/3,并有竞争比为4/3的半在线算法;已知工件的最大处理时间,可得竞争比大于等于4/3,同样有算法得出竞争比为4/3;对已知最优处理时间和工件最大处理时间的半在线问题,得到竞争比大于等于6/5,并且找到了相应的算法竞争比小于等于6/5.     

恒速机上的MapReduce在线排序算法下界研究

本文研究源自于MapReduce模型系统的一类排序问题。给定两台恒速机和一批按列表到达的工件,每个工件包含两类任务:Map任务和Reduce任务。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得这批工件的最后完工时间最小。对|M_j|≥|R_j|的情形,我们证明了任意在线算法的竞争比不小于1+(1/(2s+2)).     

带等级约束的多重工件在线(半在线)排序问题

论文提出了带等级约束的多重工件排序问题,每个客户提交多个加工时间和等级相同的工件。目标是寻找一个调度方案,使得机器的最大完工时间最小。当客户的信息未知时,论文设计了一个竞争比为5/3的在线算法。当所有工件的加工时间总和已知时,论文设计了一个竞争比为3/2的半在线算法。这些结论对经典带等级约束的两台平行机排序问题进行了推广。     

三台等级机器上带重排的半在线问题

研究了3台机上带2种等级的重排问题,当所有工件都被分配之后,在等级约束下,可以重排一台机器上的最后一个工件,目标是最小化最大完工时间。3台机上带2种等级分为2种情形：第1种是有1台机器的等级为1,另2台机器的等级为2;第2种是2台机器的等级为1,另1台机器的等级为2。针对第1种情形给出了一个竞争比下界为3/2,并提出了一个竞争比至多为5/3的在线算法;针对第2种情形给出了一个竞争比下界为3/2,并提出了一个竞争比至多为12/7的在线算法。     

三台机并行工件排序问题的改进的下界

与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。     

预测调度算法在平行机问题中的应用

常用的实时生产调度的在线算法由于只利用当前已到达的工件信息,导致调度性能不够理想。针对复杂度较高的平行机调度问题,通过对在线算法OMPR(单机可中断松弛)的改进,设计了一种具体的预测调度算法PPSA(平行机预测调度算法)。预测调度算法合理地把预知信息与已知信息结合起来进行决策,使调度解的性能得到进一步提高。仿真分析显示,该算法的性能明显优于在线算法OMPR,表明预测调度算法是一种计算简单、性能优良的实时调度算法。     

单步预测的单机调度算法及其仿真分析

调度问题中在线算法只能够利用已经到达的工件信息进行调度,但在实际生产中,往往有可能预知即将到达的未来工件信息,并且利用信息进行决策.针对经典单机加权完工时间调度问题,根据预测控制的思想,提出了一种单步预测调度的算法,并且分别在理论证明和仿真两方面进行了分析.对单步预测调度算法进行了性能分析,在理论上证明了预测调度算法的竞争比下界为2,对于一般的情况进行了大鼍的仿真比较,由于在调度中增加了未来信息,单步预测调度算法的调度结果优于在线调度算法.     

求解差异机器平行批调度的双目标协同蚁群算法

利用用户的偏好信息, 提出一种基于蚁群的双目标协同优化算法(Bi-objective synergy ant colony optimization algorithm based on Pareto domination, PDACO)并用于求解平行批处理机调度问题. 考虑在一组差异容量并带有不同加工功率的平行批处理机器上, 加工带有不同到达时间、尺寸和加工时间的一组工件, 以同时最小化最大完工时间和总能耗. 偏好向量的引入虽然可以提高算法的收敛性, 但会降低解的多样性. 为了弥补这一缺陷, 在本文所提算法中, 利用两个子蚁群分别沿着不同方向, 迭代地进行独立和联合搜索. 最后, 通过大量的仿真实验验证了本文提出算法的有效性.     

面向流程工业的批在线调度问题

从钢铁生产热轧流程中提炼出了在同构并行机上的批在线调度问题,它是流程工业中MES的重要环节。从理论上给出算法并研究了算法的性能。工件以批的形式到达,目标函数是使工件的最大完成时间最小。当一个批到达时,将这一批中的工件分成若干组,要求在同一组中的工件可以具有不同的开始加工时间但必须具有相同的完成时间。通过将批调度与在线调度的结合,给出了最坏情况比（竞争率）分别为m／（1＋（m-1）ε）,m（1-ε）／（1-ε）,m／（1＋gε）的批在线调度算法。     

针对经典排序问题的一种新算法的近似比分析

给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题。如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案。Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配。该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法。文章在此基础上,考虑该新算法在一般问题上的近似比。文中考虑了这个新算法的两种版本,分别得到了3/2和2-1/2 ^q(q∈Z⁺)的近似比。紧例子表明,文中对算法的两个版本的分析都是最优的。     

工件从大到小到达的带处理器费用的半在线调度算法

对大多数调度问题来说,处理器集往往是事先给定的,而且在算法进行过程中,它是不 变的.Imreh和Noga第一次提出了在调度中考虑处理器有费用的模型.他们研究了所谓的List Model问题,给出了竞争比为1.618的在线算法,同时证明了任意在线算法的竞争比至少是 4/3.该文研究List Model问题的一个半在线情形,即假设工件是从大到小到达的,给出一个竞 争比为3/2的半在线算法.同时证明对该问题的这一半在线情形,任意半在线算法的竞争比至 少是4/3.     

基于到达时间两台并行机上在线批调度

考虑两台同构并行机上在线批调度问题．每个批具有不确定的到达时间,一旦机器可以利用,要在当前可以利用的批中选择出合适的批,并将其中的工件调度到机器上,且工件在加工过程中不允许中断．目标函数是使调度的最大完成时间最小．给出了一个批在线调度ＲＢＬＰＴ算法,即选择当前批中加工时间之和最大的批按ＬＰＴ 规则调度．另外,利用反证法,对算法的最坏情况进行了分析．     

差异工件并行批调度问题中遗传算法研究

本文考虑了遗传算法在包含差异工件的并行批处理机调度中的应用问题.工件具有不同的尺寸和到达时间.首先基于问题假设提出了一个数学规划模型,并采用BF、ERT-LPT实现工件的分批排序调度.然后考虑到这是一个NP-Hard问题,设计了新的选择、交叉、变异操作并结合遗传算法进行求解.最后通过仿真实验对比,验证了算法的有效性.     

考虑恶化效应的MapReduce模型下的同类机调度

本文研究了MapReduce模型中考虑恶化效应的同类机调度问题. 在MapReduce模型中每个工件加工必须经 过两道工序. 其中在第1道工序中每个工件加工任务可分割成若干个子任务且能并行加工, 当某个工件中的所有子 任务全部完成后, 才允许启动第2道工序, 且第2道工序只能在一台机器上连续加工. 本文考虑了工件实际加工时间 与其开工前的等待时间呈线性函数关系的恶化效应, 构建了以最小化所有工件的逗留时间和为目标函数的混合整 数规划模型, 同时给出了问题的一个下界, 最后设计了采用正余弦差分扰动机制的改进蝙蝠优化算法来求解模型. 通过数值仿真对蝙蝠优化算法、遗传算法、CPLEX结果与下界进行对比, 验证了模型的正确性和改进算法的有效 性.     

基于到达时间两台并行机上在线批调度

考虑两台同构并行机上在线批调度问题．每个批具有不确定的到达时间,一旦机器可以利用,要在当前可以利用的批中选择出合适的批,并将其中的工件调度到机器上,且工件在加工过程中不允许中断．目标函数是使调度的最大完成时间最小．给出了一个批在线调度ＲＢＬＰＴ 算法,即选择当前批中加工时间之和最大的批按ＬＰＴ 规则调度．另外,利用反证法,对算法的最坏情况进行了分析．

     

极小化等待时间的热处理批调度模型与PSO解

机加车间的工件动态到达热处理车间后因受到批处理设备合批等的约束不能及时得到加工,基于工件动态到达的热处理车间,以最小化工件等待时间期望为目标,建立批调度模型,根据工件到达时间实现了粒子群算法微粒的编码以及对工件的分批,通过仿真实验得到结论:缩短工件的加工时间,则在热处理车间内,可以减小工件等待时间期望;降低工件数规模,工件会密集到达热处理环节,从而减短工件等待时间;工件的等待时间期望的大小与工件规模数量有关,工件数规模较小时,大尺寸工件的等待时间期望优于小尺寸工件,规模较大时,则相反。最后,对比分析了本文改进的粒子群算法的效果,发现改进的粒子群算法最优。     

带尺寸约束的二机流水车间生产运输协调博弈调度问题

研究二机流水车间生产运输协调调度问题,当工件在第1台机器加工完成后,由1台带有容量限制的运输车分批次运输到第2台机器加工,运输过程考虑工件尺寸约束,目标函数为最小化最大完工时间.考虑到源于不同客户的工件对机器及运输设备的竞争,以工件为博弈方,工件在生产运输过程中等待时间为策略,各工件完工时间为收益,建立非合作博弈模型.通过将问题转化为马尔可夫决策过程,设计线性逼近值函数的Q-learning算法求解纳什均衡调度.实验结果表明Q-learning算法求得的纳什均衡调度具有较好的全局最优性,从而能够在满足客户的利益下,提高企业的生产效率,实现客户与企业的双赢.     

基于MapReduce模型带任务分割的平行机调度优化

研究一类基于MapReduce模型的两阶段平行机调度问题.该模型中的每个工件包含Map和Reduce两道工序,前一工序的任务可以划分并同步加工,而后一工序不可划分,结合工件的到达时间、交货时间等约束,以最大完工时间和总延迟时间的加权和作为优化目标构建混合整数规划模型,设计采用差分变异策略和逐维角度扰动机制的改进鲸鱼优化算法求解模型.数值仿真实验结果表明,所设计的算法相对于经典的鲸鱼优化算法、粒子群算法的求解效果有显著的提升,验证了模型和所设计算法的有效性.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

大规模流水线调度的瓶颈分解算法研究

为了克服大规模流水线调度问题的计算复杂度,提出一种瓶颈分解启发式算法．利用瓶颈特性将流水线分解为瓶颈机和非瓶颈机,对瓶颈机建立带有到达时间和传递时间约束的单机调度模型,并优化求解,而在非瓶颈机上则采用简单的分派规则,通过不断修正瓶颈机上工件的到达时间和传递时间来协调瓶颈机与非瓶颈机之间的关联．仿真结果验证了算法的有效性．