复合工艺流程下批量生产车间调度多目标优化

曾 强 杨 育 王勇智 程 博

1.重庆大学机械传动国家重点实验室，重庆，400030 2.河南理工大学，焦作，454000 3.重庆红江机械有限责任公司，重庆，402100

0 引言

我国的多品种、中小批量生产企业在生产中，部分产品存在复合工艺流程。复合工艺流程是指同一种产品存在多个工艺流程，各个工艺流程的工序数可能相同也可能不同，工艺流程之间可相互替代，但不同的工艺流程所消耗的设备资源及生产效率存在差异。产生复合工艺流程的主要原因有两个：①大多数车间普遍存在普通设备与数控设备共存、功能不一的数控设备共存、数控设备与加工中心共存的现状[1]，为充分利用设备资源，同一产品可能需按不同的工艺流程加工；②企业进行技术改进，某些产品存在新旧工艺流程并存现象。学者已对传统的作业车间调度问题（Job Shop scheduling problem，JSP）和柔性作业车间调度问题（flexible Job Shop scheduling problem，FJSP）进行了大量的研究并取得了丰富的成果。但是，传统JSP和FJSP解决方案已不能解决复合工艺流程下批量生产车间调度问题。主要原因有两个：其一是传统JSP和 FJSP[2－5]针对的是单工艺流程而非复合工艺流程，具有复合工艺流程的车间调度问题是在传统的JSP或FJSP基础上增加了工艺流程合理选取的问题，比传统的JSP或FJSP更复杂。其二是传统的JSP和FJSP针对单件调度问题[5－8]或近似将批量车间调度问题视为单件调度问题，直接采用传统的JSP或FJSP解决方法对批量车间调度问题进行处理的方式不够精细，不利于生产效率的提升。文献[2-4，9－11]的研究表明，对于批量生产车间调度问题，通过将工序总时间区分为批量启动时间和工序加工时间，并将产品进行合理分批能取得较好的调度效果。

按各工序是否具有可选加工设备分类，复合工艺流程下批量生产车间调度主要有两个研究方向：复合工艺流程下作业车间调度问题（Job Shop scheduling problem with multiple process flows，MPF－JSP）和复合工艺流程下柔性作业车间调度问题（flexible Job Shop scheduling problem with multiple process flows，MPF－FJSP）。本文针对MPF－JSP，建立了一类复合工艺流程下批量生产作业车间多目标优化模型。在此基础上，提出并设计了一种复合工艺流程下作业车间调度多目标优化方法。

1 多目标优化模型

1.1 问题描述

车间需在M台设备上对N种按批量方式生产的产品进行优化调度，同一种产品的工艺流程不唯一，其不同工艺流程的工序数可不同。假设：①产品按等量分批原则分批；②工序在设备k上的加工时间确定，加工批次的装卸时间算在加工时间内；③批量启动时间已知；④ 加工批次的搬运时间不计；⑤ 加工批次之间具有相同的优先级；⑥加工批次一旦开始不可中断；⑦ 加工是非抢占式的。要求：在以上假设条件下进行工艺流程的合理选择和加工顺序的合理安排，在满足一定约束条件下同时使多个性能指标最优。为满足假设条件①需保证下式成立：

其中，Qn、Bn、Ln分别为产品n的生产量、加工批次数量和加工批量；Ln取Qn的约数。

1.2 优化模型

生产车间调度最关注的目标主要有三类：时间、成本、质量。复合工艺流程下的批量生产作业车间调度，因工艺流程可选，故不同工艺流程下各工序所用设备可能不同，批量启动时间及批量启动成本、加工时间及加工成本相应发生变化；同时，不同加工顺序会影响完工时间和制造成本。假定采用不同的工艺流程都需保证加工质量一致，因此，本文以完工时间、制造成本两个性能指标为优化目标，建立批量生产作业车间调度多目标优化模型。

式中，te为全部产品完工时刻；Cm为总制造成本；H 为加工批次总数

式（2）表示最大完工时间最小化，式（3）表示制造成本最小化。

