基于灰熵并行分析优化算法的多目标流水车间调度

朱光宇，贺利军

（福州大学机械工程及自动化学院，福州 350108）

基于灰熵并行分析优化算法的多目标流水车间调度

朱光宇，贺利军

（福州大学机械工程及自动化学院，福州 350108）

在供应链环境下构建一个多目标Flow Shop调度优化模型，采用灰熵并行分析（GEPA）法优化该多目标模型。在表征序列间相似程度的灰关联分析法基础上引入信息熵理论建立GEPA法，推导出的灰熵并行关联度衡量多目标Pareto解与理想解的相似程度，并将其作为适应度值引导算法进化，避免多目标优化问题中直接对目标权重赋值。在此基础上建立基于灰熵并行分析的遗传算法。实验结果表明，该算法可有效解决供应链环境下高维多目标Flow Shop调度问题，在多目标最优解、性能评价指标等方面均优于基于随机权重的遗传算法。

供应链；多目标Flow Shop；灰熵并行分析法；灰熵并行关联度；多目标优化；遗传算法

DO I：10.3969/j.issn.1000-3428.2015.10.031

1 概述

供应链环境下的企业生产比单个企业内部生产更加复杂，不但要考虑自身企业内部的生产调度问题，还要考虑到供应链上其他节点企业的因素，如原料采购、交货期、库存、运输等。国内外对供应链生产调度这一热点问题已取得一定的研究成果，如文献［1］提出供应链调度的概念；文献［2］研究了供应链环境下等待约束的流水线调度问题；文献［3］构造了遗传粒子群混合算法，运用混合算法对供应链优

化调度问题进行求解。

供应链环境下的生产调度涉及的绝大部分为多目标问题［4］，其目标维数一般要比单个企业生产调度问题目标维数大。目前求解供应链环境下企业生产调度问题的方法主要有多目标规划法和多目标智能算法，其中遗传算法（Genetic Algorithm，GA）、PSO等多目标智能算法应用越来越频繁，且2种方法研究的多为 3个目标以下的低维问题，如文献［5-6］应用多目标规划法根据固定的目标权重进行线性加权求和，优化双目标供应链问题；文献［7］设计了一种混合遗传算法求解单目标敏捷供应链调度优化问题；文献［8］提出利用广义遗传粒子群算法求解单目标供应链问题。

多目标规划法适用于求解规模较小的问题，权重选取主观因素太大，各目标间数量级和量纲也难以统一，求解规模较大的供应链问题收效甚微；多目标智能算法由于各目标相互制约，优化解在解质量、收敛性等指标上难以让人满意，其主要难点在于适应度分配策略的选取。现有适应度分配策略主要有Pareto优先排序关系［9］和随机权重［10］2种。2种适应度分配策略的缺点在于：单纯的Pareto优先排序关系方法不能很好地解决高维多目标问题，目标维数越高搜索的盲目性越大；随机权重法求解高维多目标问题时虽然优于基于Pareto优先排序方法，但忽略了Pareto解改善时可能提供的趋向性指示信息，处理高维问题时效率低［11］。 当问题规模较大、目标维数较高时，现有多目标规划法和多目标智能算法适应度分配策略的缺点更突出。

鉴于以上问题，本文建立五目标供应链优化模型，采用灰熵并行分析法与智能算法结合优化该模型。灰熵并行分析法是灰关联分析与信息熵结合的一种方法，其推导出的灰熵并行关联度是不确定序列间相似程度的度量。将灰熵并行分析法与通用性强的GA结合，建立基于灰熵并行分析的GA，以灰熵并行关联度衡量Pareto解与理想解的相似程度，并将其作为适应度引导算法进化。

2 基于灰熵并行分析的多目标优化

灰熵并行分析法是在表征序列间相似程度的灰关联分析法基础上引入信息熵理论发展而来的一种方法，其特点在于利用灰色关联分析和信息熵并行地对序列数据进行相似性分析。已有文献将灰关联分析法和信息熵理论分别应用于多目标优化中，如文献［12］利用灰关联分析法导出的灰关联度衡量Pareto解的好坏，但该方法容易导致信息丢失和陷入局部关联倾向；文献［13］将信息熵理论应用于多目标优化，以保持解的分布均匀性和多样性，其缺点在于没有有效利用各目标间关联信息。灰关联分析法和信息熵理论结合成的灰熵并行分析法能够克服2种方法的弱点，可以更好更全面地分析不确定序列间的相似接近程度。灰熵并行分析法应用于多目标优化时主要问题在于构造理想解序列与Pareto解比较序列、序列间的灰关联分析和序列间的灰熵并行分析。

