考虑任务排序策略的舰船建造车间虚拟制造单元动态调度

韩文民，孙晓梅，孔 鹏，吕 洁

(1．江苏科技大学 经济管理学院，江苏 镇江212003;2．大连船舶工业公司(集团)，辽宁 大连116001)

0 引 言

造船企业为了提高生产效率，缩短生产周期，也为了使其最终产品在今后使用过程中应对技术的快速发展和提高，在加工对象的生产、建造方面，力图实现模块化和单元化。如发达国家舰船建造已普遍实现了模块化，当出现战损或技术更新的时候，可以通过快速更换相应模块而迅速复原或提高其技术水平。但我国现有企业在生产加工中还基本采用传统的工艺专业化的生产组织方式，或基于成组技术传统的静态生产单元的生产组织方式。这就造成了生产加工组织方式与加工对象要求不能很好匹配的现象，生产加工组织的较低效率难以适应加工对象模块化和单元化的需要，过早、过量的库存与突击赶工的不良生产状况并存，影响了企业的生产效率和生产柔性的水平。

虚拟单元制造系统(Virtual Cell Manufacturing System，VCMS)［1］是单元制造模式的新发展，是近年来日益受到重视的一种先进制造方式。在环境复杂多变，产品组合难以预测的情况下，它可以通过逻辑重构，根据任务变化快速成组，共享资源，提高系统的柔性与效率。

舰船建造是动态、复杂、规模庞大的系统，在船舶制造过程中各阶段加工对象复杂性高且品种多，加工设备空间位置上常常不易移动，关键资源的共享性高，容易造成混乱、利用率不高，但因其存在工艺相似性特点，采用虚拟制造单元生产组织方式，在车间层构建单元，不改变设备的物理布局，而是逻辑上动态重构，来实现造船生产车间的协调调度，实时控制，可以提高系统的柔性和效率。其中，关键的问题之一就是如何有效实施虚拟单元动态调度。近年来，一些学者对单元调度方面的问题进行了积极地研究，Shiue和Guh［2］考虑了不确定需求下动态生产单元内的零部件调度，并运用混合遗传算法和人工神经元网络方法进行求解。Gabried［3］等提出了基于TOC 思想的生产系统启发式单元调度方法。白俊杰［4］等考虑了批量生产因素下的柔性作业车间多目标优化问题。冷晟［5］和Kesen S.E.［6］等研究了工艺柔性和工件运输等生产因素下的虚拟单元调度问题。Ye Hegui［7］和Aksoy［8］等考虑了虚拟制造单元调度问题中的成本因素并采用混合算法来求解。Kesen和Güng r［9］研究了虚拟制造单元调度中的批量分割问题。K.L.MAK，J.Ma.［10］考虑了在虚拟单元制造系统设计中存在多个时间阶段的生产调度问题。从这些研究可以看出，虚拟制造单元这一先进组织方式应用于生产制造方面已经逐渐成为研究热点问题，虚拟单元下的调度可以优化生产过程，降低生产成本，快速组织资源，提高市场响应速度。但是目前具体研究虚拟单元动态调度过程中，共享资源在各时间阶段内可能存在能力冲突或者任务重叠方面的研究还比较少，而实际生产中存在多个周期阶段的动态调度，虚拟单元的共享资源可能会存在冲突进而影响调度的效率和系统的连续性。只有协调好共享资源的使用和生产能力，才能保证系统的连续生产、负荷均衡和高效产出。本文就是在已有研究的基础上，从船舶制造系统调度动态变化的角度出发，提出了基于计划期的生产控制机制，为其提供了一种考虑共享资源协调和分配策略的虚拟单元动态调度方法。

1 问题描述及建模

1.1 问题描述

基于以上背景研究和可行性分析，本文采用阶段性变动的方法将舰船制造计划期划分为多个时间阶段，每个时间阶段内的调度模型如图1所示。统一管理和分配制造单元内的加工任务和共享资源，生成可行的调度方案。具体而言，通过检测车间资源在各个时间阶段内的使用情况，如果出现任务重叠则结合调度排序策略进行协调，同时记录资源的使用和释放时间阶段以及资源的加工剩余能力，实现动态可行的调度。最终调度结果反映的信息包括:作业的机器分配、作业在每台机器上的开始和完成时间、各阶段的机器剩余能力及计划期内各任务的加工率等。