约束条件：

式中，Sirjk、Eirjk分别为Ji工艺流程r的工序j在设备k上的开始时刻和完成时刻；Rir1jdr2gk为标志变量，d＝1，2，…，H；g＝1，2，…，Nod；若Ji的工艺流程r1的工序j和Jd的工艺流程r2的工序g在同一台设备k上加工且工序j先于工序g，则Rir1jdr2gk为1，否则为0；Ld为加工批次Jd的加工批量。

式（4）表示若Ji上道工序与下道工序所用设备不同，则上道工序完工后才能开始下道工序加工，但可以提前进行准备使上道工序完工后可立即开始加工；式（5）表示若Ji上道工序与下道工序所用设备相同，则Ji下道工序必须在Ji完工后才能开始准备；式（6）表示同一台设备k不能同时加工两个工序；式（7）表示任意工序的完工时间与开始时间之差不能小于其所需时间。

2 算法设计

2.1 定义对象

为便于处理复杂的实体逻辑关系，提高程序设计的可读性、计算效率、可扩展性，引入面向对象技术到算法整个设计过程中。本文共定义了加工设备对象、加工批次对象和染色体对象共三类对象，如图1所示。

各对象之间的逻辑关系如下：①各对象从数据源获取原始信息；②染体色对象CHR（f）根据J（i）.Np生成合法的工艺流程编码赋给PFORDER属 性；③CHR（f）根 据 J（i）.PF（PFORDER（i））.No，生成合法的加工顺序编码赋给JORDER属性；

图1 对象定义

④CHR（f）根据其 PFORDER、JORDER、MACH（k）.FREE 及J（i）.PF（PFORDER（i））.OPR解码得调度矩阵R；⑤CHR（f）根据调度矩阵R计算目标向量O。

2.2 计算流程

基于Pareto寻优思想，提出并设计了改进的快速非支配排序遗传（NSGA－Ⅱ）算法以求解上述多目标优化调度模型。算法总体计算流程[12-13]如图2所示。

图2 算法流程图

2.3 编码操作

复合工艺流程下批量生产作业车间调度问题包括两个子问题：工艺流程的选择和加工顺序的安排。根据这个特点，采用分段编码，即对各加工批次的工艺流程号和加工顺序分别编码。因引入了面向对象技术，可将两个编码分别赋予染色体对象CHR（f）的PFORDER和JORDER属性。

式（8）所示的PFORDER编码表示加工批次J1、J2、…、JH－1、JH分别选用工艺流程2、1、…、1、2。

JORDER采用基于工序的编码方式，由Not个自然数组成，Not的值由式（10）计算。加工批次号i出现J（i）.PF（PFORDER（i））.No次。例如，式（9）的JORDER中的3个1分别代表加工批次J1的工序1、2、3，依此类推。这种编码方式自然保证JORDER编码可行且其任意排列总能产生可行加工顺序。可见，各工艺流程下工序数不同可导致JORDER为变长结构。

2.4 种群初始化

设种群规模为Psize，则按如下步骤产生Psize个染色体，完成种群初始化操作。

（1）令f＝1；

（2）初始化 CHR（f）.PFORDER。 对PFORDER每一基因位i，随机产生一个1～J（i）.Np的自然数赋给PFORDER（i）；

（3）按式（10）计算CHR（f）的工序总数Not；

（4）产生一长度为CHR（f）.Not的零向量赋给CHR（f）.JORDER；

（5）按如下的伪代码给CHR（f）.JORDER赋值：

for p＝1to H－1

在 CHR（f）.JORDER中随机寻找J（i）.PF（PFORDER（i））.No个为0的位置，并将此位置的值赋为iNext

将CHR（f）.JORDER中剩余为0的位置赋为H

（6）令f←f＋1；

（7）若f≤Psize，则转步骤（2），否则种群初始化结束。

2.5 非支配排序

