﻿ 基于混沌遗传算法的集团分布式制造工序资源配置
 控制与决策  2019, Vol. 34 Issue (6): 1178-1186 0

### 引用本文 [复制中英文]

[复制中文]
LI Yi-bing, SONG Dong-lin, WANG Lei. Group distributed manufacturing process resource allocation based on chaos genetic algorithm[J]. Control and Decision, 2019, 34(6): 1178-1186. DOI: 10.13195/j.kzyjc.2017.1526.
[复制英文]

### 文章历史

1. 武汉理工大学 机电工程学院，武汉 430070;
2. 武汉理工大学 数字制造湖北省重点实验室，武汉 430070

Group distributed manufacturing process resource allocation based on chaos genetic algorithm
LI Yi-bing , SONG Dong-lin , WANG Lei
1. School of Mechanical and Electronic Engineering, Wuhan University of Technology, Wuhan 430070, China;
2. Hubei Digital Manufacturing Key Laboratory, Wuhan University of Technology, Wuhan 430070, China
Abstract: There are some problems in group distributed manufacturing enterprises, such as the scatter of geographically location, the mismatching of manufacturing resources and abilities, the coexistence of resources idle and shortage etc. Based on the characteristics of multi-agent, multi-task, multi-resource, multi-process and co-ordination in the process of manufacturing resource allocation, the optimal model of distributed manufacturing resource allocation is proposed to balance the overall interests of the group and the individual interests of the sub-ordinate enterprises. An improved genetic algorithm based on Logistic chaos is designed to obtain the Pareto optimal solution of the model. Finally, an example with its analysis is given to demonstrate the effectiveness of the proposed model and algorithm.
Keywords: group distributed manufacturing    process-level resources allocation    chaos-improved algorithm    genetic algorithm    multi-objective optimization    Pareto optimal solution
0 引言

1 问题描述

1) 单工序集对于一个单工序任务, 由于其可以被某个单元层制造单元独立完成, 不涉及工序间由工艺流程造成的多样性和复杂性, 对其进行配置简单易行, 因此本文不考虑此种情形.

2) 多工序集订单任务被分解为多工序集后, 多个订单任务的工序集之间既有联系又有冲突, 由于工序具有通用性, 不同任务在某相同工序完成后的半成品是通用的, 故对多任务的工序配置具有复杂多样性.

 图 1 工序集子任务配置
2 数学模型的建立与描述 2.1 工序级制造资源配置模型

1) 工序利用率目标函数.

 (1)

 (2)

2) 资源利用率目标函数.

 (3)

3) 成本目标函数.

 (4)

 (5)
 (6)
 (7)
 (8)

2.2 总优化目标

 (9)

3 基于混沌遗传算法的模型求解

Step 1:算法参数的设定及染色体编码.与算法相关的参数包括种群规模PopSize、交叉概率Pc、迭代次数MaxGen、变异概率Pm以及精英保留个体数EliteNumber等.采用三维矩阵与二维矩阵相结合的整数编码, 能完整地对任务集各工序如何分配给制造集、每个任务的详细工艺流程以及资源的配置情况进行描述.具体为一条染色体包含一个可变三维矩阵MP、一个可变二维矩阵MR、以及定值二维矩阵TO, 即Pop=[MP, MR, TO].其中: MPi×j×k中元素x(k, i, j)表示任务TkPj道工序的工程量分配给制造主体Mi的配额, MRk×r中元素y(k, i, j)表示任务Tk需要的资源Rr由制造主体My(k, i, j)提供; TOk×j中元素e(k, j)表示工序Pj为任务Tk的第e(k, j)道工序, 即TOk×j表示任务集的工艺流程.

Step 2:基于Logistic映射的种群初始化.初始化种群即对Pop中的MP、MR两个矩阵进行赋值, 赋值过程需要保证染色体的随机性和合法性, 即对Pop随机赋值后进行合法性判断, 如果合法则进行下一步, 不合法则重新赋值直至合法, 合法性判断即为约束检查.

1) 首先取初值介于0~1之间的随机数r1j, j=1, 2, …, D.

2) 根据Logistic映射的形式产生向量ri+1=(ri+11, …, ri+1j, …, ri+1D)的各个分量ri+1j, 即

 (10)

3) 将产生的混沌变量映射到决策矢量空间(xi, minj, xi, maxj)中, 从而得到初始种群的第i个个体Xij=(xi1, …, xij, …, xiD)的第j个分量xij, 即

 (11)

Step 3:适应度评价.进行适应度评价前对染色体进行解码, 读出其工序配置信息以及资源供应信息, 然后求得其工序利用率、资源利用率以及成本3个指标.其中在对成本指标的求解中, 总成本包括采购成本、加工成本、超期成本以及运输成本4类, 由于每道工序的生产量为任务集之和, 即存在制造主体Mi中工序Pj的当期生产量包括多个任务的配额, 而经过相同工序后的各个任务的半成品存在可替换的通用性, 即各个工序间的半成品运输方案需要进行最优求解以达到运输成本最低, 本文对该工序间运输方案的求解流程如图 2所示.

 图 2 工序间运输配置流程

Step 4:联赛选择.本文采用轮盘赌的方法进行联赛选择, 即随机生成1~PopSize之间的两个不同随机数t1t2, 对种群中个体Pop(t1)以及Pop(t2)进行适应度比较, 取出适应度较大的个体存放入新种群newPopGen中, 累计进行PopSize次选择操作, 并以新种群替代原种群.

Step 5:排序.考虑到交叉与变异操作的随机性, 容易遗漏适应度值最高的个体而留下适应度值较低的个体, 因此在进行交叉和变异操作前对种群个体进行排序, 取其适应度值最大的前EliteNumber精英个体保存并略过交叉及变异操作, 从而提高收敛速度.

