面向柔性作业分布式车间的分层调度模型研究

杨江波，陈友玲，曹 楠

重庆大学 机械工程学院，重庆 400044

面向柔性作业分布式车间的分层调度模型研究

杨江波，陈友玲，曹 楠

重庆大学 机械工程学院，重庆 400044

1 引言

随着当前市场环境的变化，制造业的生产模式已经开始从少品种、大批量生产转向多品种、小批量的生产，生产调度的优化作为减少企业生产成本、提高资源利用率的重要手段，一直受到国内外相关学者的广泛关注。柔性分布式车间作业系统将过去集中式的生产准备、计划和控制改为分布式，将权利下放给车间，以人为本，责权分明，使生产过程变得更加高效[1]。而随之而来的则是生产系统的调度问题变得更加复杂，因此迫切需要研究新的调度方法来解决此类调度的优化问题。

由于在实际的车间调度中，车间调度往往是分层进行的[2]，因此，如何将柔性分布式车间调度进行合理分层以求得最终决策目标的优化，是进一步研究的关键。目前国内外学者对分布式车间的调度问题研究得相对较少，Jia等[3]研究了分布式车间调度的特点，使用传统遗传算法进行求解；苏生等[4]分析了遗传算法在处理组合优化问题的局限性，提出改进遗传算法求解多车间调度问题；张晓东等[5]建立了生产计划和调度的集成优化模型，提出基于遗传算法的启发式算法进行求解；同时，已有相关学者将层次分析法应用于制造系统优化过程中，并取得了一定的成果，姚锡凡等[6]以生产计划、调度与控制集成为例，提出了基于目标级联法和IPDI原则的集成制造系统多层次优化模型；韩文民等[7]研究了单元生产环境中零部件生产工艺不相同的情况，采用分级调度算法对该问题进行研究；而黄英杰等[8]在分析了目标级联法可并行优化、级数不受限制等优点的基础上，建立了一种带层次性的车间调度模型，证明了目标级联法在处理可分层调度问题上的优越性。

本文根据柔性作业制造系统资源以及设备等分布多个车间生产的特点，提出一种基于目标级联法的分级调度模型，利用目标级联法具有分解目标的特点，结合遗传算法搜索全局最优解的能力来解决柔性分布式车间调度问题，调度过程既实现了单车间的调度时间最小，同时实现多车间的协同调度达到总体最优。

2 柔性分布式车间调度问题描述

柔性分布式车间作业系统是在成组技术基础上发展起来的一个由多个功能独立、地理位置分散的独立制造岛组成的新型生产形式[9]。柔性分布式车间系统的作业计划是在满足某些约束（如完工时间、工艺路线等）条件的基础上对零件以及操作工序的排序，按照排序分配资源和时间，使得某个决策目标最优。分布式车间作业系统的具体特点如下：

（1）每台机器可完成若干个加工操作，不同机器可加工操作不完全相同，不同机器进行相同操作所用时间也不完全相同，各机器所在的地理位置不完全相同。

（2）零件按照一定的工艺路径进行加工。

（3）每个工件的一个工序均可由一台机器单独加工完成，由于各道工序受技术上的约束，必须按某一特定顺序进行。

（4）运输成本等折合在加工成本中，运输时间加在总时间内。

（5）假设所有工件均可在调度前获得。

3 目标层解法

目标级联法简称TC法（Target Cascading），又称为ATC法（Analytical Target Cascading），1999年由美国Michigan大学的Michelena、Kim和Papalambros等人提出，是一种用于解决非集中式、层次结构协调问题的一种新方法[10]，它在消除了复杂的系统分析的同时，保证了各个子系统的并行优化，因此常被应用于解决大规划的系统优化问题。它允许结构中各层次元素自主决策，父代元素对子代元素的决策进行协调优化而获得整体最优解[11]。ATC通常包含两级：系统级和分析级；系统级负责元素目标的优化，分析级负责计算元素的反映值。局部设计变量、子代元素的反映值和参数为其输入，而传递给系统优化级的反映值为其输出。图1所示为ATC优化模型中元素Pij的原理图，父代系统将Pij的优化目标和协调变量传递下来，优化过程结束后，把响应变量和联系变量的值回传给父代系统，同时将下传给子代系统，并作为子代系统P(i+1)j的优化目标和协调变量。为输入，Rij为输出，过程如图1所示。

图1 ATC优化原理图