非支配排序的目的是计算种群中各染色体的前沿值Ra。将所有染色体进行分层，具体过程如下：找出当前种群中不被任何其他染色体支配的染色体，这些染色体的集合为第1级非支配染色体集，令Ra＝1；将第1级非支配集中的染色体从当前种群中去除，然后从剩余染色体中找出非支配染色体集，令Ra＝2；依此类推，直到种群中所有染色体的前沿值确定为止。

2.6 拥挤度计算

为增强种群的多样性，引入染色体拥挤度Cd的概念。CHR（f）.Cd反映了该染色体周围（同一级）相似染色体的数量，其计算公式为

式中，m为优化目标数；fq（f）为CHR（f）的第q个目标值；maxfq、minfq分别为某一前沿面上所有染色体第q个目标的最大值和最小值。

从式（11）可见，拥挤度CHR（f）.Cd越大，说明CHR（f）周围的点越稀疏，进化过程中应给以较大的生存概率以保证种群多样性。

2.7 遗传操作

2.7.1 选择操作

选择操作采用二元联赛机制，每次从父代种群中随机选择2个染色体，若二者的Ra不相等，则选择Ra小的染色体，若二者相等，则选择拥挤度大的染色体，将选中的染色体加入配对池POOLPOP，另一个舍弃，直到达到规模Psize／2为止。

2.7.2 交叉操作

因PFORDER为定长结构，JORDER为变长结构，故规定交叉操作只对PFORDER进行。由于PFORDER交叉后，相应加工批次Ji的工序数可能发生变化，因此需对JORDER进行修复。

如图3所示，采用两点交叉法，随机产生1～H 的自然数C1和C2并使C1≤C2，将PFORDER1与PFORDER2的C1～C2之间对应的基因值进行对换。根据PFORDER1的C1～C2之间每一个基因值的变化情况，按如图4所示的流程对JORDER1进行修复。同理，根据PFORDER2对JORDER2进行修复。

图3 PFORDER交叉操作示意图

2.7.3 变异操作

变异操作采用分段方式进行，包括PFORDER的变异和JORDER的变异。变异的原则是两者分别独立变异，即PFORDER变异则JORDER不变异，JORDER变异则PFORDER不变异。

对PFORDER的变异采用单点变异，随机产生一个自然数i（i＝1，2，…，H）代表要变异的基因座，再随机产生一个自然数a（a＝1，2，…，J（i）.Np）代表变异后的工艺流程号，用a取代PFORDER（i），再利用与图4相似的原则对JORDER进行修复。

图4 JORDER修复流程

对JORDER的变异操作设计了两种：逆序变异和两点交换变异。将两种变异方式相结合有利于增强种群多样性和寻优能力。采用这两种变异方式可保证变异后的JORDER仍然可行，不必进行修复。

2.8 解码操作

为充分提高生产率，在算法中采用3种精细化调度技术来减少设备空闲时间。第一，将工序总时间区分为批量启动时间和工序加工时间，使下道工序可以提前准备，一旦上道工序加工完毕可立即开始加工下道工序[2，9]；第二，若将同一产品不同加工批次的同一工序前后安排在同一台设备上，则后一道工序省去批量启动时间及批量启动成本；第三，对工序采用“间隙挤压法”[8]进行“插入式”安排以产生活动化调度。整个调度算法的原理如图5所示，其中白色方框代表已安排的时间段，黑色方框、条纹方框分别代表当前待安排工序的批量启动时间段和加工时间段，Fyb为设备k的第y空闲时间段的起始时间，Fye为设备k的第y空闲时间段的结束时间，其值需根据图6流程进行修正。

图5 解码示意图

图6 Fye值修正流程图

解码过程如下：

（1）从加工顺序编码JORDER中取出下一道待安排工序，设为Ji的工艺流程r的第j道工序，加工设备为k。

（2）对设备k的每一空闲时间段，按式（12）从左向右依次寻找待安排工序的可插入位置，一旦找到则退出寻找过程。