图1 各时间阶段内的调度模型Fig.1 Scheduling model within each time period

1.2 虚拟单元动态调度模型

模型中考虑舰船制造车间包含多种类型的零件作业，多种类型的机器，且同种类型的机器不只一台，机器的最大生产能力已知且不变。机器在物理位置上常常是难以移动的，机器间的距离也是已知且不变的。基本假设:1)虚拟单元构建已完成;2)任意时刻每台设备只加工一项任务;3)每项任务都有已知的加工路径;4)任务在设备上一旦开始加工则不允许中断;5)所有调度作业在0 时刻都已经就绪可以进行加工;6)每项任务可以选择同种类型设备的任一台进行加工;7)设备调整时间忽略不计。

模型符号说明:

j 表示作业(j=1，2，…，n);

Vj表示作业j 的加工数量;

m 表示车间工作区类型(m=1，2，…，M);

rj表示作业j 的加工路线;

Oj，i表示作业j 的第i 个工序;

Kj表示作业j 的操作工序总数量;

MCm，p表示j 阶段工作区i 的最大加工能力;

PH 表示计划期;

L 表示时间阶段的长度;

D(rj)表示作业j 的生产路径r 的总物料运输距离;

决策变量为:

PRj，i，m(rj)，p表示p 阶段，在工艺路线r 下使用m 工作区时，作业j 的第i 个工序的加工率(加工数量);

Pj，i表示作业j 的工序i 的总批量加工时间段;

Sj，i，m(rj)，p表示作业j 的工序i 的开始加工时间;

Fj，i，m(rj)，p表示作业j 的工序i 的完成时间;

RCm，p表示p 阶段工作区m 的剩余加工能力。

1.3 模型建立

通过充分利用虚拟单元的共享资源，以设备生产能力为约束，依据排序调度策略，最终达到最大完工时间和总物料运输距离最小的目标。则虚拟单元多阶段动态调度的非线性数学模型如下:

满足约束:

当Xj，i，m(rj)，p=1 时，Yj，i，m(rj)，p+t′=1。

即满足

在模型中，式(1)表示一旦作业j 的i 操作完成，下一个操作i+1 立即开始;式(2)保证每个阶段内作业j 的每个工序的加工率是相同的;式(3)保证所有操作的开始时间必须在计划的周期里;式(4)保证作业j 的操作i 可以在阶段［p，p+θ］内完成;式(5)表明每个工作区m 在阶段p 的剩余加工能力，且取值是大于等于0 的;式(6)表示p 阶段的工作区m的加工能力约束;式(7)表示作业α=1，β=3 的操作i 的开始加工时间;式(8)表示作业α=1，β=3的操作i 的总批量加工时间阶段;式(9)表示作业α=1，β=3 的操作i 的完成时间;式(10)保证加工率是大于等于0 的;式(11)确保决策变量是二进制变量。

1.4 排序调度策略

考虑虚拟单元调度的动态性特点，传统调度规则有其一定的局限性。因此针对虚拟单元多阶段动态调度，本文考虑将时间阶段与任务排序策略相结合的启发式规则，可以在各个时间阶段合理分配共享资源加工能力，避免任务重叠，同时能确定出加工任务的使用时间阶段和调度次序，实现虚拟单元的动态调度、高效产出和物流平衡。排序调度策略设计如下:

1)计算出各项作业的开始加工的时间阶段。

2)比较工作区每台机器上各个操作的时间阶段，如果在给定机器上加工的2 个操作的时间阶段并不重叠，则这2 个操作的优先顺序可以确定;如果2 个操作的时间阶段出现重叠，则要计算每个操作对的时间间隔以确定优先级排序。同一机器m 上的操作(m，i)和(m，i′)之间的时间间隔，σ(m，i)→(m，i′)=dm，i′- sm，i- pm，i- pm，i′，dm，i′表示操作i′ 的交货期，sm，i表示i 的开始加工时间，pm，i和pm，i′分别表示操作i和i′ 的加工时间。σ(m，i)→(m，i′)可能会出现下面4 种情形:

