同等并行处理机上独立任务的调度

ｎ个独立任务在ｍ个同等并行处理机上处理，使总完成时间最小的非抢先调度是确定性调度理论的一个基本问题．文中提出一种算法——ＢｏｕｎｄＦｉｔ算法，它的最坏情况性能至少和ＭＵＬＴＩＦＩＴ算法一样甚至更好。

一类资源负荷均衡问题的双最小平衡调度算法

针对一类n个独立任务在m个不完全同等的处理机上处理 ,使处理机的最大负荷为最小的非抢先调度问题 ,在最小平衡算法的基础上提出了双最小平衡算法 ,并分析了它的时间复杂性。在此基础上 ,提出了基于遗传的双最小平衡算法 。

一类资源负荷均衡问题的优化调度算法

针对一类n个独立任务在m个不完全同等的处理机上处理 ,使处理机的最大负荷为最小的非抢先调度问题 ,提出了一种启发式算法———最小平衡算法 ,并分析了它的时间复杂性。在此基础上 ,又将最小平衡算法和遗传算法结合起来 ,提出了基于遗传的最小平衡算法 ,并用实例证实了该算法的有效性。

求解一类并行多机调度问题的混合启发式算法

该文研究了一类工件具有不同释放时间的并行多机调度问题 ,调度目标为使总流程时间最小。针对该类调度问题具有强NP -hard的特点 ,首先构造了的一种启发式算法 ,该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降 ,结合遗传算法的全局搜索能力 ,提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点 ,能够在较短的时间内求解较大规模的调度问题 ,算法的计算量小 。

启发式任务调度中的处理器选择策略

任务调度是并行分布计算中最为基本、最为关键，也最具有挑战性的问题之一，是影响并行分布计算执行效率的一个关键因素．现有的基于任务静态优先级的启发式任务调度方法都是以“当前任务具有最早起始执行时刻”为目标来选择执行处理器．该文在详细分析讨论该种调度方法的基础上，指出了以该目标选择处理器存在的问题及缺点，并提出了以“当前任务的直接后继具有最早起始执行时刻”为目标选择处理器的方法，并给出了相应的约束条件．

平行机问题中GKK算法性能比界的改进

将n个工件分配到m台平行机上加工,在工件的加工不中断及目标函数是极小化最大完工时间的条件下, 对其GKK算法的最坏情形性能比界作了改进,并用实例表明了所得新上界的可达性.

考虑能耗成本和拖期成本的非同等并行机调度

针对橡胶轮胎硫化车间能源消耗大,浪费严重的现象,提出一类考虑能耗成本与拖期成本的非等同并行机调度问题,建立基于硫化机正常运行、空闲、停机三种运行状态的能源消耗成本与拖期成本的调度模型。设计了基于优先调度规则的启发式算法、基于能耗优化的启发式算法、组合启发式算法用于模型求解,并通过仿真实验分析、比较了各种算法的有效性与适用环境。同时,仿真实验结果也表明本文提出的考虑能耗成本和拖期成本的非同等并行机调度问题具有一定的理论与实践意义。

一类资源负荷均衡问题的误差极小化调度算法

针对一类n个独立任务在m个不完全同等的处理机上处理,使处理机的最大负荷为最小的非抢先调度问题,在双最小平衡算法的基础上提出了误差极小化算法,并分析了它的时间复杂性。在此基础上,提出了基于遗传的误差极小化算法,并通过仿真实例证实了它在结果上优于基于遗传的双最小平衡算法。

AN IMPROVED BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE WEIGHTED FLOWTIME ON IDENTICAL PARALLEL MACHINES WITH FAMILY SETUP TIMES

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.