基于细胞自动机的大尺度制造4D调度模型

陈　勇,羊笑笑,王　成,王亚良

(浙江工业大学 特种装备制造与先进加工技术教育部重点实验室，浙江 杭州 310014)

基于细胞自动机的大尺度制造4D调度模型

陈勇,羊笑笑,王成,王亚良

(浙江工业大学 特种装备制造与先进加工技术教育部重点实验室，浙江 杭州 310014)

摘要：针对大型装备生产过程中空间、时间和设备资源冲突问题，提出了基于细胞自动机的大尺度4D调度模型.用生产场地长、宽、零部件加工时间和设备资源四个维度构建4D调度概念.在时间维度上设定分割点划分三维时空从而获得有限个三维划分层.在三维划分层上建立基于规则的二维空间调度模型和基于层次遗传算法的设备调度模型.层布局细胞和设备资源调度细胞通过自组织演化规则相互作用构成动态调度系统的演化，建立4D调度细胞自动机模型.通过实例演算验证模型和算法的正确性和有效性。

关键词：大尺度制造;4D调度;设备调度;细胞机;层次遗传算法

4D Scheduling model for large-scale equipment manufacturing

based on cellular automata

CHEN Yong, YANG Xiaoxiao, WANG Cheng, WANG Yaliang

(Key Laboratory of Special Purpose Equipment and Advanced Processing Technology, Ministry of

Education, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:To resolve the conflict of the space, time and equipment resource in large-scale equipment manufacturing, a 4D scheduling model based on cellular automata was proposed. Taking length, breadth of the yard, processing time and equipment capabilities as four dimensions, the concept of 4D scheduling was imported. After dividing the three-dimensional workplace into layers, two-dimensional spatial scheduling and equipment scheduling based on hierarchical genetic algorithm in one layer was modeled. 4D scheduling model with layer spatial scheduling cells and equipment scheduling cells influencing each other by local self-evolution rules was built based on cellular automata. Example test was performed to validate the correctness and effectiveness of the 4D scheduling modeling。

Keywords:large-scale equipment manufacture; 4D scheduling; equipment scheduling; cellular automata; hierarchical genetic algorithm

大型装备产品通常涉及船舶、航天和大型专用设备等，制造过程复杂而独特，通常具有以下特点：1)采用定位生产；2)零件种类多达数万种且工艺多样；3)工序加工时间长，加工设备非唯一并且选择不同加工设备所需加工时间不同；4)在制品尺寸很大，生产过程中空间场地受限明显；5)物流设备无法及时响应搬运需求.在大型装备生产过程中资源冲突明显，将发生资源冲突的订单进行优先排序，实现有限资源的合理分配.基于地理空间概念，将此类调度新问题定义为“大尺度制造调度”问题。

目前国内外关于大尺度调度问题的研究主要集中在考虑作业顺序约束和空间约束的空间调度问题，以及考虑作业顺序约束和共享资源约束的生产调度问题，而将两者综合考虑的调度研究很少.文献[1-2]运用运筹学求解空间调度问题，其复杂性和NP-hard特性使数学模型变量多，约束多，优化求解的难度大，耗时长；文献[3-4]采用经典的基于调度规则的算法求解空间调度问题，该方法需要特定的调度经验和特殊环境支持，寻优效率低且无法阐述所得解同最优解的近似程度；文献[5-6]采用的智能优化算法具有鲁棒性强、通用性强等特点，在空间调度领域应用广泛；文献[7]中细胞机技术很好地模拟大型装备空间调度的复杂性和柔性.笔者在三维空间调度基础上构建4D调度概念，建立基于细胞机的4D调度模型，以期为一定优化目标下大型装备制造企业生产调度提供有效的分析方法与工具。

14D调度细胞机模型建立

1.1模型抽象

部件在工作平台上的放置位置、开工时间和加工时间等受交货期约束、工序约束、空间约束以及设备资源约束等.空间调度涉及第一、第二维度场地二维平面，以及零部件加工时间.设备调度涉及第一、第二维度场地二维平面，零部件加工时间以及设备.由于调度目标存在冲突，两者需通过博弈达到平衡构建4D调度.如图1所示。

图1　4D调度概念Fig.1　4D schduling definition

用三维空间调度的3个关键属性(场地长、宽和时间)构造三维时空.以三维时空资源为对象，物流设备调度周期为划分点，在时间维度上对其进行层划分，如图2所示.该划分方式使每层所需调度的部件集合稳定，由此三维空间调度问题转换为有限个二维的布局问题。

