集成式工艺规划与车间调度问题研究现状及发展

文笑雨, 王康红, 孙海强, 高 亮

(1.郑州轻工业大学 a.河南省机械装备智能制造重点实验室;b.机电工程学院，郑州 450002;2.华中科技大学 数字制造装备与技术国家重点实验室，武汉 430074)

随着中国经济高速发展和人民生活水平的提高，消费者对于产品的需求逐渐从标准化趋向于个性化、定制化，这会对生产设备的柔性提出了更高的要求。为满足不同用户的不同需求，越来越多的企业开始进行非标准机械设备的设计和制造。这些机械设备一般具有加工灵活性高的特点，多由多个小功能单元组成复杂的系统，每一个功能单元的组成部分相对简单，一般包含种类繁多的不同零件，单个零件的结构相对简单、加工灵活性比较大，因此工艺路线可选择性比较大。在加工生产这一类非标准机械设备时，制造系统中会包含丰富的机器柔性、工序顺序柔性和加工路径柔性，工艺规划与车间调度环节相互制约与影响的程度较大。这些企业现场管理均存在工艺规划环节与车间调度环节难以协调，生产调控困难的问题，实现工艺规划与车间调度的集成优化显得极其重要。工艺规划与车间调度是制造系统中重要的两个子系统，工艺规划的输出制约着车间资源的分配，车间的实时状态影响工艺规划的有效性。若将工艺规划与车间调度分成两个独立环节展开研究，两者的相互制约关系将对制造系统整体性能的提升产生不良的影响[1]。随着智能制造的兴起，数字孪生[2]、网络化制造[3]等新技术的发展使得工艺规划环节和车间调度环节的数据更容易互联互通，对不同制造环节的集成优化以及调度方案的动态调控是保证智能制造能够推行的重要技术。对集成式工艺规划与车间调度(integrated process planning and scheduling, IPPS)问题进行研究可以在工艺规划初期对后期加工现场的资源利用状况进行预测，能够有效避免加工现场的资源冲突，使现有的生产资源得到充分利用，满足企业对市场需求的快速响应。

在制造业可持续发展的需求下，在进行工艺规划及车间调度时需要考虑一些绿色指标，如噪音、能耗、碳排放等[4]。另外，制造系统实时运行过程中常伴随一些无法预料的不确定扰动因素，如工件工序加工时间不确定、机器故障、交货期变化、订单变化等。为保证生产高效、低耗、有序运行，要求制造系统必须能够对不确定扰动因素及时响应、动态调整[5]。IPPS问题因为考虑到制造系统的多种柔性因素，能够应对生产中一些不确定扰动因素。对IPPS问题进行研究时需要考虑如何在模型构建以及运作方法上及时应对不确定扰动事件，减少不确定性因素对调度方案带来的影响。

在上述背景下，针对近年来IPPS问题的研究现状，笔者分别从IPPS建模、IPPS求解方法两方面进行综述与分析，并对不确定扰动下IPPS问题以及面向绿色制造的IPPS问题研究现状进行了总结与分析。在上述分析基础上，对未来开展IPPS问题研究的一些方向进行了展望。

1 IPPS问题研究现状

1.1 IPPS建模方法的研究概况

工艺规划与车间调度一般分属于制造企业中的不同部门，在实施集成优化时，重点需要考虑两环节之间信息如何进行交互。根据两环节不同的信息交互方式，一种经典的分类方法是将工艺规划与车间调度的集成模型分为3种[1,6]：非线性方法、闭环式方法以及分布式方法。吕盛坪等[7]将上述3种集成方法归纳为离线式接口集成方法、在线式接口集成方法以及面向功能集成方法。这3种集成方法的特点及应用情况如表1所示。这3种集成方法中，非线性方法因其在工艺规划与车间调度环节信息交互方式上比较简单，应用最为广泛。大多数研究者聚焦于建立合适的混合整数规划模型，以期能够保证工艺规划环节为车间调度环节提供尽可能多的备选工艺路线集合[8]。

