复杂并行机调度问题基于分解的优化算法

摘要

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题,提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题,然后针对机台选择子问题提出一种进化规划算法,并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题,以得到问题特征信息(即每台机器对应拖期工件数的最小值),该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明,本文提出的算法是有效的。