图2　层划分Fig.2　Layers division

大尺度制造4D调度元胞机二维网格系统共有2行n列，n为三维空间的划分层数，如图3所示.每一个网格代表一个元胞，第一行代表每一层所对应的层布局元胞，第二行代表每一层所对应的设备资源调度元胞。

图3　元胞机网络结构Fig.3　Network structure of the cellular automata

图4　模型演化Fig.4　Model evolution

1.2细胞状态

层布局细胞的邻域是该层内所布置部件在时间维度上直接影响的层的布局方案以及该层的设备资源调度方案.只有该层及其邻域层布局成功，且该层内设备资源调度成功时，该层的布局才算成功.某层内设备资源调度细胞的邻域是其对应的层布局细胞.只有当该层设备调度成功且该层布置成功时，该层的设备调度才算成功。

层布局细胞t时刻的状态属性表示为

其中：Bi为第i层待布置部件编号的集合；R1为对应部件时间规则r1的集合，r1∈{0,1}，0表示先到先服务规则，1表示非先到先服务规则；R2为对应部件形状简化规则r2的集合，r2∈{0,1}，0表示矩形规则，1表示非矩形规则；R3为对应部件布置策略规则r3的集合，r3∈{0,1}，0表示边规则，1表示最大剩余空间规则；Db为对应部件决策变量db的集合，db∈{0,1}，0表示部件布置成功，1表示布置失败。

层内设备资源调度细胞t时刻的状态属性表现为

其中：Oi,j为第i层已布置部件bi,j在该层内的工序集合；R4为对应部件定位规则r4的集合，r4∈{0,1}，0表示非相似工序分散布置规则，1表示相似工序分散布置规则；R5为对应搬运工序时间规则r5的集合，r5∈{0,1}，0表示工序在该层完成，1表示工序推迟到下一层完成；R6为对应加工工序时间规则r6的集合，r6∈{0,1}，0表示工序在该层完成，1表示将工序分成前后两部分，后一部分推迟到下一层完成；Do为是对应工序决策变量do的集合，do∈{0,1}，0表示工序完工，1表示工序未完工。

层布局细胞初始条件设置如下：初始状态下时间规则设置为先到先服务规则，部件简化规则设置为矩形规则，定位规则设置为边策略.相似工序分散布置使设备资源调度难度增加，因此某层内设备资源调度细胞初始规则为选取非相似工序分散布置.边界条件为定值型，即当所有部件决策变量以及工序决策变量都取0值。

1.3演化规则

当细胞及其邻域的决策变量db，do任意一值非零时，其对应的db，do为非零的部件或工序的属性值需要调整，直至细胞及其邻域中的决策变量都取0，且下一时刻的细胞中的决策变量db，do都取0.此时各个集合状态属性保持不变，状态稳定。

1.4评价函数

模型多目标函数为

EI=αEI1+β(1-EI2)+γ(1-EI3)

(1)

式中：α,β,γ为评价系数；EI1为任务延迟指标；EI2为时空利用率指标；EI3为设备利用率指标，且有

(2)

式中：Cmax为企业在部件制造上所能承受的最大成本；Db为制作完成时间延迟和进行外协制作的部件数目；C1为每个部件的延迟成本，同理：

(3)

式中：Sbi为部件i的占地面积；tbi为部件i的制作周期；Sp为场地的可用面积；T为布置解在时间上的宽度；C2为实际时空利用率每降低一个百分点所带来的成本，同理：

(4)

式中：tn为每台设备用于改性任务和运输任务的时间；to为每台设备的开动时间；C3为指实际设备有效利用率每降低一个百分点所带来的成本。

2层模型建立

2.1层布局

2.2层内设备资源调度

2.2.1数学模型

Obj.minmax(tei,j,k)

(5)

(6)

∑l∈Ei,j,kei,j,k,l=1

(7)

(8)

tsi,j,k+1≥tei,j,k

(9)

tei,j,k=ti,j,k+tsi,j,k

(10)

(11)

ti,j,k=Δtl∀oi,j,k∈ER∪EX

(12)

模型中：式(5)表示最小化最大完工时间；式(6，7)表示每道工序占用一台可用设备；式(8)表示设备加工完当前部件后才能加工下一部件；式(9)表示部件工序约束；式(10，11)表示部件当前工序有效完工时间是有效开始与有效处理时间之和.式(12)表示搬运工序的有效处理时间为搬运延迟时间。