表1 3种集成方法的特点及应用情况Table 1 The characteristics and applications of three integration methods

随着IPPS基本集成模型研究的日渐成熟，越来越多的学者开始关注特定生产环境下工艺规划与车间调度进行集成的特殊性。从大批量定制化生产模式的特点出发，充分考虑到不同类型的制造企业对于工艺规划与车间调度阶段的重视程度有所不同，陈亮[9]采用主从联合优化思想构建工艺规划与车间调度的集成优化模型。Chen等[10]构建了面向产品不确定性的IPPS双层规划模型，采用混合整数规划模型描述上层工艺规划模型，采用基于Agent的建模方法处理下层车间调度问题。Rietz等[11]建立了一种伪多项式网络流模型，用以对中期工艺规划与短期车间调度进行集成。为了应对实际制造过程中存在的多车间供料及加工的情况，巴黎等[12]提出了综合考虑装配及物流环节的IPPS模型。针对具有并行单元和资源受限的多产品单级批处理工厂，结合制造服务理念，Aguirre等[13]提出了一种IPPS与机器维护维修集成的模型。上述研究均表明，IPPS建模方法的研究在朝向更贴近实际生产的方向逐步发展，所建立的集成模型注重工艺规划与车间调度的层次关联性，对不同的生产模式更具有针对性，对实际制造环境描述的更加完备。这将进一步促进IPPS嵌入商业级工业软件，从而更好地发挥其服务实际生产过程的作用。

1.2 IPPS求解方法的研究概况

当前IPPS问题的求解方法主要集中在使用非线性方法实现工艺规划与车间调度阶段的信息交互，并采用智能优化算法对问题解空间进行搜索寻优。依据优化目标个数的不同，基于智能优化算法的IPPS求解方法又可以进一步分为单目标优化方法和多目标优化方法。

单目标IPPS问题的求解方法研究相对较为成熟，主要集中在基于蚁群算法的优化方法和基于遗传算法的混合算法设计。研究者在使用蚁群算法求解单目标IPPS问题时，会将蚂蚁探寻路径的过程与IPPS问题中柔性工艺路径的选择相结合。Leung等[14]构建了基于Agent系统的蚁群算法求解单目标IPPS问题。Zhang等[15]提出了一种构造式元启发规则与蚁群算法结合求解IPPS问题。王进峰等[16]及黄学文等[17]使用改进的蚁群算法求解单目标IPPS问题。在混合算法设计方面，一般采取的方法是设计有效的邻域结构嵌入全局搜索能力比较好的算法中进行局部搜索，从而对解空间进行充分探索。混合算法的代表为遗传算法与变邻域搜索算法的结合。Li等[18]设计了一种高效遗传变邻域混合算法求解单目标IPPS问题。此方法在工艺规划阶段采用一种三层编码方法，不仅能够对工艺规划阶段的工艺柔性、工序柔性及加工柔性进行比较完备的表达，同时也能够使用相对比较简单的交叉变异算子。在车间调度阶段考虑的车间类型为作业车间调度问题，将变邻域搜索嵌入遗传算法中，兼顾多种邻域结构的优点，充分探索问题解空间。工艺规划与车间调度阶段协同进化，在求解IPPS最大完工时间上取得了非常优异的计算结果。该方法被用来求解Kim提出的24个IPPS基本测试算例，其中19个解超过或等于当前已取得的最好解，在6个测试算例上发现了当前最好解。作者还将该算法应用于某非标机械制造厂中实际存在的IPPS问题，计算结果显示所提出算法能够有效解决实际工程案例。金亮亮等[19]将遗传算法与变邻域搜索有机结合，提出了一种文化基因算法求解单目标IPPS问题。Zhang等[20]提出了一种面向对象编码的遗传算法求解单目标IPPS问题。杜轩等[21]综合运用遗传算法、差分进化算法以及克隆邻域搜索算法的特点，设计了一种有效的多群体混合算法求解单目标IPPS问题。Zhang等[22]提出了一种扩展帝国竞争算法求解分布式单目标IPPS问题。Liu等[23]设计了求解单目标IPPS问题的量子启发式混合算法。文笑雨等[24]提出了一种两阶段混合算法求解单目标IPPS问题。Barzanji等[25]设计了基于逻辑的Benders分解方法求解单目标IPPS问题。