2.1 理想解序列与Pareto解比较序列构造

灰熵并行分析法应用到多目标优化时，首先需要找到理想解序列与Pareto解比较序列，然后计算2个序列的灰熵并行关联度值，该值越大，则Pareto解比较序列与理想解序列越相似。

（1）理想解序列构造

对多目标优化的每个子目标实现 k次单目标优化，各子目标的单目标优化解的平均值构成理想解序列Y0=｛f1（0），f2（0），…，fM（0）｝，其中，M为目标个数；fM（0）为第 M个子目标的单目标优化解。

（2）Pareto解比较序列构造

多目标优化中生成的Pareto解，构成Pareto解比较序列Yi=｛f1（i），f2（i），…，fM（i）｝，i=1，2，…，N，fM（i）为Pareto解的第M个子目标值。

2.2 灰关联分析

灰关联分析的基本思想是根据序列曲线几何形状的相似程度来判断其联系是否紧密。曲线越接近，相应序列之间灰关联度就越大，反之就越小［14］。因此，可以将灰关联分析法应用于多目标优化来分析理想解序列与Pareto解比较序列的相似程度。灰关联分析法对理想解序列与Pareto解比较序列进行关联分析的过程如下：

（1）均值化

通过均值化算子对理想解序列与Pareto解比较序列的各子目标均值化处理，以消除目标间数量级和量纲的影响，均值化算子公式如下：

其中，k=1，2，…，M；i=0，1，…，N。

（2）求两级最大差和最小差：

其中，k=1，2，…，M；i=1，2，…，N。

（3）求灰关联系数：

其中，ρ∈（0，1）为分辨系数；k=1，2，…，M；i=1， 2，…，N。

2.3 灰熵并行分析

式（5）导出的灰关联度r（Y0，Yi）表征的是理想解序列与Pareto解比较序列的相似程度，该值越大，相似程度越大。但灰关联度值计算的是灰关联系数的平均值，这容易导致信息丢失；同时灰关联度值具有局部关联倾向，倾向于灰关联系数大的目标。针对这2个弱点，引入信息熵内容，计算多目标解各子目标的熵值权重，与灰关联分析法结合成灰熵并行分析法，以期克服灰关联分析的弱点。

（1）计算式（1）中Pareto解序列均值化后各子目标所占比重，即：

（4）求灰关联度值：

其中，k=1，2，…，M；i=1，2，…，N。

（2）计算Pareto解序列各子目标的信息熵：

其中，k=1，2，…，M；i=1，2，…，N。

（3）计算Pareto解序列各子目标的熵值权重：其中，k=1，2，…，M；i=1，2，…，N。

（4）熵值权重和灰关联系数结合，计算灰熵并行关联度R（Y0，Yi）：

其中，k=1，2，…，M；i=1，2，…，N。

灰熵并行分析法是动态灰过程发展态势整体接近性分析与信息熵结合的方法，是一种全局方法。灰熵并行分析法对于分析对象的数据序列不需要其服从某一特定分布，其主要以目标数据为基础，对于所研究目标数据离散或数据不充分问题均适用，因此可以应用于供应链环境下多目标Flow Shop调度优化问题中。以灰熵并行关联度作为适应度引导智能算法进化，灰熵并行关联度值越大表明优化解越相似于理想解。

3 问题描述及多目标模型

3.1 问题描述

本文构建了一个线性供应链问题，涉及到供应链上原料供应商、制造商和销售商3个企业，涉及到原料采购、生产、运输等供应链活动。具体问题描述如下：

制造商从销售商接到一订单，需要加工一批数量为n的工件，完工后运输到销售商。制造商工厂为典型Flow Shop生产类型，即n个工件由m台机器加工，每个工件具有一定数量的工序，每个工件以相同顺序访问所有机器，工件在机器上的加工时间固定［15］。整个供应链活动由以下部分组成：

（1）制造商加工工件前从原料供应商处采购加工原料，原料采购成本和原料运输成本都为固定值。受到销售商交货期和自身库存影响，制造商必须在合理时间完成工件。超过交货期完工的工件将受到拖期惩罚，产生拖期成本，提前完工的工件将产生库存成本。拖期成本和库存成本都与时间成正比。

（2）工件完工后将批量性运输到销售商，运输工具最大运载数量固定。假设制造商完工工件达到运输工具最大运载数量时即开始运输，每次起运时刻为每批最后一个工件完工时间，若最后一批工件数不足最大运载数量则按一批运输。

本文问题是确定工件加工顺序，使工件最大完工时间、最大拖期时间、总流程时间、总库存成本和总拖期成本5个目标最小。