①批量启动时间Stirjk按如下原则确定。若设备k第y空闲时间段前面的工序与待安排工序属于同一产品不同加工批次的同一个工序，则Stirjk＝0；否则Stirjk取待安排工序在设备k上的批量启动时间。②工序最早允许开始时间u按如下原则确定。若j＝1，则u＝Sir1k；若j＞1，令j－1工序所用设备为m，分两种情况处理：若k＝m（图5b），则令u＝Eir（j－1）m；否则（图5c）令u＝Eir（j－1）m－Sirlk。

（3）将待安排工序安排在所找到的y空闲时间段内，则其起始时间为 max（u，Fyb），结束时间为 max（u，Fyb）＋Stirjk＋CtirjkLi。

（4）根据flag值修正y空闲间段后道工序的批量启动时间、批量启动时刻。

（5）更新设备k的空闲时间表MACH（k）.FREE。

2.9 目标值计算及终止条件

根据解码得到的调度矩阵R计算该调度方案对应的目标值，包括最大完工时间te和制造成本Cm。采用基于最大迭代次数的终止方式，即当迭代次数超过最大迭代次数Nmax时退出进化过程。

3 实例分析

为验证本文方法的有效性，以MATLAB 2007为编程环境实现了上述算法，并将其在某船舶零配件企业金属加工车间生产调度中进行应用。该车间在某调度周期内要在7台设备（车床M1、立式铣床M2、磨床M3、卧式铣床 M4、立式加工中心M5、卧式加工中心M6、摇臂钻M7）上安排4种产品（P1、P2、P3、P4）的生产，各产品均存在2个工艺流程，编号为1、2，生产量均为200件。产品工艺参数如表1所示，表1中产品P1第一行工序1对应的向量（1，8，30，50，40）分别表示P1的工艺流程1的工序1在设备1上加工，单件加工时间为8min，批量启动时间为30min，加工费率为50元／h，批量启动费率为40元／h，以次类推。取最大迭代次数Nmax为200，种群规划Psize为50。

表1 工艺参数

3.1 复合工艺流程与单一工艺流程的对比

固定加工批量向量L＝（100，100，100，100），它表示J1～J4对应的加工批量均为100件，对工艺流程1、工艺流程2和复合工艺流程分别进行优化，得到的Pareto最优解集如图7所示，图8～图10是各工艺流程下某调度方案对应的设备甘特图。

图7 单一工艺流程与复合工艺流程下的Pareto解集

图8 工艺流程1下A方案设备甘特图

图9 工艺流程2下C方案设备甘特图

实例分析可知：

（1）由图7和图8可见，工艺流程1下得到了多个Pareto解，但分布过于集中，生产排产柔性不足；在工艺流程1下，4种产品用到了一般数控设备1、2、3、4、7，制造成本较低，但因加工时间长，使得完工时间较长。

图10 复合工艺流程下B方案设备甘特图

（2）由图7和图9可见，工艺流程2下只得到了一个Pareto解，说明生产排产柔性很差；在工艺流程2下，4种产品用到了设备1、2、5、6、7，其中设备5、6为加工中心，制造成本高，但它们能独自完成原来由几台一般数控设备才能完成的多道工序，同时因加工中心加工速度快，使完工时间短于工艺流程1。

（3）由图7和图10可见，复合工艺流程下得到了多个Pareto解且解的个数较多、分布较均匀，生产排产柔性很强；在复合工艺流程下，一般数控设备与加工中心相结合，通过将产品分成多个加工批次，在数控设备和加工中心之间进行负荷均衡分配，使完工时间较短，制造成本位于单一工艺流程1和工艺流程2的制造成本之间。

3.2 复合工艺流程下不同加工批量对比

取复合工艺流程，以4种不同的加工批量方案分别进行优化：①加工批量向量L＝（200，200，200，200），②加工批量向量L＝（100，100，100，100），③加工批量向量L＝（50，50，50，50），④加工批量向量L＝（20，20，20，20），得到的 Pareto最优解集如图11所示。

实例分析可知：

（1）在一定的范围内，随着加工批量的减小，Pareto解集向“左下”方向平移，说明调度解整体优化；