将xy平面网格化处理，使每小格长Δy等于宽Δx.普通物流设备运行速率为vg.有效与实际时间的关系如图5所示，其计算式为

图5　普通物流设备作业有效与实际时间关系图Fig.5　The relation between effective and real operation time of general logistics equipment

(13)

(14)

(15)

(16)

tsi,j,k=tei,j,k-1

(17)

(18)

(19)

式(13~19)均需满足ei,j,k,l=1，∀l∈P.式(13，14)分别定义普通物流设备搬入、搬出工序实际处理时间.式(15，16)定义普通运输工序有效处理时间；式(17)定义普通物流设备有效开始时间；式(18)定义普通物流设备当前任务结束才能处理下一任务；式(19)表示普通物流设备有效时间关系。

行车作业有效与实际时间的关系如图6所示，对于任意l∈C，其计算式为

图6　行车作业有效与实际时间关系图Fig.6　The relation between effective and real operation time of crane

(20)

(21)

(22)

(23)

式(20，21)定义行车搬出工序有效处理时间；式(22，23)定义行车搬入工序有效处理时间。

图7　行车调度时空网络图Fig.7　The network diagram of crane scheduling

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

(33)

(34)

(35)

式(24)表示行车调度目标函数；式(25)定义节点是否在行车行驶路径中；式(26，27)保证行车运行路径可行；式(28)表示行车运行安全距离约束和不可跨越约束；式(29)定义行车初始位置；式(30)保证分配给行车的任务得到处理；式(31)表示每台行车当前任务结束才能处理下一任务；式(32)定义任务优先级；式(33，34)分别表示加工任务和重车任务不可打断；式(35)定义格点权重。

2.2.2层次遗传算法

现构建层次遗传算法求解大尺度制造设备调度问题.用外层算法确定设备集成调度方案，每一个设备集成调度方案对应一个最优的行车调度方案，通过内层得到后传递到外层得到最优设备集成调度方案。

外层遗传算法采用分段编码，染色体由设备选择和工序排序两部分组成，如图8所示.设备选择部分保证了后续遗传操作后产生的解仍是可行解；工序排序部分编码柔性高，在解码过程中可以产生活动调度。

图8　外层遗传算法染色体编码Fig.8　Chromosome coding of the outer genetic algorithm

外层遗传算法种群初始化方式：将全局选择、局部选择和随机选择有机结合提高初始解在设备选择部分中解的质量.全局选择保证优先选择最短加工机器和平衡机器工作负荷，局部选择保证选择负荷最小的机器，随机选择保证初始种群多样性.工序排序部分染色体采用随机生成初始种群的方法。

外层遗传算法的遗传操作方式：选择操作采用锦标赛方法.设备选择部分采用均匀交叉法，以保证每位基因的先后顺序保持不变.工序排序部分采用POX交叉法.设备选择部分变异方法为在染色体基因串中随机选择一个位置，在此工序的可选设备集中选择加工时间最短的设备替换当前的基因.工序排序部分采用进行互换变异法，即从染色体中随机选择两个位置的基因，然后将它们进行位置的互换。

内层遗传算法的染色体编码：若车间配置n台行车，则染色体由n段组成，每段长相等为imax，代表相应行车运行轨迹.如图9所示，基因座代表节点ni,j中i，基因值代表j。

图9　内层遗传算法染色体编码Fig.9　Chromosome coding of the inner genetic algorithm

内层遗传算法的种群初始化方式：将分配给c1处理的工序按先后排列，每个工序对应生成一条最短基因链，当工序任务优先级为2或3时，基因链抱团成基因块，在其它基因座之间均可插入基因使染色体长度为imax，如图10所示.该方法保证行车有顺序地经过各个任务格点，同时缩短了染色体长度。

图10　内层遗传算法种群初始化Fig.10　Population initialization of the inner genetic algorithm

内层遗传算法的遗传操作方式：选择操作采用锦标赛方法，从种群中随机选择k个个体，选择最好的个体放到交叉池中，同时被选择的个体还放回到种群中，可以重新参与选择.每段染色体交叉方式：选择在同一可插入基因点插入基因的两条染色体作为母体，插入基因链中的等位基因前后是可选交叉点(图11所示灰色基因)；随机选择其中两个交叉点，交换两条交叉点之间的部分染色体；进行可行性判断与处理.每段染色体变异方式：随机删除某段插入的基因链，选择另一尚未插入基因链的可插入基因点插入相等长度的基因链；进行可行性判断与处理.交叉及变异方法同样保证了行车轨迹有顺序地经过各个任务节点。