依据对多个目标处理方法的不同，多目标IPPS的求解方法可被分为两类，即非Pareto的方法和基于Pareto的方法。非Pareto的方法属于先决策后优化，即权重的确定代表了决策者的决策结果，权重的设定会对优化结果带来一定的主观影响因素。早期多目标IPPS问题的研究多采用加权法进行求解，近年来该方法使用较少。仅有Shokouhi[26]使用加权法和遗传算法求解多目标IPPS问题。近年来，更多的学者采用基于Pareto的方法对IPPS问题进行求解，以期能够减少主观决策对问题求解的影响，找寻兼顾多个优化目标的Pareto前沿。基于Pareto的方法属于后验法，即先优化再决策，优化的过程只与问题本身特性有关系，较少受到主观因素的干扰。Jin等[27]设计一种改进的多目标Memetic算法求解多目标IPPS问题。Zhang 等[28]研究了再制造环境下的IPPS问题，提出了一种基于仿真优化的多目标遗传算法。李言等[29]设计了基于NSGA-II的多目标IPPS求解方法。Mohapatra等[30]设计了一种精英受控的NSGA求解多目标IPPS问题。Luo等[31]提出了一种带免疫原理和外部存档策略的多目标遗传算法求解多目标IPPS问题。Manupati等[32]面向网络制造环境提出一种基于移动代理的方法同时优化IPPS的最大完工时间以及设备利用率。Milic等[33]提出了一种基于混沌理论的粒子群优化算法同时优化IPPS问题的最大完工时间、平均流程时间以及机器负载平衡。杜轩等[34]提出一种聚类差分进化算法同时优化IPPS问题的3个目标。Zhang等[35]设计出一种参数调整的增强蚁群优化算法同时优化最大完工时间、流程时间以及计算时间。

由于基于Pareto的方法能够更加客观反应问题特性，该方法是当前多目标IPPS求解方法的研究焦点。但是，当前大多数研究仅停留在使用基本的多目标进化算法框架进行多目标IPPS问题的求解，与单目标IPPS优化方法相比，多目标IPPS优化方法在利用问题领域知识方面略显不足。另外，在进化算法的研究领域，高维多目标进化算法已经在函数优化问题上取得了较为丰硕的理论成果[36]，但是在车间调度领域的应用还非常少。

2 不确定扰动下的IPPS问题研究现状

受信息技术的发展制约，早期的IPPS研究聚焦于静态生产环境，一般在提出模型时先假设不考虑实际制造过程中的不确定扰动因素，相关理论成果在实施应用时具有一定的局限性。随着近年来新一代信息技术的高速发展，制造系统实施运行中各环节的相关数据能够更容易地被采集以及存储，不同系统之间的数据也更容易进行互联互通，因此，越来越多的学者开始关注于不确定扰动下IPPS问题的研究。

Liu 等[37]考虑了新工件到达的不确定事件，设计了基于蚁群优化算法的动态IPPS求解方法。为应对机器故障和新工件到达的不确定性，Xia等[38]将混合算法与滚动窗口技术相结合求解动态 IPPS 问题。Yu等[39]提出了一种混合遗传粒子群优化算法求解动态IPPS问题，求解过程分为静态阶段和动态阶段，在动态阶段，针对机器故障这一车间运行动态事件，通过调整机器故障时间段内待加工工件工艺路线以应对动态事件。巴黎等[40]将不确定加工时间考虑到工艺规划与调度集成问题中。Jin等[41]提出一种文化基因算法求解带不确定加工时间的IPPS问题。Jin等[42]考虑最大完工时间，稳定性及拖期时间3个准则，提出一种求解动态IPPS问题的驱动重调度策略。Li等[43]采用区间数描述不确定加工时间，设计混合遗传粒子群优化算法对不确定IPPS问题进行求解。

