摘要：研究了一类考虑外包的平行机调度问题,目标是使作业外包总成本与最大完工时间同时最小化。通过对该类问题进行形式化描述与分析,设计了一种数字串形式的解的表示方法,其中每位数字表示固定作业对应的机器编号,该方法能够有效缩小解空间,从而提高搜索效率。进而构建了一种带精英策略的非支配遗传算法PD-NSGA-Ⅱ,为该类多目标调度问题提供Pareto最优解集。大量数据实验结果表明,所构造的PD-NSGA-Ⅱ算法能够在合理的时间内有效求解该类调度问题,其解的质量与计算效率均优于SPEA算法。

关键词：平行机调度 外包 pareto最优 非支配遗传算法 

单位：合肥工业大学; 合肥230009; 过程优化与智能决策教育部重点实验室; 合肥230009