图11　内层遗传算法交叉方式Fig.11　Crossover operator of the inner genetic algorithm

内层遗传算法的可行性判断与处理方式：在种群初始化、遗传操作等阶段对每个染色体进行可行性判断，包括不可跨越检查、安全距离检查，如果某相对应的染色体段无法满足要求，则选择可变动基因较多的那段重新生成染色体，直至满足要求。

3实例验证

以某大型装备企业部件加工车间为例对模型进行检验.该部件加工车间由2块长宽均为60m×12m的区域组成.部件基础数据如表1所示，部件工序信息如表2所示.车间配备加工设备M1，M2，M3，M4各3台，行车C共2台，普通物流设备P1，P2各3台.行车和普通物流设备的运行速率分别为1，1.5m/s.Cmax=100，C1=0.3，C2=0.3，C3=0.3，α=0.3，β=0.5，γ=0.2.通过模型进行求解.4D调度甘特图如图12所示，二维布局图如图13所示，Aug8层内的设备资源调度情况见图14，15.表3显示改善方案优于原方案，证实基于细胞机的大尺度制造4D调度模型可行、有效。

表1　部件基础数据表

表2　工序信息表

图12　4D调度甘特图Fig.12　The gantt chart of the 4D scheduling

图13　4D调度二维空间布局Fig.13　The two dimensional space layout of the 4D scheduling

图14　11.10层设备调度甘特图Fig.14　The gantt chart of the equipment scheduling in 11.10

图15　11/10层行车运行轨迹Fig.15　The path of the cranes in 11/10

方案部件延迟指标EI1时空利用率指标EI1设备利用率指标EI3综合评价指标EI实际方案0.27780.14810.08020.5064D调度方案0.41670.16510.13240.714

4结论

基于细胞机的大尺度制造4D调度模型在改善空间利用率、延迟部件数和设备有效利用率数等关键指标上效果明显.但目前关于大尺度4D调度的研究尚不成熟，模型运行效率有待提高，采用启发式调度规则寻求二维布局最优效率低效果差，在基础上寻求设备调度最优易使模型陷入局部最优.因此提高4D调度模型的运行速率和寻优性能是后续研究重点。

参考文献：

[1]张志英,陈洁.空间调度问题的非线性规划分析求解方法[J].计算机集成制造系统,2010,16(6):1272-1278。

[2]CHRISTOPHER G, GHAITH R. Exact and approximate methods for parallel multiple-area spatial scheduling with release times[J]. OR Spectrum,2013,35:639-657。

[3]CAPRACE J D, PETCU C, VELARDE M G. Optimization of shipyard space allocation and scheduling using a heuristic algorithm[J]. Journal of Marine Science and Technology,2013,18:404-417。

[4]张志英,曾燕慧,陈洁.基于多规则的船体分段建造空间调度方法[J].工业工程,2011,14(3):96-100。

[5]VALLS V, BALLESTIN F, QUINTANILLA S. A hybrid genetic algorithm for the resource-constrained project scheduling problem[J]. European Journal of Operational Research,2008,85:495-508。

[6]王蕾,张志英.基于规则的船体曲面分段空间调度方法[J].上海交通大学学报,2009,43(11):1709-1714。

[7]陈勇,陈亮.基于细胞机的造船企业分段车间空间调度模型的建模方法:中国,CN102968523A[P].2013-03-13。

[8]陈勇,阮幸聪,王亚良.基于元胞机的大型机械构件生产车间柔性调度求解[J].浙江工业大学学报,2011,39(4):433-439。

[9]陈超,鲁建厦.重型机械加工车间物流协调调度问题研究[J].浙江工业大学学报,2011,39(4):452-457。

[10]黄亚平,王万良,熊婧.基于改进蚁群算法的智能调度系统设计与开发[J].浙江工业大学学报,2010,38(3):251-256。

(责任编辑：陈石平)

中图分类号：TB497

文献标志码：A

文章编号：1006-4303(2015)02-0168-07

作者简介：陈勇(1973—)，男，湖南湘潭人，教授，博士，研究方向为生产系统建模与仿真，E-mail：cy@zjut.edu.cn。

基金项目：国家自然科学基金资助项目(71371170，71301148)

收稿日期：2014-06-05