表2 不确定扰动下IPPS问题应对策略及新增优化目标Table 2 Coping strategies and new optimization objectives of IPPS under uncertain disturbance

3 面向绿色制造的IPPS问题研究现状

绿色车间调度是绿色制造的重要环节，比传统调度问题的求解难度更高，更具学术研究意义和工程应用价值[4]。IPPS问题是一种扩展的车间调度问题，随着绿色制造的大力推进，绿色制造模式下IPPS问题的研究开始得到越来越多学者的关注。Li等[44]研究了面向可持续制造和再制造的IPPS模型。Dai等[45]建立了面向节能的工艺规划与车间调度集成模型，其中能耗指标包含制造系统中所有工作机器在生产和非生产阶段的总能耗。Zhang等[46]提出一种IPPS节能优化模型。刘琼等[47]提出了一种考虑碳排放量的IPPS模型。李聪波等[48]建立了面向能耗的分批IPPS模型。黄志清等[49]建立了工艺规划与车间调度的能量优化模型。李玲玲[50]、张漪[51]构建了IPPS与加工参数集成优化的模型。孟磊磊等[52]使用空闲能耗和空闲时间的不同建模思想构建了面向节能的IPPS模型。Jin等[53]采用基于网络图的混合整数线性规划模型构建了面向节能的IPPS模型。

在研究绿色制造模式下的IPPS问题时，不仅可以在车间调度环节通过改变工件在机器上的加工顺序以实现节能减排，还可以在工艺规划环节综合考虑可选加工工艺、可选加工机器以及工序加工序列等因素对于绿色指标的影响。因此，绿色IPPS问题的研究能够进一步发掘制造系统节能减排的潜力。对绿色IPPS问题进行研究的难点之一是如何构建合适的问题模型。上述面向绿色制造模式的IPPS问题研究大多数采取在建立模型时增加一个环境相关的目标函数，如能耗、碳排放等，建模方法相对比较单一。在已有绿色车间调度模型研究中，不仅仅采用增加绿色目标函数这一方法构建绿色车间调度模型，还有将能耗因素作为约束条件(如峰值能耗)以及将不超过截止完工时间作为约束来优化总能耗的方法来构建绿色车间调度模型。这些研究成果能够为绿色制造模式下的IPPS问题的研究提供新的思路。另一方面，由于绿色IPPS问题在进行求解时，需要同时兼顾经济指标和绿色指标，问题的解空间更加庞大复杂。绿色指标与经济指标之间呈现复杂的非线性关系，在进行优化求解时，对求解算法的设计提出了更高的要求。

4 研究展望

随着智能制造技术的发展，IPPS问题的研究迎来了新的机遇与挑战。未来对该领域的研究可从以下几个方面继续展开：

1)基于工艺规划和车间调度的层次关系构建有效集成模型。

IPPS问题涉及到工艺规划部门的决策者与车间调度部门的决策者以及企业上层管理部门的决策者。不同决策者因其面向的对象不同，进行决策时的侧重点也有所不同。工艺规划部门关注工艺编制的合理化与安全规范、工艺技术的改进以及标准化等工作；车间调度部门关注车间合理化派工，机器故障的实施监控与诊断等工作；企业上层管理部门直接与客户对接，更加关注于产品交货期与客户满意度等需求。不同决策者之间通常处于一种非合作的竞争关系，如果不能协调好各决策者之间的关系，就有可能出现企业生产无法顺利执行的不利局面。IPPS问题是一个典型的多决策者博弈问题。不同企业的工艺规划部门和车间调度部门职责和能力有所不同，决策者对于工艺规划和车间调度的重视程度也有所不同。但是，在对工艺规划和车间调度集成模型方面，现有研究大多数是将工艺规划和车间调度放在同一层次。如何从企业自身制造特点出发，结合制造系统柔性，评估工艺规划与车间调度在其进行集成优化时的主从关系具有非常重要的实际应用价值。比如，当企业更重于工艺需求，则工艺规划在集成优化中占据主导地位。当企业订单任务紧急时，车间调度在集成优化中应当占据主导地位。因此，对工艺规划和车间调度进行集成优化时，需要结合具体企业的实际生产能力和订单需求，研究能够揭示工艺规划和车间调度之间层次关系的有效模型。

