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

申请免费试用、咨询电话：400-8352-114

1 引 言

生产过程调度问题是学术界和工业界的前沿性研究方向，也是制造执行系统技术研究中涉及的关键问题之一。近年来，以遗传算法为代表的进化计算方法以其具有较强的全局搜索性能，且易于融入与优化问题相关的知识等优点，在生产过程调度问题中获得了较为广泛的应用，并取得了一系列有价值的研究成果。然而大部分调度问题属于NP难题，这意味着随着问题规模的增大，解空间呈指数增长，单纯采用进化计算方法求解大规模复杂生产过程调度问题难以取得令人满意的效果。

本文以纺织生产过程为背景，研究了以最小化拖期工件数为目标，带特殊工艺约束的并行机调度问题，提出了一种基于分解的优化算法。

2 问题描述

首先将原调度问题分解为机台选择和工件排序两个子问题，然后针对机台选择子问题提出一种进化规划算法，并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题，以得到进化规划算法迭代过程所需的问题特征信息（即各机器对应拖期工件数的最小值），该特征信息用来确定进化规划算法中各机器对应基因位的变异概率。

由于工件排序子问题存在具有多项式时间复杂度的最优算法且该算法所需计算量小，因而可有效降低搜索空间；另一方面，通过上述算法求解得到的工件排序子问题特征信息可用以确定进化规划算法中各机器对应基因位的变异概率，因而能有效指导算法的搜索过程。

生产过程中有n个工件J1，J2，…，Jn，所有工件组成的集合为J，每个工件均只有一道加工工序，该道工序共有m台机器M1，M2，…，Mm，所有机器组成的集合为M。每个工件Ji具有确定的加工时间pi和交货期di。所有工件在零时刻均可加工，同一工件不能同时在多台机器上加工，同一机器不能同时加工多个工件，且加工过程一旦开始不可中断，直至加工完成。加工过程含有特殊工艺约束，即可加工工件Ji的机器集合μi满足μi?M，ui≠φ。设工件Ji的完工时间为Ci，

式（1）表示工件Ji是否拖期（1表示拖期，0表示未拖期），则该批工件的总拖期工件数，调度目标即是确定n个工件的加工机台和加工顺序，使得最小。

3 问题分解及算法结构

本文所研究的带特殊工艺约束的并行机调度问题可分解为如下两个子问题：

1）机台选择子问题  有n个工件Ji，J2，…，Jn，对每个工件Ji，确定加工该工件的机器Mk（Mk∈μj），使得原调度问题目标达到最优。

2）工件排序子问题  有n个工件J1，J2，…，Jn，m台机器，设机器Mj上的待加工工件集合为Sj，满足Sj?J，j＝1，2，…，m，确定Sj内各工件的上机顺序，使得总拖期数5最小。

基于上述问题分解的算法结构如图1所示。

最小。

3 问题分解及算法结构

本文所研究的带特殊工艺约束的并行机调度问题可分解为如下两个子问题：

1）机台选择子问题  有n个工件Ji，J2，…，Jn，对每个工件Ji，确定加工该工件的机器Mk（Mk∈μj），使得原调度问题目标达到最优。

2）工件排序子问题  有n个工件J1，J2，…，Jn，m台机器，设机器Mj上的待加工工件集合为Sj，满足Sj?J，j＝1，2，…，m，确定Sj内各工件的上机顺序，使得总拖期数5最小。

基于上述问题分解的算法结构如图1所示。

图1 基于问题分解的算法结构

在本算法中，首先由进化规划算法确定各工件的机台选择方案，然后采用具有多项式时间复杂度的最优算法求解工件排序子问题，以求得各机器对应工件的加工顺序，同时得到问题特征信息（各机器对应拖期工件数的最小值），该信息用以确定进化规划算法中各机器对应基因位的变异概率。在调度目标上，机台选择子问题的调度目标是降低总拖期工件数，工件排序子问题的调度目标是在机台选择方案确定后降低各机器对应的拖期工件数。

4 工件排序子问题的最优算法

本文基于1‖ΣUi调度问题的最优算法构造工件排序子问题的最优算法，其流程如下。