（2）当加工批量减小到一定幅度后再继续减小加工批量，Pareto解集向“右上”平移，说明调度解整体发生了恶化。

产生以上现象的原因是：加工批量过大时，单个加工批次的加工时间较长，下道工序开工较晚，设备等待时间较长；进行工序插入式安排时可使空闲时间段减少，设备“时间碎片”增多，延长了完工时间；加工批次过少，生产排产柔性差，设备难以得到均衡利用。反之，随着加工批量的减小，加工批次增多，单个加工批次的加工时间缩短、生产排产柔性增强，调度效果逐步得到改善；加工批量减小时，加工批次的增多导致加工批次的批量启动时间所占比例逐渐增大，批量启动成本也逐渐增加；加工批量过小时，批量启动时间所占比例及批量启动成本均大大增加，整体上表现出调度解的质量发生恶化。因此，可以推测，理论上存在一个最优的加工批量方案使得完工时间和生产成本综合效果最佳。然而，问题的“组合爆炸”特点使得这个最优方案的时间成本相当高，甚至缺乏时效性。

图11 Pareto解集

4 结论

（1）复合工艺流程下批量生产车间调度多目标优化方法能有效解决复合工艺流程下的批量生产作业车间多目标优化调度问题，帮助调度人员寻找满意调度方案。

（2）复合工艺流程下通过分批将产品不同加工批次按不同的工艺流程进行加工，可达到均衡设备负荷的目的，使批量生产作业车间多目标调度优化效果明显优于单一工艺流程下优化效果。

（3）加工批量大小对复合工艺流程下批量生产作业车间多目标调度效果具有显著影响，理论上存在最优的加工批量方案使调度效果最佳，但准确确定最优的加工批量方案的时间成本很高。

[1]周延佑，陈长年.多品种、单件、小批量生产和少品种、大批量生产解决方案的新发展[J].制造技术与机床，2007（5）：28-36.

[2]潘全科，朱剑英.多工艺路线的批量生产调度优化[J].机械工程学报，2004，40（4）：36－39.

[3]孙志峻，安进，黄卫清.作业车间多工艺路线批量作业计划优化[J].中国机械工程，2008，19（2）：183－187.

[4]孙志峻，乔冰，潘全科，等.具有柔性加工路径的作业车间批量调度优化研究[J].机械科学与技术，2002，21（3）：348－354.

[5]潘全科，朱剑英.多工艺路线多资源多目标的作业调度优化[J].中国机械工程，2005，16（20）：1821－1826.

[6]Seo Minseok，Kim Daecheol.Ant Colony Optimisation with Parameterised Search Space for the Job Shop Scheduling Problem[J].International Journal of Production Research，2010，48（4）：1143－1154.

[7]Bagheri A，Zandieh M，Mahdavi I，et al.An Artificial Immune Algorithm for the Flexible Job－shop Scheduling Problem[J].Future Generation Computer Systems，2010，26（4）：533－541.

[8]吴秀丽，孙树栋，余建军，等.多目标柔性作业车间调度优化研究[J].计算机集成制造系统－CIMS，2006，12（5）：731－736.

[9]周亚勤，李蓓智，杨建国.考虑批量和辅助时间等生产工况的智能调度方法[J].机械工程学报，2006，42（1）：52－56.

[10]Jeong H L，Park J，Leachman R C.Batch Splitting Method for a Job Shop Scheduling Problem in an MRP Environment[J].International Journal of Production Research，1999，37（15）：3583－3598.

[11]Huang Rong Hwa.Multi－objective Job－shop Scheduling with Lot－splitting Production[J].International Journal of Production Economics，2010，124（1）：206－213.

[12]陈华平，谷峰，古春生，等.两级排序遗传算法在柔性工作车间调度中的应用[J].系统仿真学报，2006，18（6）：1717－1720.

[13]卫田，范文慧.基于NSGAⅡ的物流配送中车辆路径问题研究[J].计算机集成制造系统，2008，14（4）：778－784.