一类带平行机的两阶段柔性流水调度近似算法

本文研究一类柔性流水调度与平行机调度相结合的两阶段流水调度模型,模型中第1阶段有1台机器,第2阶段有m台同构并行机,每个任务在第2阶段需要size_i台机器同时并行执行.目标是所有任务都完成的完工时间最小化.该模型已被证明出是强NP难的,并给出了在某种特定情况下近似比为3的近似算法.本文首先详细分析了前人近似算法基本过程,给出该算法近似比分析的局限性;接着给出了一个近似比为3的算法,摒弃了前人给出的近似比为3时的约束条件;最后研究了当第2阶段机器数为2和3时的两种特定情况,采用列表调度思想,给出了近似比为2.5和2.67的近似算法.