2)揭示IPPS问题多个优化目标的复杂关系。

IPPS问题的优化目标往往并不是绝对意义上的矛盾冲突关系，在全局和局部都可能会存在线性或非线性的复杂制约关系，也可能会存在冗余目标。比如，在工艺规划阶段，工艺成本的降低与客户对于工艺设计的满意度之间并不是一种简单的线性关系，在一定程度上能够达到双赢，但是很多时候又是相互冲突的；最大完工时间的减少一般情况下会减少总流程时间，但是有可能会带来总流程时间的增加，从而影响到面向交货期的目标。另外，在工艺规划阶段决定的每个工件的加工时间最短有时能够带来车间调度总完工时间最短，但是当机器之间的负载平衡性没有有效考虑时，又会增加车间调度阶段的完工时间。绿色制造模式下，经济类的优化目标和环境类的优化目标之间也存在复杂的耦合关系。如果能够揭示IPPS问题多个优化目标之间的复杂关系，就可以为多目标优化方法的设计提供一定的先验知识，有助于提高算法性能。

3)基于问题领域知识的高效集成优化方法设计。

已有IPPS问题的研究中，大多数仅考虑同时优化3个以内的目标。从上述总结中可以看出，IPPS问题包含的优化目标非常多，远不止3个，属于高维多目标优化问题。与同时优化3个以内的多目标优化方法相比，高维多目标优化问题中优化目标数量多使得Pareto支配关系失效，优化目标之间制约关系复杂使得问题求解更为困难。由于IPPS问题工艺约束少，柔性大，与传统调度问题相比，IPPS问题解空间的冗余更大，IPPS高维多目标优化方法的研究极具挑战性。基于Pareto的多目标优化方法能够更加客观地反应问题本身的特性，因此是当前的主要研究方向。但是，当IPPS问题优化目标大大增多时，基于Pareto的多目标优化方法在非支配解排序方法，种群收敛性和多样性维护策略等方面会给算法的设计带来新的挑战，传统多目标优化方法无法有效地解决高维多目标IPPS问题，亟需深入挖掘IPPS问题的层次关联性、决策空间结构与目标空间特性，指导高效集成优化方法的设计。

4)基于数字孪生技术的IPPS动态调控方法研究。

IPPS问题本身因为考虑到制造系统的多种柔性因素，可以较好地应对生产中一些不确定扰动因素。可以考虑结合数字孪生技术，实时采集工艺规划与车间调度环节的产品、资源、物流与生产数据，利用搜集的数据统计加工时间不确定、交货期不确定、急件插入、机器故障等不确定扰动事件，归纳不确定扰动事件类型，分析不确定扰动事件对生产效率、碳排放和客户满意度的影响，确定不同不确定扰动事件的应对策略，对可选工艺计划、车间资源，以及在碰到突发事件时的再规划和再调度问题指标进行统计分析。从模型构建以及运作方法上及时响应突发事件，发挥IPPS兼顾多种工艺柔性的特点，探索不确定扰动下的IPPS问题动态调控方法，更好地发挥工艺规划与车间调度集成优化带来的优势。

总而言之，IPPS问题的研究对提高我国智能制造产业的管理水平、核心竞争力、促进其可持续发展具有重要意义，其理论价值与现实意义广阔。