基于目标级联法和粒子群算法的柔性分布式车间调度
黄英杰，姚锡凡
(华南理工大学 机械与汽车工程学院，广东 广州，510640)
摘要：针对传统的单车间调度优化不能满足分布式车间调度优化的需求，提出一种基于目标级联法和粒子群算法的层次化柔性分布式车间调度优化模型，其中的生产计划层负责零件的分配，车间调度层负责零件加工路线的规划。以2个柔性制造车间组成的调度优化问题为例，验证该调度模型的有效性。研究结果表明：所提出的模型在将加工零件合理地分配到适当车间的同时，实现了零件加工路径的规划，从而为解决柔性分布式车间调度优化问题提供一种有效方法。
关键词：目标级联法；分布式车间计划与调度；粒子群算法
中图分类号：TH165 文献标志码：A 文章编号：1672-7207(2012)01-0151-08
Planning and scheduling of multiple flexible-shops based on analytical target cascading and particle swarm optimization
HUANG Ying-jie, YAO Xi-fan
(School of Mechanical and Automotive Engineering, South China University of Technology, Guangzhou 510640, China)
Abstract: Because the traditional scheduling model of single job-shop can not meet the requirements of distributed scheduling systems of multiple job-shops, a planning and scheduling model of multiple job-shops based on analytical target cascading and particle swarm optimization was established, where the planning layer was responsible for distributing jobs to each workshop, and the workshop scheduling layer was responsible for planning job operations in each workshop. Take a two job-shop system as an illustrated example to verify the proposed model. The results show that distributed scheduling problems of multiple flexible-shops can be solved effectively, and jobs can be distributed to the workshops rationally, and meanwhile job schedule in each workshop is realized.
Key words: analytical target cascading; multiple shops planning and scheduling; particle swarm optimization
生产计划的制定是合理利用企业资源和最大限度满足客户需求的关键，生产调度是显著减少产品生产等待时间和总时间、显著提高设备利用率的重要手段，因此，生产调度的优化问题一直是研究的热点。在现有生产调度的研究中主要针对单车间生产环境[1-2]，对于柔性分布式车间的生产调度问题研究比较少，在柔性分布式车间的调度系统中，由于生产资源异地分布，生产设备分布在不同的工厂或车间，而且制造信息具有分布性和非预见性等，使得现有的生产调度机制、方法与策略难于产生理想的效果，因此，迫切需要新的调度方法和调度机制来解决这类柔性分布式车间调度优化问题。目前只有少数研究者研究过分布式车间调度的问题，如：Jia[3]用遗传算法求解分布式车间调度问题；苏生等[4]用改进的遗传算法求解多车间计划与调度问题；张晓东等[5]用基于遗传进化的启发式算法求解多级车间生产计划与调度问题。目标级联法 (TC)又称为目标级联分析法(ATC)，是最近提出的解决非集中式、层次结构协调问题的一种新方法[6]，它允许层次结构中各元素自主决策，父代元素对子代元素的决策进行协调优化，从而获得问题的整体最优解；与其他优化方法相比，具有可并行优化、级数不受限制和经过严格的收敛证明[7]等优点，因此，常用于解决复杂系统优化问题[8-9]。粒子群算法是由Kennedy和Eberhart提出的一种源于对鸟群捕食行为模拟的新的进化计算方法，因具有个体数目少、计算简单、鲁棒性好等特点[10-13]而在JSP(Job-shop scheduling problem)类的组合优化问题中获得了成功应用。在此，本文作者通过ATC方法和粒子群算法来解决柔性分布式车间调度问题，以实现多层次柔性车间调度系统的整体最优化。
1 目标级联法
目标级联法是Kim等[6, 14-15]提出的一种解决复杂系统中目标优化问题的新方法，其特征如下：首先是目标级联，即系统中的父级系统为子系统设置目标并将目标传递给子系统；其次，子系统都有一个分析模块计算子系统的响应；同时，继承了协同优化方法的最小化设计问题中协调子系统之间的偏差来达到子系统之间一致性的思想。在协同优化中，每一级子系统在设计优化时暂时不考虑同级子系统之间的联系而独立进行优化，优化目标是使该子系统设计优化结果与上一级系统优化提供的目标差异最小，各个子系统设计优化结果的不一致性通过上一级系统优化来协调。
ATC是基于模块的、层次性的优化方法。ATC模型中包括2类模块：优化设计模块和分析模块。优化设计模块负责元素目标的优化；分析模块用于计算元素的反应，局部设计变量、参数和子代元素的反应为其输入，而传递给优化设计模块的反应为其输出。图1所示是ATC优化模型中元素Pij的原理图[6]。Pij的优化目标
和联系变量
由父代系统传递下来，Pij的优化问题结束后，将响应
和联系变量的值
回传给父代系统；同时，将
和
下传给子代系统，并作为子代系统
的优化目标和联系变量。其中：
，
和
为分析模块的输入，
为分析模块的输出。
ATC模型中，元素Pij的数学模型[6-7]表述如下。
min：
s.t. 
式中：
为Pij的局部设计变量；为Pij的联系变量；为父代系统为本级系统设定的联系变量；为本级系统为子代系统设定的联系变量；
为子代系统传回本级系统的联系变量；为
的反应值；为父代系统为本级系统设定的反应值；
为本级系统为子代系统设定的反应值；
为子代系统回传本级系统的反应值；
和
分别为本级系统和子代系统反应偏差的权重系数；
和
分别为本级系统和子系统联系变量偏差的权重系数；
和
分别为反应和联系变量的偏差容量；
；
为Pij子代问题的个数；Sij为二进制选择矩阵；gij和hij分别为不等式约束和等式约束。
图1 ATC优化模型Pij的原理图
Fig.1 Schematic diagram of ATC optimization model
2 基于ATC的层次化调度模型与编码
基于ATC的柔性分布式车间调度模型围绕着一批订单在N个柔性制造车间加工的任务来进行。这批订单中有多个工件要加工，订单中的每个零件在这N个制造车间中任一个加工。由于各个车间中加工设备的性能不同，导致零件在各个车间中的加工时间不一样，所以，调度系统首先的任务是根据制造车间的设备性能和零件的加工要求条件来确定零件的加工车间，然后在各个加工车间中根据本车间加工工件的工艺约束和加工时间来规划车间内各类零件的加工路线。调度模型的目的是使整批订单所有零件的总加工时间最短，其中N个加工车间中最后加工的车间零件加工完成时间为总体的加工完成时间。
图2 基于ATC的柔性多车间调度模型
Fig.2 Scheduling model of multi-shop based on ATC
根据ATC的设计思想，柔性分布式车间调度模型分为生产计划层和车间调度层，生产计划层的任务是负责零件的分发，车间调度层的任务是完成零件加工路线的规划。以图2所示的2个制造车间的调度为例，说明柔性分布式车间调度的优化模型。
2.1 生产计划层的模型与编码
生产计划层的任务是为各个车间合理地分配加工零件，使各制造单元的加工尽可能同时完成。本层的目标是加工完所有零件的时间最短，为了简便，在优化中偏差权重系数取1，二进制选择矩阵系数Sij取为0，其数学模型为：
min
w.r.t.(
,
,
,
)
s.t. 
式中：
为生产计划层的系统反应值，等于加工较慢车间零件的进度值；T0A为系统的总目标值。柔性多车间的调度任务是尽可能缩短所有零件的加工时间，因此，总目标值T0A取为0；为生产计划层的反应允许误差，为使本层的总目标值最小化，直接取为反应偏差值的平方和，即等于
；为生产计划层为车间调度层中B1设定的系统反应，即要求的加工完成时间；
为车间调度层中B1上传给生产计划层的系统反应值。同样，为生产计划层为车间调度层中B2设定的系统反应，
为车间调度层中B2上传给生产计划层的系统反应值；x0A为本层的设计变量，在实验中用位置向量来表示，
为所有零件的集合。
设计变量x0A采用这样的编码方法：用1个P维(订单中零件数)的向量Xworkshop[P]来表示位置，位置向量中的每一位代表每个零件加工的车间ID号。比如位置向量为[2 1 2 3 2 3 1 3 2 3]，则表示该订单中有10个零件要加工，有3个加工车间，第1个零件在车间2中加工，第2个零件在车间1中加工，第3个零件在车间2中加工，依此类推，第10个零件在车间3中加工。
由于粒子群算法是连续空间的算法，而车间编号是整数，因此，位置向量在迭代过程中做些修改：若按照位置向量公式计算出来的是小数，则采取向下取整的办法进行修正，而且车间向量的取值为[1, p]区间的整数；若计算出的结果超出取值区间，则按照边界取值。在优化中适配值函数为总目标函数的倒数。
2.2 柔性车间调度层模型与编码
柔性车间调度层的任务是完成柔性制造车间内各零件的加工工艺路线规划，使柔性制造车间中的零件尽快加工完成。本层的目标是尽可能缩短各柔性制造车间所有加工零件完成时间与生产计划层给定的完成数学模型为：
min
w.r.t.(
)
式中：
为
柔性制造车间中最后零件的加工完成时间；
为生产计划层为该柔性制造车间设定的反应值；
为柔性制造车间的局部设计变量，表示各零件的加工路径，实验中用位置向量来表示。
这里用1个2L维(
，为总工序数)的向量来表示此位置向量。实际上，这个位置向量由2个L维的向量组成，即工序向量Xprocess[L]和机器向量Xmachine[L]组成。工序向量Xprocess[L]由L个非零且不大于n (工件数)的自然数组成，自然数的顺序决定了工件工序的加工顺序。本文用基于操作的编码方法，即每个工序向量用L个代表操作的位组成，是所有操作的一个排列。例如工序向量Xprocess[L]为[2 1 1 2 2 3 1 3 3]，则其中的1表示工件1，2表示工件2，3表示工件3；第1次出现的1代表工件1的第1道工序, 第2次出现的1代表工件1的第2道工序,第3次出现的1代表工件1的第3道工序，工件2和工件3编码与此类同。机器向量Xmachine[L]由L个非0且不大于m(机器数)的自然数组成，代表加工Xprocess[L]对应位置工序的机器号。
由于粒子群算法是连续空间的优化算法，而柔性作业车间调度问题是离散的非数值优化问题，因此，在迭代计算过程中进行如下修改：
(1) 对于Xmachine[L]，由于机器向量的取值为[1, m]区间的整数，若按照位置公式计算出来的是小数，则采取向下取整的办法进行修正；若按照位置公式计算出的结果超出取值区间，则按照边界取值。
(2)对于Xprocess[L]，由于柔性车间调度优化问题为工序顺序的排序问题，因此，采用以下方法进行迭代运算。如经过某次迭代运算得到如下结果：
将计算后的数值按照由小到大进行排序，并按照此排序，将与计算后的值所对应的初始值重新排列，得到如下结果：
则这次迭代过后的结果为[1 2 1 1 3 2 3 3 2]，经过这样的转化就可以得到一个满足要求的可行解。
3 ATC柔性多车间调度的流程
基于ATC柔性分布式车间调度模型是一种层次优化模型。在ATC的优化过程中，生产计划层不断给车间调度层的各车间设定最小加工完成时间，在车间调度层的各制造车间优化完成后，获得的最小加工完成时间传递回生产计划层，这样进行不断迭代，最后获得最优解。基于ATC的柔性分布式车间调度流程如图3所示，具体步骤如下。
第1步：预先设定生产计划层的种群数NPopsize和车间调度层各车间的种群数NPopsize1以及生产计划层和车间调度层粒子群优化算法的各项参数，并设定生产计划层的迭代次数NMaxEvolve和车间调度层的进化代数NMaxEvolve1。
第2步：在生产计划层内，随机取NPopsize个
和
，由和
计算生产计划层的反应值
，并分别把反应值和作为2个车间的给定值传递给车间调度层。随机取NPopsize个，分别根据进行解码，把订单中的零件分配到2个加工车间。
第3步：在各个制造车间内，对于生产计划层的每个粒子，随机产生NPopsize个工序向量Xprocess[L]和机器向量XMachine[M]作为初始种群，工序向量和机器向量的位数由分配到车间内零件的个数来决定。对于每个粒子，根据粒子群算法的速度计算公式计算各粒子的工序速度vProcess[L]和机器速度vMachine[M]，根据算法的位置计算公式更新各粒子的工序向量XProcess[L]和机器向量XMachine[M]，并解码求出各个粒子的加工完成时间，以最小化车间调度层的目标函数
而不断地进行迭代优化，直到迭代次数大于给定值NMaxEvolve1为止，把每个最优解的反应值
传递回生产计划层。
第4步：在生产计划层内，分别用NPopsize个制造车间传递回的反应值和
，计算反应偏差的平方和
，令
等于，计算总目标
，并保留总目标最小的，x0A和。用粒子群算法的速度计算公式计算速度向量vworkshop[P]，的速度和的速度，用算法的位置计算公式更新位置向量Xworkshop[P]，和。判断迭代次数是否大于第1步给定的生产计划层最大迭代次数NMaxEvolve，若小于NMaxEvolve，则解码x0A，并返回第3步；若大于NMaxEvolve，则进入下一步。
图3 ATC车间调度的流程
Fig.3 Flow chart of ATC-based multi-shop scheduling
第5步：把总目标最小时保留的作为最短的加工完成时间输出，以保留的和经解码分别作为零件在各制造车间中的最优分配方案和各零件的最优加工路线，结束优化。
4 算例分析
以3个柔性车间的调度优化为例说明柔性分布式车间调度模型。在车间1中有5台机器，分别称为A，B，C，D和E；在车间2中也有5台机器，分别称为F，G，H，I和J；在车间3中也有5台机器，分别称为K，L，M，N和O。有一批包括13个零件的订单要加工，其加工时间如表1所示。
表1 订单中的零件加工时间
Table 1 Process jobs in order form
生产计划层的最大迭代次数NMaxEvolve为30，初始种群规模N为50，粒子群算法最大惯性系数ω1为0.9，最小惯性系数ω2为0.3，c1和c2都为2.0；车间调度层的最大迭代次数NMaxEvolve1为50，初始种群规模N1为100，粒子群算法参数ω1为0.9，ω2为0.3，c1和c2都为2.0。经优化后求得加工完成时间为12，生产计划层的染色体为 [3 3 3 2 2 2 3 1 1 1 1 2 1]，代表性零件8，9，10，11和13在车间1中加工；零件4，5，6和12在车间2中加工；零件1，2，3和7在车间3中加工。图4所示为车间1的甘特图，图5所示为车间2的甘特图，图6所示为车间3的甘特图。在甘特图中横坐标为加工时间，纵坐标为机床类型，甘特图中间的数字为加工的工件类型。按照时间顺序依次表示工件的1~3个工序，比如工件类型10的第1工序在机床A中加工，第2工序在机床B中加工，第3工序在机床D中加工；工件类型8的第1工序在机床E中加工，第2工序在机床B中加工，第3工序在机床D中加工。其他工序依此类似。由图4~6可以看出：本文提出的柔性分布式车间调度模型能很好地用于求解柔性分布式车间调度的优化问题，在调度中既能把零件合理地分配到合适的车间加工，又能很好地规划零件的加工路径。
图4 车间1的甘特图
Fig.4 Gantt chart for first shop
图5 车间2的甘特图
Fig.5 Gantt chart for second shop
图6 车间3的甘特图
Fig.6 Gantt chart for third shop
5 结论
(1) 建立了一种基于目标级联法和粒子群算法的柔性分布式车间调度模型，并以2个柔性制造车间的调度优化为例，验证该调度优化模型的有效性，为解决柔性分布式车间调度优化问题提供了一种有效而又实用的方法。
(2) 该方法能够在分布式制造系统中合理地分配加工零件和规划零件的加工路径。在优化中如果用混合粒子群算法代替粒子群算法，可以获得更好的优化效果，但优化时间将变长。
参考文献：
[1] 陈耀军, 姚锡凡, 张庆. 一种用于车间调度的基于熵的混合遗传算法[J]. 华南理工大学学报: 自然科学版, 2009, 37(9): 112-116.
CHEN Yao-jun, YAO Xi-fan, ZHANG Qing. A hybrid genetic algorithm based on entropy for job-shop scheduling[J]. Journal of South China University of Technology: Natural Science Edition, 2009, 37(9): 112-116.
[2] Gaafer L K. Genetic algorithms and simulated annealing for scheduling in agile manufacturing[J]. International Journal of Production Research, 2005, 43(14): 3069-3085.
[3] Jia H Z. A modified genetic algorithm for distributed scheduling problems[J]. Journal of Intelligent Manufacturing, 2003(14): 351-362.
[4] 苏生, 战德臣. 多工厂生产计划与调度优化模型与求解算法[D]. 哈尔滨: 哈尔滨工业大学计算机科学与技术学院, 2007: 1-176.
SU Sheng, ZHAN De-cheng. Optimization models and algorithm for production planning and scheduling of multiple plants[D]. Harbin: Harbin Institute of Technology, School of Computer Science and Technology, 2007: 1-176.
[5] 张晓东, 严洪森. 多级车间生产计划和调度的集成优化[J]. 机械工程学报, 2005, 41(9): 98-105.
ZHAN Xiao-dong, YAN Hong-sen. Integrated optimization of production planning and scheduling for multi-stage workshop[J]. Chinese Journal of Mechanical Engineering, 2005, 41(9): 98-105.
[6] Kim H M. Target cascading in optimal system design[D]. University of Michigan, Ann Arbor, 2001: 1-145.
[7] Kim H M. Lagrangian coordination for enhancing the convergence of analytical target cascading[J]. AIAA Journal, 2006, 44(10): 2197-2207.
[8] 凌六一, 梁樑. 基于ATC的供应链优化设计[D]. 合肥: 中国科学技术大学管理科学与工程, 2007: 10-30.
LING Liu-yi, LIANG Liang. Optimization design of supply chain based analytical target cascading[D]. Hefei: University of Science and Technology of China, Management Science and Engineering, 2007: 10-30.
[9] 赵刚, 江平宇. 面向大规模定制生产的e-制造单元目标层解分析优化规划模型[J]. 机械工程学报, 2007, 43(2): 178-185.
ZHAO Gang, JIANG Ping-yu. Analytical target cascading based synergistic cell formation model in E-manufacturing system for mass customization[J]. Chinese Journal of Mechanical Engineer -ing,2007, 43(2): 178-185.
[10] 贾兆红, 陈华平, 孙耀晖. 混合粒子群算法在柔性工作车间调度中的应用[J]. 系统仿真学报, 2007, 19(20): 43-47.
JIA Shao-hong, CHEN Hua-ping, SUN Yao-hui. Hybrid particle swarm optimization for flexible job-shop Scheduling[J]. Journal of System Simulation, 2007, 19(20): 43-47.
[11] 谷峰, 陈华平, 卢冰原, 等. 粒子群算法在柔性工作车间调度中的应用[J]. 系统工程, 2005, 23(9): 20-23.
GU Feng, CHEN Hua-ping, LU Bing-yuan, et al. Particle swarm optimization for flexible job shop scheduling[J]. Systems Engineering, 2005, 23(9): 20-23.
[12] 刘鑫朝, 颜宏文. 一种改进的粒子群优化RBF网络学习算法[J]. 计算机技术与发展, 2006, 16(2): 185-187.
LIU Xin-chao, YAN Hong-wen. A RBF neural network learning algorithm based on improved PSO[J]. Computer Technology and Development, 2006, 16(2): 185-187.
[13] 刘林. 一类离散制造业生产过程中的优化问题研究[D]. 合肥: 合肥工业大学管理学院, 2009: 1-115.
LIU Lin. Research on optimization problem of manufacturing process in a discrete manufacturing industry[D]. Hefei: Hefei University of Technology. School of Management, 2009: 1-115.
[14] Kim H M, Michelean N F, Papalambros P Y. Target cascading in optimal system design[J]. Journal of Mechanical Design, Transactions of the ASME, 2003, 125(3): 474-480.
[15] Michalek J J, Papalambros P Y. An efficient weighting update method to achieve acceptable consistency deviation in analytical target cascading[J]. Journal of Mechanical Design, Transactions of the ASME, 2005, 127(3): 206-214.
(编辑 陈灿华)
收稿日期：2011-05-15；修回日期：2011-07-28
基金项目：国家高技术研究发展计划(“863”计划)项目(2007AA04Z111)；国家自然科学基金资助项目(51175187)
通信作者：黄英杰(1977-)，男，广东梅州人，博士研究生，从事制造系统优化和人工智能的研究；电话：15989184129；E-mail: huangyingjiehyj@163.com
