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

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

Decomposition-based Optimization Algorithm for Complex Parallel Machine Scheduling Problems

A decomposition-based optimization algorithm is presented for solving larger scale parallel machine scheduling problems with the objective of minimizing the total number of tardy jobs and machine eligibility restriction in textile manufacturing process.Firstly,the whole scheduling problem is decomposed into two sub-problems: the machine selection problem and the job sequencing problem.Then,an evolutionary programming algorithm is proposed to solve the machine selection problem,and a polynomial optimization algorithm is adopted to solve the job sequencing problem in order that the problem characteristic information(the minimal value of the total number of tardy jobs on each machine),which is used to guide the search process of evolutionary programming,can be obtained.Numerical computational results of different scale parallel machine scheduling problems and practical application effects show that the proposed algorihm is effective.