规划过程中，只要确定系统级的性能指标或目标值，其下层分析级的指标或目标值将由逐层转换得到。目标值的转换过程是一个由上至下层层分解的过程，该过程要求各层之间以及同层元素之间能够在一定的范围内相互协调，如果所有目标值均达到要求，那么整个系统目标就获得了优化[12]。因此，可以认为生产计划其实是一个将目标分解的过程，其目标是：在一定的条件约束下，将计划层的总体目标集进行分解，使其成为若干子目标集映射到执行层，求解得到局部目标最优，然后对求解的结果进行协调。这样，生产计划和调度的过程就演变成目标分解—子目标求解—各目标协调的迭代过程。分层调度过程如图2示。

图2 ATC分层调度过程示意图

4 柔性分布式车间分层调度模型

柔性分布式车间调度模型是围绕一批订单在N个柔性制造车间加工的任务来进行，这批订单中有M个零件要加工，订单中每个零件可以在这N个制造车间中任一个加工[13]。因为不同车间加工的环境、设备的加工性能都不一样，使得零件在不同车间中的加工时间也不同，因此，调度系统的任务就是要根据零件的加工要求以及车间机器的加工性能来确定零件的加工车间，然后在车间中根据零件的加工时间和工艺约束来规划车间内零件的最佳加工路线。调度模型的目标是订单所有零件的总加工时间最短，其中N个车间中最后完工车间的零件加工完成时间为总体的加工完成时间。

柔性分布式作业车间的分层调度是以总体调度时间最短作为总体目标，通过将生产计划层的时间分解至车间调度层再至零件规划层，先保证零件规划层所用的时间最短，将最短时间作为目标传至上层，层层之间达到最优以实现整体的调度时间最短。它主要是利用ATC可以解决复杂系统协同优化的思想以及GA能够进行全局搜索及内在的处理并行问题的能力[14]来实现调度分级后的整体最优的目标。根据ATC的分层思想，将柔性分布式车间调度问题分为三个层次：（1）生产计划层；（2）车间调度层；（3）零件规划层。其调度模型如图3所示。

4.1 生产计划层模型

不同的车间调度问题往往有不同的约束条件，本文以时间为最终决策目标。生产计划层的任务是以不同的车间为单位，通过协同调度使得各车间的加工尽可能同时完成来保证总调度时间最短，本层的目标值是柔性制造系统最终所能达到的进度，其数学模型为：

其中，式（1）表示本计划层制造系统加工完成所用的时间最短；式（2）为生产计划层的系统反映值，即加工较慢车间的进度值；式（3）表示本层的系统反应允许误差，是生产计划层给车间调度层中B1设定的系统反应，即要求的加工完成时间；是车间调度层中B1上传给生产计划层的系统反映值。式（4）表示设计变量。

4.2 车间调度层模型

车间调度层要完成零件的车间分配规划，任务是为各个零件合理分配车间以及设备，形成设备集。本层的目标是车间所有零件完工的时间最短，本层的目标值是制造系统内每个生产车间所能达到的制造进度。其数学模型为：

其中，式（5）表示本层制造车间加工完成所用的时间最短；式（6）为车间调度层的系统反映值，即加工较慢车间的进度值；式（7）表示本层每个车间加工的进度约束；是生产计划层给车间调度层中Bi设定的系统反应，即要求的加工完成时间；是车间调度层中Bi上传给生产计划层的系统反映值；式（8）为柔性制造车间的局部设计变量，表示各零件的加工路线。

4.3 零件规划层模型

零件规划层的任务是安排车间内零件加工的工艺路线，使车间中的零件能够尽快完工。本层的目标是缩短车间内每个零件的完工时间，本层的目标值是车间内的零件所能达到的制造进度。其数学模型为：

其中，式（9）表示本层车间内零件的完工时间最短；式（10）表示零件的加工进度约束；是车间调度层给零件规划层设定的完工时间，是该层零件的实际完工时间，即该零件给车间调度层的反映值。

零件的完工时间受加工路线的影响，因此零件规划层的任务是为零件选择合适的加工路线使总的完工时间最短。本文运用遗传算法，采用基于加工任务的编码方式，每个染色体由n（任务数）乘m（工艺数）个代表加工任务的基因组成，是所有操作的一个排列[15]。解码时，根据零件加工的工艺约束不同来安排加工顺序，在平衡设备负荷的同时得出完工时间最短的工艺路线，依次加工形成最终的调度方案。

5 调度流程及算法求解步骤

图3 柔性分布式车间作业分级调度模型