情形1:如果σ(m，i)→(m，i′)≥0 而且σ(m，i′)→(m，i)＜0，则优先级排序为(m，i)→(m，i′);

情形2:如果σ(m，i)→(m，i′)＜0 而且σ(m，i′)→(m，i)≥0，则优先级排序为(m，i′)→(m，i);

情形3:如果σ(m，i)→(m，i′)＜0 而且σ(m，i′)→(m，i)＜0，则不成立;

情形4:如果σ(m，i)→(m，i′)≥0 而且σ(m，i′)→(m，i)≥0，则具有同样的优先级，每种排序均可。

3)当出现情形3 时需要回溯修改条件;当满足情形1、2 、4 时，则加入新的操作优先级排序，生成调度方案，再更新时间直至所有任务动态调度完成。

2 混合算法求解

蚁群算法具有原理简单、通用性强、受限制约束较小等特点，在动态调度中的应用前景较好［11］。但传统的蚁群算法搜索时间过长且易陷入局部最优解中。因此，本文采用改进蚁群算法与启发式分配规则相结合的混合算法来实现优化的动态调度求解。改进蚁群算法中的精英策略和最大最小蚂蚁算法可以加快收敛速度，增强更新能力，更好地找到全局最优解。混合算法又能进一步提高改进蚁群算法的全局和局部搜索效率和质量，达到优势互补，优化搜索过程，混合算法流程图如图2所示。

步骤1:参数初始化。任务j 与任意设备mk间信息素的初始值设为τmax;Nant为蚂蚁数量，Nd为迭代次数，N 为任务总数，令迭代项I 为1。

步骤2:任取一只蚂蚁，令a=1。任务的开始加工时间和完成时间分别对应开始、完成时间矩阵，蚂蚁最初可选的工序集合Da为所有待加工任务的第一个工序组成的集合。

图2 混合算法流程图Fig.2 Hybrid algorithm flow chart

1)蚂蚁a 依据状态转移规则选择工序集合Da中任务j 的工序i 对应的设备，蚂蚁每次走完一步，其路径上的信息素便开始蒸发。

2)将该工序安排给所选的设备，并时时更新开始、完成时间矩阵，并将与该任务工序的紧后工序放入Da中，替换掉该工序，令j=j+1。

3)对于集合Da中的每一个工序选择相应的设备，同时计算每台机器上时间间隔，确定出操作排序，并更新已分配的工作区的剩余能力。

4)如果该工序i 为某任务的最后一个工序，则从Da中将其删除，否则将同属于该任务的紧后工序放入Da中，替换掉该工序i。Da中与工序i 不在同一设备上的工序，在下一次为任务j+1 选择工序时，不需要再次计算。若j=N，转到步骤3，否则，令j=j+1，转步骤2 中的3)。

步骤3:若a ＜Nant，令a=a+1，转到步骤2的1)，否则，转到步骤4。

步骤4:比较各蚂蚁的搜索路径，采用精英蚂蚁策略进行全局信息素的更新。

步骤5:如果出现新的全局最优解，则更新信息素浓度区间，同时更新τmin，τmax，否则，转到步骤6。

步骤6:若迭代项I 小于Nd，令I=I+1，转到步骤2，否则，结束求解。

3 案 例

为验证动态调度模型的有效性，本文以某船厂舾装车间的某班组作业数据为例进行研究，调研数据整理如下:车间内共享的工作区有6 类，每个工作区中的设备数量已给出，具体情况如表1所示，零件的具体加工信息如表2所示，表3 描述的是各工作区之间的运输距离。

表1 工作区的设备信息Tab.1 The workspace machine information

表2 各作业任务的基本加工信息Tab.2 Job processing information

表3 各工作区之间的运输距离矩阵(单位:m)Tab.3 Travelling distance matrix between each workspace

3.1 虚拟单元动态调度的结果

本文采用改进蚁群算法与启发式规则，具体参数为:蚂蚁的数量Nant=50，迭代次数Nd=50，信息素蒸发速率为0.1，信息素参数α=1，β=3。图3 表示的是7 项作业的最终调度结果，表4给出了虚拟单元共享工作区下的作业调度时间安排。从图3 中可知计划期被分为30 个阶段，每个阶段的长度设为240 min，系统的最大完工时间为76 h(4 560 min)，无作业延迟，所有作业的总物料运输距离为2 671 m，与原有制造数据相比有了很大的改进。