3.2 多目标模型

本文建立的多目标模型为F=m in（f1，f2，f3，f4，f5），其中：

其中，f1为工件最大完工时间；f2为最大拖期时间；f3为总流程时间；f4为总库存成本；f5为总拖期成本。Ci，Di，Li分别为工件i最后完工时间、交货期和起运时刻，处于同一批次工件起运时刻一致；Tik为工件i的第k道工序所需加工时间；Cik表示工件i的第k道工序完工时间；g，h分别表示原料和完工工件运输工具单次最大运输数量；V（i），S（j）分别表示原料和工件运输工具单次实际运输数量；a，b分别表示原料和工件批量运输次数；βi，γi分别表示单位时间库存和拖期成本。

4 多目标Flow Shop调度问题

遗传算法（GA）已经被应用于众多领域，本文将灰熵并行分析法与GA结合，同时优化供应链模型的5个目标。考虑到Flow Shop调度生产工件加工路线和工序相同的特点，GA编码采用基于工件顺序的编码方案［16］。基于灰熵并行关联分析的GA求解供应链环境下多目标Flow Shop调度问题的具体步骤如下：

步骤1 利用GA对问题的各目标单目标优化，单目标优化解构成理想解序列 Y0。产生初始种群，生成NP个个体为种群当代代数。利用式（10）～式（14）计算个体的多目标函数值，各目标值构成Pareto解序列

步骤2 利用式（9）计算理想解序列 Y0与 Pareto解序列的灰熵并行关联度，并将其作为GA适应度值引导算法进化。

步骤3 选择操作。采用二元锦标赛［17］方法进行选择。

步骤4 交叉操作。采用部分映射交叉（PMX）［17］方法交叉，交叉概率Pc一般取0.40～0.99。

步骤5 变异操作。采用互换变异（SAWP）［17］方法变异。变异操作可以维持群体多样性，Pm一般取0.001～0.1。

步骤6 外部档案维护和更新。通过非劣排序以及拥挤距离［16］对每代产生的非劣解进行计算，将每次迭代产生的解与外部档案Pareto解进行优劣比较，进行相应的删除、添加操作更新Pareto解，即对外部档案进行更新，通过精英保留策略使得种群的多样性得到提升。

步骤7 判断是否满足终止条件。群体适应度值连续一定次数不发生变化或者进化次数达到要求的最大代数maχgen时迭代终止；否则，gen=gen+1转步骤2。

上述算法实现过程中，主要是步骤1、步骤2和步骤6会对GA复杂度造成影响。其中，步骤1的时间复杂度为O（n×m×M×maχgen×NP2）；步骤2时间复杂度为O（maχgen×NP）；步骤6时间复杂度为O（maχgen×Wmax×log Wmax）；标准多目标GA时间复杂度为O（n×m×M×maχgen×NP2），其中，n为问题工件数；m为工序数；M为目标数；maχgen为迭代代数；NP为种群规模。由此可知时间复杂度量级最大的步骤1与标准多目标 GA时间复杂度相同，并没有增加 GA时间复杂度。算法空间复杂度方面，由于本文算法程序所需存储空间都很小，计算机设备完全能满足其存储空间要求，本文算法也不会对GA空间复杂度造成明显影响。

5 仿真实验与结果分析

为验证灰熵并行分析法的有效性，本文参考文献［17］方法对供应链环境下的制造商工厂产生16个不同规模的调度问题实例。从多目标最优解、各性能指标等方面，将基于灰熵并行分析的遗传算法（Grey Entropy Parallel Analysis Method Genetic Algorithm，GEPA-GA）与基于随机权重的遗传算法［18］（Random Weighting Genetic Algorithm，RW-GA）进行比较，因为基于随机权重的非Pareto优先排序方法被证实在处理高维问题时表现较好［11，19］。 通过分析比较说明该方法的有效性，展示算法GEPA-GA在求解供应链环境下多目标Flow Shop调度问题的优越性。

5.1 参数设置

算法的种群规模 NP=20，外部档案个体数Wmax=50，最大迭代次数maχgen=100。GA交叉概率Pc=0.75，变异概率Pm=0.1。单目标优化次数k=10。单位库存成本βi=1.5，单位拖期成本γi= 2。原料每批运输最大数量g=10，完工工件每批最大运输量h=5。灰关联分析分辨系数ρ=0.5。

5.2 评价指标

本文采用当代距离（Generational Distance，GD）、间隔距离（Spacing，SP）和相对于理想解平均百分比偏差（ARPD）3个参数作为算法性能评价指标。