ATC柔性多车间调度是一种层次优化的过程，生产计划层通过设定目标值T0给车间调度层的各个车间设定同时完工策略，车间调度层给零件规划层的各零件设定最小完工时间，在零件规划层的优化程序完成后，获得的最小完工时间回传给车间调度层，车间调度层再将各车间的完工时间回传给生产计划层，这样进行不断迭代，每次迭代下层最优的值将作为新目标，直到最后获得最优解。

基于ATC的柔性分布式车间调度流程如图4所示，调度算法主要步骤如下：

为了方便叙述，做如下规定：

循环次数为CN；生产计划层的进化代数为VN；X0A为生产计划层的决定变量；X0B为车间调度层决定变量；其他出现的符号同前面所提到的含义一致。

（1）预先设定生产计划层、车间调度层、零件规划层的允许误差值 ε0、ε1、ε2，车间调度层传给生产计划层的响应值及零件规划层传递给车间调度层的响应值同时设定生产计划层的循环次数CN和车间调度层的进化代数VN。

（2）在生产计划层内，根据各车间中零件批量、进度完成快慢的不同情况，设定 X0A（生产计划层决定变量），X0B（车间调度层决定变量）。

（3）在车间调度层内，根据零件的工艺路线及零件在各类机器上的加工时间来初始分配各类加工设备，形成加工设备集，并用基因谱来描述。

（4）在零件规划层内，生产车间随机产生n个个体作为初始染色体种群，染色体的位数由车间内零件的种类数和设备的类型数来决定。

（5）根据零件的种类数和车间内的设备类型数，以尽早完工为准则，对基因进行解码，计算每个个体的完工时间，将最小的完工时间作为本车间零件层的反应值，判断零件规划层的响应值与进度值之差是否小于给定的误差或者判断循环次数是否大于给定的循环次数，如果是，则取之为最大值。

图4 基于ATC的柔性分布式车间调度流程图

（6）如果不是，则判断零件规划层的某零件的完成时间是否大于给定的响应值，如果是则返回（4）；如果不是则将最大、最小值所在的生产车间内零件的染色体进行交叉操作同时将R重新排列并与R最大的单元的染色体进行交叉，完成遗传操作后重新解码。

（7）如果（5）成立，判断车间调度层的完工时间与进度值之差是否满足要求或者判断循环次数是否大于给定的循环次数，如果是则取R为最大值；如果不是，则判断遗传操作是否全部完成或者判断迭代次数是否大于给定的次数，如果是则取R为最大值。如果不是则返回（6）。

（8）如果（7）成立，判断生产计划层的完工时间与进度值之差是否满足要求或者判断迭代次数是否大于给定的次数，如果是则输出结果，如果不是则返回（6）。

6 实例分析

本文以三个柔性车间的协同调度来说明实际调度过程。假定在A、B、C三个车间各有5台机器，分别编号为A1，A2，A3，A4，A5，B1，B2，B3，B4，B5，C1，C2，C3，C4，C5。现在有一批包括 9个零件的订单要加工，其加工时间分别如表1所示。

设定算法初始参数如下：最大迭代次数CN为200，进化次数VN取为100，初始种群规模n为100，交叉概率为0.85。生产计划层的系统允许反应误差ε0为1.0，车间调度层的系统允许反应误差ε1为0.6，零件规划层的系统允许反应误差ε2取为0.2。经算法优化后，得到的加工完成时间分别为A车间9 min，B车间10 min，C车间9 min，可知调度结果，调度系统完成这批9个零件的订单需要花费最小时间为10 min。生产计划层的染色体为[3322231121]，代表零件7，8和10在A车间中加工；零件3，4，5和9在B车间中加工；零件1，2和6在C车间加工。图5所示为A车间的甘特图，图6所示为B车间的甘特图，图7所示为C车间的甘特图，图中横坐标为加工时间，纵坐标为机场类型，而图中间的数字表示加工的零件，并且依照时间从左向右的顺序依次表示零件的1～3个工序，比如零件7的第一道工序在车间A的机器A4上进行，第二道工序在机器A3上进行，第三道工序在机器A4上进行，调度甘特图如图6。

表1 零件的工序及在三个车间的加工时间表 min

图5 A车间的调度甘特图

图6 B车间的调度甘特图

图7 C车间的调度甘特图

由图5～7中可以看出：本文提出的柔性作业车间调度模型能很好地求解相关调度的优化问题，在调度中既能把零件合理地分配到合适的车间加工以谋求总体最优的加工时间，又能很好地规划零件的加工路径。

7 结论

