考虑外包的平行机调度问题的多目标遗传算法

摘要：

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

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

分类号：O223(运筹学)

资助基金：国家自然科学基金资助项目71101040,71471052;安徽省自然科学基金资助项目1408085MG136;教育部人文社会科学研究规划基金资助项目14YJA630051

在线出版日期：2014-12-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：3174-3179