Step 6:多点交叉.从上述内容可知, 本文染色体Pop=[MP, MR, TO].其中: MP可分解为某工序Pj下任务集在Pj的所需工程量的配置子方案集, 即为染色体Pop的基因位.因此本文交叉操作具体为产生随机数rand(), 若rand()>pc, 则产生1-b的3个随机数t1t2t3, 对于个体Pop1和Pop2, 交换MP矩阵工序维度上的t1t2t3三维矩阵, 并对MR矩阵采取相同操作.交叉操作完成后对染色体子代进行合法性检查, 若满足, 则将子代替换父代并放入种群, 否则将父代放入种群.

Step 7:基于混沌的变异.文献[12-13]指出, 将Logistic混沌迭代方程应用到进化算法的自适应缩放过程中, 能有效地提高算法的寻优能力. Logistic映射又称为Logistic迭代, 是研究动力系统、混沌、分形等复杂系统行为的经典模型之一, 其本质是一个时间离散的动力系统.本文将Logistic混沌迭代方程应用于GA的变异过程中, Logisti混沌映射定义如下:

 (12)

Step 8:终止判断.当迭代次数gen>MaxGen时, 算法终止, 否则转入Step 3.

4 应用案例

 图 3 适应度值
 图 4 平均成本
 图 5 工序利用率
 图 6 资源利用率
 图 7 算法对比

 图 8 仿真实验结果

 图 9 仿真实验的Pareto最优解分布

5 结论

 [1] Wang L, Guo S, Li X, et al. Distributed manufacturing resource selection strategy in cloud manufacturing[J]. Int J of Advanced Manufacturing Technology, 2018, 94(9): 3375-3388. [2] 刘洪伟, 苑东平, 郑飞. 集团分布式制造模式下生产调配优化模型研究及算法设计[J]. 运筹与管理, 2017, 26(1): 1-7. (Liu H W, Yuan D P, Zheng F. Optimization of production allocation and algorithm design based on group distributed manufacturing[J]. Operations Research and Management Science, 2017, 26(1): 1-7.) [3] 杜百岗, 郭顺生, 彭兆, 等. 集团制造多主体外协订单任务制造资源配置[J]. 计算机集成制造系统, 2015, 21(2): 455-466. (Du B G, Guo S S, Peng Z, et al. Multi-agent manufacturing resource allocation of outsourcing order in group manufacturing[J]. Computer Integrated Manufacturing Systems, 2015, 21(2): 455-466.) [4] 周珂, 吕民, 王刚, 等. 制造任务分解与制造单元级资源配置协同优化[J]. 哈尔滨工业大学学报, 2009, 41(11): 47-52. (Zhou K, Lü M, Wang G, et al. Collaborative optimization of manufacture task decomposition and resource deployment of manufacturing unit[J]. J of Harbin Institute of technology, 2009, 41(11): 47-52. DOI:10.3321/j.issn:0367-6234.2009.11.010) [5] 王时龙, 宋文艳, 康玲, 等. 云制造环境下的制造资源优化配置研究[J]. 计算机集成制造系统, 2012, 18(7): 1396-1405. (Wang S L, Song W Y, Kang L, et al. Manufacturing resource allocation based on cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2012, 18(7): 1396-1405.) [6] 郭钢, 沈磊, 杨联星, 等. 装备类产品外协件协同制造过程及资源匹配模式[J]. 重庆大学学报, 2012, 35(5): 29-34. (Guo G, Shen L, Yang L X, et al. Resource matching mode of collaborative manufacturing process for outsourcing planning of equipment products[J]. J of Chongqing University, 2012, 35(5): 29-34.) [7] Wang J, Sun S. Multiform hybrid decision for TOC product mix optimization with extending capacity of outsourcing based on immune algorithm[J]. Acta Aeronautica Et Astronautica Sinica, 2007, 28(5): 1216-1229. [8] 王凌, 邓瑾, 王圣尧. 分布式车间调度优化算法研究综述[J]. 控制与决策, 2016, 31(1): 1-11. (Wang L, Deng J, Wang S Y. Survey on optimization algorithms for distributed shop scheduling[J]. Control and Decision, 2016, 31(1): 1-11.) [9] 刘东波, 陈玉娟, 张自强, 等. 基于第三方监理组织的虚拟企业动态监督机制[J]. 计算机集成制造系统, 2009, 15(10): 2073-2079. (Liu D B, Chen Y J, Zhang Z Q, et al. Virtual enterprise dynamic supervision mechanism based on the third supervisory organization[J]. Computer Integrated Manufacturing Systems, 2009, 15(10): 2073-2079.) [10] Liao G C, Tsao T P. Application of a fuzzy neural network combined with a chaos genetic algorithm and simulated annealing to short-term load forecasting[J]. IEEE Trans on Evolutionary Computation, 2006, 10(3): 330-340. DOI:10.1109/TEVC.2005.857075 [11] Sengül Doǧan. A new data hiding method based on chaos embedded genetic algorithm for color image[J]. Artificial Intelligence Review, 2016, 46(1): 129-143. [12] 李祥飞, 邹莉华. 基于Logistic映射的混沌优化若干理论问题分析[J]. 湖南工业大学学报, 2009, 23(3): 70-73. (Li X F, Zou L H. Analysis on theoretical issues of chaos optimization based on logistic map[J]. J of Hu'nan University of Technology, 2009, 23(3): 70-73. DOI:10.3969/j.issn.1673-9833.2009.03.018) [13] 李兵, 蒋慰孙. 混沌优化方法及其应用[J]. 控制理论与应用, 1997, 14(4): 613-615. (Li B, Jiang W S. Chaos optimization method and its application[J]. Control Theory & Applications, 1997, 14(4): 613-615.)