（1）当代距离［20］（GD），表征算法所得非劣解集与理想解间的接近程度，评价算法的收敛特性。计算公式为为外部档案个体数，di为第i个非劣解与理想解间的欧氏距离，GD值越小表示与理想解越接近。

（2）间隔距离［21］（SP），表征算法所得非劣解集的解分布情况。SP计算公式为：

（3）相对于理想解的平均百分比偏差［22］（Average Percentage Deviation，ARPD），表示算法所得解的平均质量，偏差越小，解的质量越高。子目标M的ARPD（M）计算公式为：

其中，Wmax为外部档案个体数；FHM（j）为外部档案个体j的第M个目标的值；fM（0）为理想解的第M个目标的值。

5.3 结果分析

表1为2种算法的仿真实验结果，在实例1、2、6、9、10、13、14中，算法GEPA-GA所得多目标最优解有4个目标要好于算法RW-GA；实例3，4，5，7，8，11，12，15，16中，算法GEPA-GA在5个目标上都要好于算法RW-GA。这说明在解决该类问题上，GEPA-GA在整体上都要优于RW-GA。16个实例的灰熵并行关联度（GEPRD）均在0.8以上，表明GEPA-GA所得多目标最优解与理想解的相似程度都比较高。

表1 16个问题实例的仿真结果

表2为2种算法性能评价指标结果，在当代距离（GD）指标上，除实例1，9，10，16外，其余12个实例上算法GEPA-GA的GD值都要小于算法RW-GA，表明算法GEPA-GA的收敛性整体上要好于算法RW-GA。在间隔距离（SP）上，除实例7，9，11，15，16外，其余11个实例上算法GEPA-GA的SP值都要小于算法RW-GA，表明算法GEPA-GA的解集整体上比算法RW-GA的解集分布更均匀。在相对于理想解的平均百分比偏差（ARPD）指标上，除实例1的第4个目标（f4）外，算法GEPA-GA在各实例上各目标的ARPD值都要小于算法RW-GA，说明算法GEPA-GA的多目标优化解的质量要高于算法RW-GA的多目标优化解；算法GEPA-GA在一些实例中的ARPD值出现负数情况，表明算法GEPA-GA的多目标优化解的某些目标的质量甚至要高于理想解。ARPD值出现负数情况可能是以下两方面原因导致的：首先，GA是一种随机搜索算法，每次搜索到的最优解之间可能存在微小偏差，且本文理想解构造方式为单目标优化解的平均值，其大小会比真实最优解稍大；其次，本文算法迭代终止条件都为达到指定代数时终止，算法迭代次数达到指定代数时可能尚未完全收敛，导致其最优解与真实最优解之间存在误差。仿真实验结果表明，本文所采用灰熵并行分析法可以有

效解决多目标优化问题，基于灰熵并行分析的遗传算法在求解供应链环境下多目标Flow Shop调度问题时，其多目标最优解、算法性能评价指标都要优于基于随机权重的遗传算法。

表2 2种算法的性能评价指标结果

6 结束语

本文提出采用灰熵并行分析法进行多目标优化。建立基于灰熵并行分析的遗传算法，以灰熵并行关联度作为适应度引导算法进化，优化供应链环境下多目标Flow Shop调度问题。仿真实验结果表明，灰熵并行分析法与遗传算法可有效结合，基于灰熵并行分析的遗传算法可以有效解决供应链环境下多目标Flow Shop调度问题，显示出了灰熵并行分析法在解决高维多目标优化问题的优越性。

［1］ Hall N G.Supply Chain Scheduling：Batching and Delivery［J］.Operations Research，2003，51（4）：566-584.

［2］ Chauhan S S，Gordon V，Proth J M.Scheduling in Supply Chain Environment［J］.European Journal of Operational Research，2007，183（3）：961-970.

［3］ 刘小华.基于遗传粒子群混合的可重入生产调度优化［J］.同济大学学报：自然科学版，2011，39（5）：726-731.

［4］ 黄明达，刘 林.供应链下Flow Shop调度问题的多目标混合算法研究［J］.合肥工业大学学报：自然科学版，2011，34（10）：1564-1569.

［5］ 杨 懿.产供销一体化的供应链生产多目标规划模型［J］.西华大学学报，2006，25（6）：93-95.

［6］ 周金宏，汪定伟.考虑多运输方式的供应链生产计划多目标模型［J］.系统工程学报，2000，15（4）：362-366.

［7］ 王建华.求解敏捷供应链调度优化问题的混合遗传算法［J］.计算机工程与应用，2011，47（17）：224-228.