（1）本文根据柔性分布式车间制造系统在多个车间一起进行加工的特点以及目标级联法在解决分层调度问题上的优越性，提出一种分级调度模型，以3个车间的调度结果说明了该模型的有效性。

（2）该方法能够根据加工时间和加工数量动态，合理分配机器数量和工件的加工路径，在优化过程中如果采用改进的遗传算法代替传统遗传算法，能够得到更好的优化效果。

[1]杨敬松，崔广才.基于混合遗传算法的分布式车间作业调度问题[J].长春理工大学学报，2005，28（3）：19-22.

[2]黄英杰，姚锡凡.基于目标级联法的作业车间调度[J].华南理工大学学报，2010，38（6）：128-132.

[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.

[5]张晓东，严洪森.多级车间生产计划和调度的集成优QL[J].机械工程学报，2005，4l（9）：98-105.

[6]姚锡凡，帅旗，谭伟，等.基于目标级联法和IPDI原则的制造系统建模与优化策略[J].南京理工大学学报：自然科学版，2009：257-262.

[7]韩文民，田丽丽，陈娟.基于目标级联法的动态零件族跨单元生产的单元调度研究[J].机械设计与制造，2012（10）：113-115.

[8]黄英杰，姚锡凡.基于目标级联法和粒子群算法的柔性分布式车间调度[J].中南大学学报，2012，43（1）：151-158.

[9]杨敬松，夏秀峰，崔广才.混合遗传算法在分布式车间作业调度中的应用[J].计算机工程与应用，2005，41（19）：213-215.

[10]Miehelena N，Kim H M，Papalambros P Y.A system partitioning and optimization approach to target cascading[C]// Proc 12th Int Conf on Eng Design，Munich，1999，2：1109-1112.

[11]赵刚，江平宇.面向大规模定制生产的e-制造单元层解分析优化规划模型[J].机械工程学报，2007，43（2）：178-185.

[12]曹楠，陈友玲.基于ATC和GA的可重构制造单元分级调度研究[J].计算机应用研究，2011，28（12）：4467-4470.

[13]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，2005，127（2）：206-214.

[14]Moon C，Seo Y.Evolutionary algorithm for advanced process planning and scheduling in a multi-plan[J].Computers&Industrial Engineering，2005，48（2）：311-325.

[15]田颖，江平宇，周光辉.基于遗传算法的工艺规划与调度集成方法[J].西安交通大学学报，2006，40（9）：1041-1044.

YANG Jiangbo,CHEN Youling,CAO Nan

School of Mechanical Engineering,Chongqing University,Chongqing 400044,China

Aiming at the workshop distributed manufacturing system scheduling optimization problems,combined with the actual production situation,a hierarchical scheduling model based on analytical target cascading and genetic algorithms is proposed.The model divides the scheduling process into three parts:the planning layer,the workshop scheduling layer and the job planning layer,the whole time minimal as its target is divided into various levels,to achieve the overall optimal scheduling time.Taking a three job-shop system as an example to verify the proposed model could be used in jobs allocation and program the path of each job.

multi distributed manufacturing system;analytical target cascading;hierarchical scheduling;genetic algorithm

针对多车间分布式制造系统调度优化问题，结合车间实际生产情况，提出一种基于目标级联法和遗传算法的层次调度模型。模型将生产调度过程划分为生产计划层、车间调度层和零件规划层，并将整体时间最短的优化目标划分到各个层次，通过层层优化达到时间最优后反馈至上层，以实现整体调度时间最优。以3个制造车间协调调度问题为例，验证了该模型在零件分配和零件的工艺路线选择上的合理性和有效性。

多层分布式制造系统；目标级联法；分层调度；遗传算法

A

TP391

10.3778/j.issn.1002-8331.1301-0169

YANG Jiangbo,CHEN Youling,CAO Nan.Research on grading scheduling model of flexible job distributed workshop.Computer Engineering and Applications,2014,50（23）：239-244.

国家自然科学基金（No.71271224）。

杨江波（1988—），男，硕士研究生，主要研究方向为生产调度、生产管理；陈友玲（1964—），女，博士，教授，硕导，主要研究方向为生产计划与调度、生产系统建模与仿真；曹楠（1987—），女，硕士研究生，主要研究方向为生产调度、生产管理。E-mail：15025471015@163.com

2013-01-15

2013-04-15

1002-8331（2014）23-0239-06

CNKI网络优先出版：2013-05-03,http://www.cnki.net/kcms/detail/11.2127.TP.20130503.1707.003.html