论文部分内容阅读
本文重点研究任务等待时间受限的并行批处理调度问题,研究了单阶段调度和双阶段调度两个小问题,分别建立问题的约束规划模型。第一个问题是基础,求解它的“小s大S”规则也成为第二问题求解算法的一部分。 第一个问题是单阶段等待时间受限的并行批调度问题,设计类似库存管理中的“小s大S”规则,该调度规则最重要的参数为队长参数和考虑等待时间受限的时间限制参数,基于该规则进行模拟实验,用RSM响应面方法进行参数优化,将模拟结果同在CPLEX环境下用约束规划(CP方法)求得的解进行比较。“小s大S”规则在运行时间、目标函数优化效果、操作便利性方面都比CP方面表现优异。当机器数量比较少时(接近于任务族数量),“小s大S”规则和CP方法求得解的质量比较相似。随着机器数量的增多,“小s大S”规则求得解中每个任务平均完工时间逐渐减少,趋近于任务的加工时间,很少出现任务超过受限时间才开始加工的现象。而CP方法解的质量变化不显著,运行时间迅速加长,占用空间迅速变大。 第二个问题为两阶段的并行批调度问题,引入上游的预处理加工机器。结合单阶段批调度的“小s大S”规则,设计了两种求解算法,分别为SPT-(s,S)算法与PSO-(s,S)算法。算法的SPT(最短加工时间规则)部分和PSO(粒子群算法)部分用于第一阶段的调度,“小s大S”规则用于第二阶段的调度。两种算法都能很好的解决两阶段的并行批调度问题,SPT-(s,S)算法操作简单,但是求解质量不高,PSO-(s,S)算法求解速度快而且解的质量也很好,在小规模问题中能救出最优解。两种算法分别与约束规划的方法(CP方法)相比较,求解大、中规模的问题很有优势。