①初始化i＝1，j＝1，令Qj为机器Mj对应的未拖期工件集合，Qj＝φ（j＝1，2，…，m），t为调度时刻，t＝0；②将机器Mj对应的待加工工件集合Sj中的所有nj个工件按交货期di由小到大的顺序排序，不失一般性，设为d[1]≤d[2≤…≤d[nj；③若t＋p[i]≤d[i]，则Qj＝Qj∪{J[i]}，t＝t＋p[i]，转⑤；④若t＋p[i]＞d[i]，则分两种情形：

a）若p[i]＜p[k]（J[k]为集合Qj中加工时间最长的工件，若Qj＝φ，则p[k]＝0），则Qj＝Qj{J[k]}，Qj＝QjU{J[k]}，时t＝t－p[k]＋p[i]；b）若p[i]≥p[k]，转⑤；⑤若i＜ni，则i＝i＋1，转③；⑥若j＝m，则算法结束；否则令i＝1，t＝0，转②。

1‖ΣUi调度问题的最优解算法时间复杂度为O（nlog n）[7]（n为工件数）。由于上述工件排序问题由m个1‖ΣUi调度问题组成，且m个子问题间相互独立，因此上述算法的时间复杂度为O（mnlog n），仍为多项式时间算法。

5 进化规划算法设计

1）编码  本文采用如下编码方式表示各工件的机台选择方案，其染色体表示为

M1︱J11，J12，…，J1 n1︱；M2…Mm︱Jm1，Jm2，…，Jmnm︱

式中，nj（j＝1，2，…，m）为第j个机器对应的待加工工件数，第j个机器Mj对应的第i个基因位；Jji（j＝1，2，…，m；i＝1，2，…，nj）表示该机器上待加工的第i个工件，采用工件号表示相应的基因值。

2）初始种群产生  对每个染色体，从工件集合中J依次选择工件Ji，从其可加工机器集合μi中任意选择一台机器作为该工件的加工机器，同时，将该工件号加入至所选定机器对应的基因位中。

3）变异  本文提出的基于问题特征信息的变异方法将变异过程分为如下两个步骤：

①确定各机器对应基因位的变异概率pmj；采用第4 节中工件排序子问题的最优算法确定各机器上的工件加工顺序后，还可求得各机器对应拖期工件数的最小值Njtardy＝nj－︱Qj︱，其中︱Qj︱为集合Qj中元素的个数。依据上述特征信息，机器Mj对应各基因位的变异概率pmj为pmj＝pmmax×N[j]tardy/Nmaxtardy式中，Nmaxtardy＝max{Njtardy︱j＝1，2，…，m}；pmmax为最大变异概率。

②对染色体各基因位进行变异  在pmj确定以后，对机器Mj对应的各基因位采用位变异方法进行变异。其流程为：随机产生实数r∈[0，1]，若r＜pmj，则从该基因位对应工件的可加工机器集合中任意挑出一台机器作为变异后该工件的加工机器，同时在染色体中将该工件号从原加工机器对应基因位中去除，并将其加入至变异后加工机器对应的基因位中。同时，由于上述变异过程会将拖期工件数较多的机器对应的工件转移至其他机器上加工，因而若变异概率过大，可能会产生振荡现象。因此，为保证解在进化过程中逐步趋于稳定，最大变异概率pmmax随着迭代过程的进行逐渐变小。在本文算法中，第k 次迭代过程的最大变异概率pmmax（k）为pmmax（k）＝pmmax×（Nl－k＋1）/Nl式中，Nl为总迭代次数。

4）评价和选择  本文算法中，对每个个体对应的拖期工件数，采用指数定标的方法得到该个体的适应度函数值；定标后采用轮盘赌方式进行选择，以形成新一代种群。

6 数值计算及分析

采用来自实际纺织生产过程织布工序的生产数据对本文提出的算法进行数值计算。实际织布工序生产中，工件仅可在部分机器上加工，各调度时刻均有大量的工件等待上机，且各工件具有确定的加工时间和交货期，是典型的带特殊工艺约束的复杂并行机调度问题。

本文取三种规模（以n×m表示问题规模，其中n为工件数，m为机器数）的生产数据对本文所提出的调度算法（简称DPMA）与EOXA进行数值计算比较。其中对每种规模取6组不同时期的数据，不同组数据数值计算结果的总拖期工件数5取平均值。本算法各参数设置如下：种群规模Np＝20，迭代代数Nl＝30，最大变异概率pmmax＝0.5。在EOXA 中，种群规模Np＝40，迭代代数Nl＝30，其他参数同EOXA中设置相同。数值计算结果见表1。

表1 算法性能及运行时间比较

从表1可看出，本文算法在不同规模调度问题上的数值计算结果均优于EOXA算法，在大规模调度问题上的优化效果更为明显。在运行时间上，本算法也比EOXA算法小很多。

另外，为验证本文提出的利用工件排序子问题中的问题特征信息指导进化规划迭代过程方法的效果，本文比较了采用本文提出的变异方法与单纯采用位变异方法对应算法的优化效果。其中位变异方法的变异概率pm＝0.2，种群规模、迭代代数及初始种群产生方法、评价与选择方法等均与本文算法相同。两种算法在上述大规模并行机调度问题上的性能比较结果，如图2所示。

图2 采用不同变异方法的调度算法性能比较

从图2可看出，本文所提出的采用基于工件排序子问题特征信息指导的调度算法在大规模调度问题上的优化效果（收敛速度和总拖期工件数）明显优于单纯采用位变异方法的调度算法。这是由于本文算法在变异过程中采用的问题特征信息能有效反映各机器对应工件的机台选择方案的优劣，用该信息指导进化规划的迭代过程可使得机台选择不合理的工件及时得到校正，从而有效提高了进化规划算法的寻优效果。

本文提出的复杂并行机调度问题基于分解的优化算法已在某大型色织企业织布车间调度中得到成功应用，并取得了满意的效果。

7 结 语

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题，提出了一种基于分解的优化算法。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明，本文提出的算法是有效的。（万方数据）