［8］ 胡桂武.基于广义遗传粒子群优化算法的供应链优化求解［J］.计算机应用，2008，28（11）：2840-2843.

［9］ Elaoud S，Loukil T，Teghem J.The Pareto Fitness Genetic Algorithm：Test Function Study［J］.European Journal of Operational Research，2007，177（3）.

［10］ 王 凌.车间调度及其遗传算法［M］.北京：清华大学出版社，2003.

［11］ 卫 忠.多目标混合流水车间作业调度的演化算法［J］.计算机集成制造系统，2006，12（8）：1227-1234.

［12］ 李俊峰，戴文战.基于遗传算法和灰色关联度的多目标问题求解方法研究［C］//第25届中国控制会议论文集.北京：航空航天大学出版社，2006：557-560.

［13］ 王 娜.基于混沌多目标粒子群优化算法的云服务选择［J］.计算机工程，2014，40（3）：23-27，38.

［14］ 刘思峰，谢乃明.灰色系统理论及其应用［M］.北京：科学出版社，2008.

［15］ 雷德明.现代制造系统智能调度技术及其应用［M］.北京：中国电力出版社，2010.

［16］ 雷德明，严新平.多目标智能优化算法及其应用［M］.北京：科学出版社，2009.

［17］ Ishibuchi H.Balance Between Genetic Search and Local Search in Memetic Algorithms for Multi-objective Permutation Flow Shop Schedul-ing［J］.IEEE Transactions on Evolutionary Computa-tion，2003，7（2）：204-223.

［18］ Konak A.Multi-objective Optimization Using Genetic Algorithm s：A Tutorial［J］.Reliability Engineering and System Safety 2006，91（1）：992-1007.

［19］ Hughes E J.Evolutionary M any-objective Optimization：Many Once or One Many［C］//Proceedings of IEEE Congress on Evolutionary Computation.Edinburgh，UK：IEEE Service Center，2005：222-227.

［20］ Abraham A，Jain L.Evolutionary Multi-objective Optimization［M］.［S.1］：Springer，2006：18-20.

［21］ Gong Maoguo.Multi-objective Immune Algorithm with Nondominated Neighbor-based Selection［J］.Evolutionary Computa-tion，2008，16（2）：225-255.

［22］ 齐学梅，罗永龙.求解流水车间调度问题的混合粒子群算法［J］.计算机工程与应用，2012，48（9）：33-39.

编辑 索书志

Multi-objective Flow Shop Schedule Based on Grey Entropy Parallel Analysis Optimization Algorithm

ZHU Guangyu，HE Lijun
（College of Mechanical Engineering&Automation，Fuzhou University，Fuzhou 350108，China）

This paper establishes a multi-objective Flow Shop schedule optimization model under the environment of supply chain and optimized with the Grey Entropy Parallel Analysis（GEPA）method.Based on the grey relational analysis method，which expresses the similar degree between sequences，the information entropy theory is adopted to establish grey entropy parallel analysis method.The Grey Entropy Parallel Relational Degree（GEPRD）deduced by this method is used to measure the similar degree between multi-objective Pareto solutions and ideal solution and is used as the fitness to guide the evolution of the algorithm.By this way，the shortcoming that assignment the target weight directly in multi-objective optimization problem is overcome.The Genetic Algorithm based on Grey Entropy Parallel Analysis（GEPA-GA）is established.Experimental results show that GEPA-GA can solve high-dimensional multi-objective Flow Shop schedule problem under the environment of supply chain effectively.The multi-objective optimal solution and performance evaluation index of GEPA-GA are all superior to Genetic Algorithm based on Random Weighting（RWGA）.

supply chain；multi-objective Flow Shop；Grey Entropy Parallel Analysis（GEPA）method；Grey Entropy Parallel Relational Degree（GEPRD）；multi-objective optimization；Genetic Algorithm（GA）

朱光宇，贺利军.基于灰熵并行分析优化算法的多目标流水车间调度［J］.计算机工程，2015，41（10）：165-170.

英文引用格式：Zhu Guangyu，He Lijun.Multi-objective Flow Shop Schedule Based on Grey Entropy Parallel Analysis Optimization Algorithm［J］.Computer Engineering，2015，41（10）：165-170.

1000-3428（2015）10-0165-06

A

TP18

福州市科技计划基金资助项目（2012-G-131）；福建省教育厅科技计划基金资助项目（JK 2013006）；福建省自然科学基金资助项目（2014J01183）。

朱光宇（1970-），男，教授、博士，主研方向：多目标优化；贺利军，硕士研究生。

2014-09-22

2014-11-15E-m ail：zhugy@fzu.edu.cn