表4 虚拟单元作业调度时间阶段安排Tab.4 Job scheduling time arrangement of virtual cells

图3 调度甘特图Fig.3 Schedule gantt chart

3.2 结果分析

与原船厂舾装作业车间相应制造指标进行比较得到表5，可以看出虚拟单元系统的平均作业完工时间明显短于现有制造车间。进一步比较系统的产出(产品加工率)如表6所示，可以看出总体来说虚拟制造系统的产出效率是显著高于现有车间的，可见虚拟单元系统的资源共享和逻辑重构特点能显著地提高效率和生产加工率，且总的完工时间也明显缩短。

表5 作业完工时间对比Tab.5 Completion time comparison

4 结 语

考虑造船企业实际生产环境的复杂性和动态需求的多变性，基于计划期的虚拟制造单元动态调度控制机制的研究有着较大的理论意义和应用价值。本文具体针对虚拟单元动态调度过程中的任务资源选择及共享资源的协调和分配问题进行了研究，提出了虚拟单元多阶段动态调度的数学模型，其中设计了排序调度策略，对于共享资源中存在的任务重叠问题给予了一定的优先级解决策略，实现了虚拟制造单元动态调度过程中共享资源的协调和负荷的平衡。并且提出了改进蚁群算法和启发式规则求解。船厂应用实例结果表明，虚拟单元动态调度应用于船舶制造系统可以明显提高作业效率、系统产出并能保证共享资源的合理有效分配。未来应根据舰船建造特点，进一步开展虚拟制造单元下周期驱动与事件驱动相结合的动态调度问题的研究与应用。

［1］MAK K L，LAU J S K，WANG X X．A genetic scheduling methodology for virtual cellular manufacturing systems:an industrial application［J］．International Journal of Production Research，2005，43(12):2423－2450．

［2］SHIUE Y R，GUH R S．Learning-based multi-pass adaptive scheduling for a dynamic manufacturing cell environment［J］．Roboties and Computer-Integrated Manufacturing，2006，22(3):203－216．

［3］GABRIED G C，SADAMI S，TAKAO E．A proposal for the scheduling of cell manufacturing through TOC［J］．Journal of Japanese Industry Manage Associate，2007，57(6):503－510．

［4］白俊杰，龚毅光，王宁生，等．多目标柔性作业车间分批优化调度［J］．计算机集成制造系统，2010，16(2):396－403．

BAI Jun-jie，GONG Yi-guang，WANG Ning-sheng，et al．Multi-objective flexible job shop scheduling with lotsplitting［J］．Computer Integrated Manufacturing Systems，2010，16(2):396－403．

［5］LENG Sheng，WEI Xiao-bin，ZHANG Wen-yi．Improved ACO scheduling algorithm based on flexible process［J］．Transactions of Nanjing University of Aeronautics and Astronautics，2006，23(2):154－160．

［6］SAADETTIN E K，SANCHOY K D，Zülal Güngr．A genetic algorithm based heuristic for scheduling of virtual manufacturing cells(VMCs)［J］．Computers and Operations Research，2010，37(6):1148－1156．

［7］YE He-gui，LIANG Ming．Simultaneous modular product scheduling and manufacturing cell reconfiguration using a genetic algorithm［J］．Journal of Manufacturing Science and Engineering，Transactions of the ASME，2006，128(4):984－995．

［8］AKSOY，ASLIOZTURK，NURSEL．Simulated annealing approach in scheduling of virtual cellular manufacturing in the automotive industry［J］．International Journal of Vehicle Design，2010，52:82－95．

［9］KESEN，SAADETTIN E，Güng r，Zülal．How important is the batch splitting activity in scheduling of virtual manufacturing cells(VMCs)［J］．International Journal of Production Research，2011，49(6):1645－1667．

［10］MAK K L，MA J．A Novel hybrid algorithm for multi-period production scheduling of jobs in virtual cellular manufacturing systems［J］．Proceeding of the Word Congress on Engineering，2011(1):978－988．

［11］ARNAOUT J P，RABADI G，MUSA R．A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times［J］．Journal of Intelligent Manufacturing，2010，21:693－701．