智能制造系统中基于网络图拓扑的MILP工艺规划模型

工程7（2021）807研究智能制造-文章智能制造系统中基于网络图拓扑的MILP工艺规划模型刘启豪，李欣宇，高亮华中科技大学机械科学与工程学院，数字化制造装备与技术国家重点实验室，武汉430074阿提奇莱因福奥文章历史记录：收到2019年2021年3月21日修订2021年4月27日接受2021年5月5日网上发售保留字：工艺规划网络混合整数线性规划A B S T R A C T智能工艺设计是智能制造系统的重要组成部分，是连接产品设计和实际生产的桥梁PP是一个非确定性的多项式时间（NP）困难的问题，现有的数学模型不是制定在线性形式，他们不能很好地解决，以实现PP问题的精确解本文提出了一种新的混合整数线性规划（MILP）数学模型，该模型考虑了网络的拓扑结构和网络中代表一种或逻辑的或节点通过提出三种类型的优先关系矩阵，讨论了操作之间的优先关系此外，所提出的模型可以编程在常用的数学规划求解器，如CPLEX，Guidelines，等等，寻找最佳的解决方案，为大多数开放的问题。为了验证所提出的模型的有效性和通用性，五组数值实验进行了著名的基准。结果表明，该模型可以有效地解决PP问题，可以得到更好的解决方案比国家的最先进的算法。©2021 THE COUNTORS.Elsevier LTD代表中国工程院出版，高等教育出版社有限公司。这是一篇CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）中找到。1. 介绍智能制造涉及智能制造技术和智能制造系统[1智能工艺规划（PP）是最重要的智能制造技术之一，在智能制造系统中起着至关重要的作用[4，5]。PP可以有效缩短生产周期，提高产品质量，进而降低资源和能源的消耗[6]。因此，PP在工业应用中获得了相当多的关注。然而，由于PP内部广泛的灵活性，在实际生产场景中很难解决最佳工艺方案[7]。解决传统的PP问题通常涉及三个步骤：流程选择，资源分配和操作排序[5]。第一步是确定工艺选择，然后，可以确定工艺路线的长度，因为不同的工艺方法的操作数量不同。其次，资源的配置，包括机器和工具，应该是*通讯作者。电子邮件地址：lixinyu@mail.hust.edu.cn（X. Li）。为所有操作配置。对操作进行排序是获得遵守优先约束的可行工艺路线的最后一步也是最关键的一步[8]。例如，铣削和磨削必须安排在精铣和精磨操作之前，孔螺纹的攻丝必须在钻孔操作之后进行[9]。PP问题已被证明是非确定性多项式时间（NP）困难的[6，10]，这意味着仅依靠传统的梯度下降方法，图论方法或基于模拟的方法很难解决。因此，大多数研究者试图引入元分析[11]来研究PP问题。PP问题的主要研究方法包括遗传算法（GA）[7，12]、禁忌搜索（TS）[13]、粒子群优化（PSO）[8]、蚁群优化（ACO）[14]和蜜蜂交配优化（HBMO）[10]，这些方法旨在以较少的计算成本找到高质量的解在此背景下，尚未找到许多开放PP问题的最佳解决方案[8，15]。一个重要的原因是，最近的研究更多地关注提高智能算法的性能，而不是修改现有的算法。https://doi.org/10.1016/j.eng.2021.04.0112095-8099/©2021 THE COMEORS.由爱思唯尔有限公司代表中国工程院和高等教育出版社有限公司出版。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表工程杂志首页：www.elsevier.com/locate/engQ. Liu，X.Li和L.高工程7（2021）807808数学模型，特别是混合整数线性规划（MILP）数学模型[14]。一个有效的MILP模型可以用CPLEX、Guidelines等数学规划求解器求解，在一定条件下可以稳定地得到PP问题的最优解。然而，一个MILP模型的解决效果是高度相关的问题规模。一旦规模变大，模型的求解效果迅速恶化，甚至可能在较长的计算时间内找不到可行解[16]。因此，目前对PP的研究工作并不集中在MILP模型上。事实上这些模型将原始网络图转换为表格形式，以简化过程表示。这种转换在一定程度上改变了原有的工艺信息的网络。（关于这种情况的讨论见第3.3节。）此外，尽管存在可以避免上述情况的其他建模方法，但它们需要复杂的预处理，例如生成所有可能的处理操作的组合，以便消除和替换表示网络内的OR逻辑类型的OR节点[18]。这种预处理过程是复杂的，特别是，存在太多的或节点或复杂的拓扑结构将大大增加PP问题的复杂性和计算时间。为了填补最近报告的研究工作的空白，基于PP网络拓扑结构，提出了一种新的MILP模型本文的主要贡献如下：(1) 本文提出了一种新的基于OR节点的并行规划问题的MILP模型，该模型不需要任何特征转换或其他预处理。(2) 详细讨论了操作的优先关系，并给出了三种类型的优先关系矩阵来说明优先关系约束。(3) 在通用代数建模系统（GAMS）/ CPLEX求解器中编码，该MILP模型成功地为文献[8，15，16]中的开放问题找到了新的最优解。本文的其余部分组织如下。第二节介绍了相关的工作，第三节提出了模型，并详细讨论了上述相关分析第四通过几组对比实验验证了该模型的优越性。第5节提出结论，并概述今后的一些工作。2. 相关工作PP的相关工作可分为算法和数学模型两大类。Xu等人[6]和LeoKumar[4]都对PP问题提供了很好的评价。智能算法如GA、模拟退火（SA）算法、TS算法、PSO算法等已显示出足够的优越性，并在PP问题中得到了广泛的应用[6]。为了解决具有复杂棱柱部件的PP问题，Li等人[19]提出了一种包括GA和SA算法的良好混合算法。该混合算法采用基于备选路径间汉明距离的寻优策略，增强了算法的局部搜索能力。Hua等人[20]提出了一种基于GA的综合算法，用于搜索PP问题的全局或近全局最优解。Li等人[15]提出了一种有效的遗传编程（GP）算法，该算法对网络图中的OR节点分支执行遗传操作。考虑到刀具选择和进给方向等制造资源，Shin等人[21]提出了一种共生进化算法来优化三个目标，包括平衡机器工作负载，最小化零件移动和最小化刀具更换。Wang等人[22]提出了一种粒子群算法结合两种局部搜索策略来解决PP问题。随后，Li等人。[8]提出了一种改进的PSO来解决考虑机器之间传输时间的PP问题。Liu等人[14]将蚁群算法与问题的约束矩阵和状态矩阵相结合，并应用于求解两个棱柱形零件的PP问题。虽然智能算法在求解PP问题方面取得了一定的成果，但由于Meta启发式算法不能保证解的最优性，在现有的PP问题中，解的质量还有待进一步提高。此外，数学模型作为一种描述问题的方法，可以帮助研究者更深入、更透彻地理解和理解问题[23]。因此，对PP数学模型的研究具有重要意义。Floudas和Lin[24]在时间表示方法上分析了PP问题的几种混合整数规划（MIP）模型，并提出了几种有效的优化方法来提高模型的计算效率。鉴于PP和调度问题的复杂性，Li等[25]建立了一个将PP问题和车间调度问题集成的数学模型。Xia等人。[26]提出了一种基于特征的可重构PP问题的数学模型。类似地，基于特征，Jin和Zhang[16]建立了考虑机器之间的传输时间的PP的MILP模型。据我们所知，PP问题的数学模型始终是基于特征的[8，14，17]。虽然这种建模方法可以描述大多数类型的作业，但仍然不可避免地必须添加一些直接优先约束，这些约束在原始网络中不存在[16]。因此，网络图方法比基于特征的方法更能够描述不同的装配柔性提出了一种直接基于网络图拓扑结构的MILP模型，该模型可以描述PP的各种制造柔性，而不需要添加或省略任何约束。通过求解所提出的模型，成功地得到了一些著名的基准问题的新的最优解。3. 提出的PP3.1. 问题描述聚丙烯柔性的类型包括工艺柔性、设备选择柔性和操作顺序柔性。有几种方法来描述PP问题，如Petri网[27]，特征表[28]，AND/OR图和网络[29，30]。在图1中，表示了制造灵活性以网络图的形式。该网络图由五种类型的节点组成：起始节点是虚拟的，表示零件生产的开始;结束节点也是虚拟的，表示零件生产的结束中间节点包含三条信息：实心圆中的工序号、{ }中的替代机器号和[ ]中的相应加工时间。例如，中间节点6指示操作6可以在三个可选机器3、7和13中的任何一个机器上进行处理，所需的处理时间分别为44、48和49。论文中的时间单位与原始数据一样被省略。连接网络中节点对的箭头表示操作之间的优先关系约束[21]。例如，操作2和3之间的箭头声明操作2必须在操作3之前处理。没有箭头连接的操作之间没有固定的优先级约束。只有一个连接到OR节点的链路将Q. Liu，X.Li和L.高工程7（2021）807809×.¼.¼Fig. 1.灵活的工艺规划网络。OR1、OR2、JOIN 1和JOIN 2分别表示OR节点1、OR节点2、JOIN节点1和JOIN节点2。选定.链接中包含的操作与其他操作一起构成了该部分的可行操作组合[29]。带上菲格。 1为例：如果操作2？ 3在OR节点1和JOIN节点1之间被选择，并且如果操作7在OR节点2和JOIN节点2之间被选择，则完整可行过程路线之一是1？ 两个？ 三个？ 五个？ 六个？ 七个？ 九岁？10个。3.2. 操作之间的优先关系根据二元变量的定义，PP问题有三种建模方法[31]：这在当前文献中被广泛使用[24，34，35]。在本文中，建议的MILP模型的PP建立基于第三种方法，qjj，第一次。如图2、该部分可行的操作顺序为1？ 两个？ 三个？ 四个？ 五个？ 六个？ 七个？ 八个？9.第九条。 操作1在所有其他八个操作之前;因此，根据定义，q1 j= 1，其中j= 2，. . ，9.操作2在所有其他七个操作之前被处理，因此q2 j= 1，其中j= 3，. . ，9.矩阵Q=[ q j j j j]中的“1“的数目 图图3示出了从序列到Q矩阵的优先关系变换。对于已排序的序列，每两个操作具有顺序关系。因此，优先级关系可以由n n矩阵表示。Q矩阵包含了一个操作序列的所有优先关系。Q矩阵可以看作是操作序列优先关系的完全表达矩阵。通过观察和分析，CEMQ的特征约束可以归纳如下：(1) CEMQ的对角元素等于0：qjj¼0;8j10(2) 关于对角线对称的两个元素之和等于1：qjj0qj0j¼1;8j(3) 任意两个不同列中的元素之和不相等：Xqjj0JJhjt1;如果操作j在周期t0;否则qjt1;如果操作j是要处理的序列中的第t个操作，则为（1;如果操作j在操作j0之前处理由于PP问题的变量和约束条件较多，基于时间段的二进制变量h_（jt）在PP问题建模中很少被提及在现有文献中，定义qjt通过操作j的位置描述操作序列[16，32，33]，图二. 工艺计划网络。qjj0 ¼0;否则Q. Liu，X.Li和L.高工程7（2021）807810图三. 优先关系的转换。当量（1）表示优先关系只存在于不同的操作之间。由方程式（2），qjj= 1使qjj= 0，而qjj= 0使qjj= 1，因为两个操作之间只有一个当量因为列元素的和对应于在操作序列中唯一的位置，所以公式（3）Q矩阵包含操作之间的所有优先关系。根据相应的Q矩阵，可以快速、方便地判断一个序列是否满足网络中的优先约束。符号s j jj定义为表示图1中的优先约束。第二章：（1;如果根据网络，操作j应该在j00;否则相应的约束矩阵S =[s，j，j，j]如图2所示。 其中S矩阵中的每个“1”对应于网络中的箭头，表示优先约束。如果一个序列满足所有的优先约束，则它的CEMQ应该包含矩阵S中显示的所有优先值，可以用公式表示如下：qjj0 ≥sjj0;8j;j04矩阵S可以从网络图中生成，但矩阵Q是未知的，因为操作顺序尚未确定。因此，Eq。（4）可以视为约束。CEM Q中的“1“的数量然而，最少确定操作顺序所需的“1“的数量见图4。 网络中的优先约束和相应的矩阵S。sjj0 ¼Q. Liu，X.Li和L.高工程7（2021）807811矩阵为（n例如，为了确定序列1？ 两个？三个？ 四个？ 五个？ 六个？ 七个？ 八个？9，它只需要设置八个变量为“1”，即q12，q 23，q 34，q 45，q 56，q 67，q 78和q 89。从这一点来说，定义一个符号vjj是有帮助，其对应的ing矩阵V=[vjj]包含的变量个数最少，等于1。矩阵V可以被认为是矩阵V的精确表示矩阵（EEM）。序列的优先级关系，其中包含确切且最少数量的“1“。上述操作顺序的EEM V如图所示。 五、EEM矩阵也可以直接称为优先矩阵，因为它只包含了两个直接相邻的操作。根据直接的概率关系，通过顺序识别EEMV的元素来获得操作序列是简单的。EEM矩阵具有如下几个特征约束：(1) 在EEMV中等于1的变量的数量是（nXXvjj0 1/4n-1/5njj0(2) EEMV的每一行或每一列最多有一个等于1的元素：XVJJ0 ≤1;8j0≤6JXVJJ0 ≤1;8j≤70j图五. 序列的EEMV(3) 矩阵Q和矩阵V之间的关系表示如下：vjj0 ≤qjj0;8j;j0<$8μm矩阵V是矩阵Q的一种简化表示，两者都能确定唯一的运算序列。 然而，矩阵S不能确定一个唯一的操作序列，由于其不完全表示的优先关系 的 一 个 确 定 的 序 列 。 因 此 ， 本 文 将 矩 阵 S 称 为 部 分 表 示 矩 阵（PEM）。多个序列可以满足由S矩阵表示的优先约束。CEM Q、EEM V和PEM S如图所示。 六、3.3. 基于特征和基于网络的过程表示方法探讨在目前的文献中，所有的PP问题的数学模型是基于特征的。例如，在文献[8，16]中采用的实例在图7（a）中以特征表格的形式示出。 事实上，这个例子是从参考文献18中的例子推导出来的。[29]如图7（b）所示。因此，FIG.图7（a）和（b）示出了以两种不同的表示形式表示的相同实例。在特征表[8，16]中，特征F2、F5和F9具有替代操作或操作集，对应于网络图中的三个OR节点OR1、OR2和OR3。然而，在表格形式中，相同特征下的操作集受到在对应网络图中不存在的直接优先关系的约束。例如，如果为特征F2选择O4 然而，根据图7（b）的原始网络图，O5不必在O4之后立即处理。其结果是，可能会改变解空间，导致无法获得最优解。表1示出了通过使用GAMS/CPLEX求解器分别求解基于特征的模型和基于网络的模型而获得的两个最优解。括号中带数字下标的字母M表示分配的机器，在后续表格。从表1中可以看出，这两个序列之间的主要区别在于，通过基于网络的方法获得的序列不具有O4此外，通过基于网络的方法获得的356的生产时间优于通过基于特征的方法获得的357的值。因此，直接在网络基础上建立模型的方法要优于基于特征的方法。基于特征表示的过程灵活性通过特征的替代操作或操作集来实现。对于基于网络的表示，过程柔性通过选择OR节点的链接来表示链接是指连接到OR节点的箭头OR节点的每个链接见图6。三种类型的优先关系矩阵：（a）CEM Q，（b）EEM V和（c）PEM S。Q. Liu，X.Li和L.高工程7（2021）807812JJRLx¼。RL见图7。 同一实例的两种表示形式：（a）特征表格形式和（b）网络图。表1利用基于特征的模型和基于网络的模型得到了两个最优解基于结果的模型基于网络的模型优化工艺方案O7（M3）O9（M15）O7（M3）生产时间357 356对应于工艺灵活性的选择 图 8，按照从上到下和从左到右的顺序，OR节点及其链接如图所示进行编号。如果选择OR节点1的链路1另外，无论选择OR节点2的链路1还是2，都将不选择操作6和7。原因是，除了OR节点2之外，操作5、6、7和8由OR节点的链路2控制1. 由OR节点执行的选择仅在选择了该OR节点所在的链路时才有效引入一个二元参数wjrl来描述OR节点对运算的控制作用。参数w_jrl的定义如下所述：1;如果选择操作j0;否则第3.4节中建立的模型基于这两个变量url和xj以及一个参数wjrl。3.4. PP的数学模型所提出的MILP模型是基于优先级和OR节点的。大多数过程优化目标函数与时间相关[8]或与成本相关[14，18]。在本文中，以最小化生产时间为目标，机器之间的传输时间被考虑在模型中。布景，公司简介1;如果操作j由第r个OR节点0的第l个链路控制，则为模型的下标、参数和变量介绍如下（表3）。作为目标的总生产时间可以表示为：如下所示：对于图8中的示例，w_rl的对应值为如表2所示。minTT¼XMTjXXTjk·yjk9JJK因此，OR节点的控制功能可以归纳为：只有在操作j的所有控制链路都被选择的情况下，操作j才会被选择相反，只要操作j的控制链路之一未被选择，就不会选择操作j引入二进制变量url来描述选择链接，另一个二进制变量xj用于在右边，第一部分的Eq。（9）指总的传输时间，第二是总的处理时间。模型的约束显示如下：(1) OR节点控制约束：x≤M·。1-wΣþM·u;8j;r;lð10Þ描述操作选择状态。url和xj的定义具体如下：xj≥1-M·X Xwjrl· 1-url;8j11RL的url1;如果选择第r个OR节点的第l个链接，则为0;否则为Xurl¼1;8r12 mL..¼Q. Liu，X.Li和L.高工程7（2021）807813.ΣX xXX·¼8英寸Þ.- 是的ΣJj0J0jqjj0<$qj0j≤M·xj;8j;j0<$17<$2-xj-xj0 ·Mqj j0 ≥sj j0;8j;j0<$1 8<$等式（13）-（18）指优先关系中的约束。与Eqs不同，（1）当量（13）对应于Eq.（一）. 等式（14）和（15）对应于等式（2），在选择操作j和j′的条件在相同条件下，等式中的约束。（16）对应于Eq.（三）、至于EQ。（17），其含义是如果操作j未被选择，则概率关系Qjj和Qjjj在Eq. （18）保证所选择的操作序列服从优先约束。(3) EEMV和CEMQ约束：vjj0 1/4xj-119 mmXVJJ0 ≤1;8j≤20mm0jXvj0j≤1;8j<$21<$vjj0 ≤qjj0;8j;j0<$2 2<$由于矩阵V包含两个相邻操作之间的优先关系，因此可以容易地计算传输时间。方程中的约束条件（19）因为矩阵V是从矩阵Q导出的，所以等式（22）介绍。(4) 机器选择约束：zjk yjkxj;j23K见图8。 一个控制性讨论的例子。在Eq.（10）表示“不选择”条件：只要操作j的所有控制链路中的一个未被选择，在Eq. （11）是“选定”条件。在Eq. （12）意味着只能选择OR节点的一个链路。(2) 优先约束：qjj¼0;8j13qj j0<$qj0j≤1 <$M·。2-xj-xj0mm;8jqj j0<$qj0j≥1-M·.2-xj-xj0mm;8jM.2-xj-xj0Xqj00j-Xqj00j0j00j00当量（23）表示只有一台机器可以被分配给所选的操作，并且不需要分配任何机器用于重复操作。(5)传输限制：M Tj≤T Kkk0<$M·。1-vjj0M·.2-yjk-yj0k0;8j;j0;k;k024MTj≥TKkk0-M·1-vjj0-M·2-yjk-yj0k0 ;8j;j0;k;k02 5等式（24）和（25）制定操作的传输时间j从当前加工机器到下一台机器。4. 实验与讨论为了验证所提出的模型，五组对比实验的基础上著名的基准。所有的实验都直接与其他报道的方法的结果进行了比较。在3.7 GHz和16 GB随机存取存储器（RAM）的个人计算机（PC）上，将所提出的模型编码在GAMS中，并使用求解器CPLEX来求解PP问题。本文还引入了间隙（%）参数间隙值表示获得的解;它的定义是（BF表2参数wjrl.r和l的值WJRLj= 1j= 2j= 3j= 4j= 5j= 6j= 7j= 8r= 1，l= 101110000r= 1，l= 200001111r= 2，l= 100000100r= 2，l= 200000010Q. Liu，X.Li和L.高工程7（2021）807814表3PP数学模型的集合、下标、参数和变量的定义项目定义集和下标j，j=运算，j = 1，2，. . ，n，其中n是操作的总数k，k=机器，k = 1，2，. . ，K，其中K是机器的总数r个OR节点，r = 1，2，.. . ，R，其中R是OR节点l链路，l = 1，2，.. . ，L，其中L是一个节点的链路总数sjj网络中的优先约束：如果操作j应该在操作j之前处理，则sjj= 1;否则，sjj=0zjk1，机器k对于操作j是可选的; 0，否则wjrl1，操作j由第r个OR节点的第l个链路控制;否则为0Tjk在机器k上操作j从机器k到k的传输时间<$M一个足够大的正数变量qjj<$1，操作j在操作j之前处理;0，否则vjj<$1，操作j直接在操作j之前处理<$;0，否则yjk1，操作j在机器k上处理; 0，否则url1，选择第r个OR节点的第l条链路; 0，否则xj1，选择工序j处理零件;否则为0MTj从机器处理工序j到下一台机器处理该工序的传输时间TT总生产时间目标函数的解，BP是下界。“间隙”值越小，当前解决方案越接近最优解决方案。GAMS/CPLEX的计算时间设定为3600 s。如果在时间限制内没有找到最优解，则计算将终止，并输出最佳已知解。实验1、2、4和5中的情况所采用的机器之间的传输时间示于表4[8，18]中。4.1. 实验1实验1中的三种情况来自Jin和Zhang[16]，其中应用类似动态规划（DP）的启发式表5中给出了通过所提出的MILP模型和DP类启发式获得的结果。通过MILP方法得到的情况1的生产时间为357，这优于DP类启发式提供的360。此外，所有的三个最优解的情况下，找到了MILP模型。4.2. 实验2实验2中的四个案例来自不同的出版物：案例1来自Zhang和Nee[36]，案例2麦克马洪[37]。这些案件的详细资料可在相应的文件中找到。在李等人的工作中给出了一个改进的PSO算法的计算结果[8]的一项建议。改进的粒子群算法是求解组合优化问题的一种先进算法。PSO和MILP之间的比较如表6所示。可以观察到，MILP模型在以下情况下获得更好的解：1.此外，通过MILP模型方法在短的计算时间内（小于1秒）找到了情况2-4的最优解4.3. 实验3实验3中的两种情况采用Li等[15]，机器传输时间矩阵见表7。这两个案例采用了Li等人[15]的相同部分。这两种情况之间的唯一区别是，在情况2中假定机器2发生故障。 比较结果列于表8中。GP算法和MILP模型都能找到这两个实例的最优解4.4. 实验4实验4中的17个案例采用了著名的Kim数据集[29]，该数据集由18个部分组成，比较计算结果来自参考文献[1]。[8]的一项建议。由于文献[1]第4部分的数据存在一些问题，因此，本文对文献[1]第4部分的[8]这里没有选择。表9给出了改进的PSO算法、简单的GA和简单的SA得到的结果。在合理的计算时间内，所提出的MILP模型可以找到17个情况下的13个对于未找到最优解的情况，MILP模型仍然获得了与其他算法相似的更好的解，例如情况3，6，12和15。4.5. 实验5实验5中的11种情况采用另一个著名的Shin基准[21]，比较计算结果来自Li等人。[8]的一项建议。由于文献[1]中某些部分的数据存在问题[8]，11部分（省略部分9，10，12，13、15、17和18）。表10中给出了通过改进的PSO算法、简单GA和简单SA获得的解决方案。在合理的计算时间内，所提出的MILP模型可以从11个实例中找到9个最优解。对于未找到最优解的情况，MILP模型仍然得到较好的解，如情况3。表4传输时间矩阵[8，18]。机机1234567891011121314151057910117614131210569250345727647121078373065437243568949460446741012131415165105540101278910121110861174410044556767877236124056667778867777450423424391462485640574768101344109562508101214711127312106637807101410121012513127744107010121013510614116727121010088146781510774614141280915989168883871010890Q. Liu，X.Li和L.高工程7（2021）807815表5实验1的比较结果。情况[16]第十六话MILP1工艺计划生产时间O12（M5）O9（M15）O7（M3）357a计算时间-3546.74间隙-0%的百分比2工艺计划生产时间O13（M1）O9（M1）222O13（M1）O7（M1）222a计算时间-12.16间隙-0%的百分比3工艺计划生产时间O1（M2）212O1（M2）212a计算时间-0.44间隙-0%的百分比a表示找到了最佳解决方案。表6实验2的比较结果。情况改进的PSO[8]MILP1工艺计划客观价值O12（M4）O9（M1）359O16（M4）O10（M2）358计算时间-3600.00间隙-4.71%2工艺计划客观价值O1（M4）O13（M4）O16（M4）O1（M4）O10（M4）O13（M4）计算时间-0.20间隙-0%的百分比3工艺计划客观价值O1（M4）O6（M4）O1（M4）O10（M4）计算时间-0.44间隙-0%的百分比4工艺计划客观价值O16（M4）O11（M4）187O16（M4）O9（M4）187a计算时间-0.39间隙-0%的百分比a表示找到了最佳解决方案。表7机器之间的传输时间机机123456789101058121546101318250371064610133830471064610412740314106465151073018121064646101418058121576461012503710810646108304891310646127404101813106415108404.6. 讨论所提出的MILP模型在可接受的计算时间内获得了37个实例中的28个最优解。MILP模型找到的解决方案优于高性能启发式[16]和元启发式算法[8，15]。实验4和5在两个广泛使用的基准测试[21，29]上进行，较好的结果表明所提出的模型的优越性如表11所示，所提出的模型包含四种类型的下标，即操作、机器、OR节点和链接，而参考文献[16]中报告的模型包含六种类型Q. Liu，X.Li和L.高工程7（2021）807816下标，即特征、操作集、操作、机器、位置和地点。与文献[16]中提出的模型相比，所提出的模型中的下标更少，使得计算更有效。此外，基于OR节点的建模方法使所提出的模型更通用，以解决不同类型的PP问题。这就是为什么大多数最佳表8实验3的比较结果。情况GP[15]MILP1工艺计划目的O1（M2）213O1（M2）213a值计算-0.16时间间隙-0%的百分比2工艺计划目的O10（M9）224O10（M8）224a值计算-0.13时间间隙-0%的百分比a表示找到了最佳解决方案。可以得到两个金[29]和申[21]基准5. 结论和今后的工作考虑到网络图的拓扑结构，提出了一种新的基于OR节点的MILP数学模型。首先，针对操作之间的优先关系，引入了三种优先矩阵。其次，为了更好的通用性，引入了wjrl、url和xj来描述OR节点的控制功能。最后，在数学规划求解器CPLEX中对所提出的MILP模型进行了编码，并在公共基准上进行了测试。大量的对比结果验证了该模型的正确性和优越性本文首次提出了一种基于OR节点的建模方法，为PP问题及其扩展研究提供了新的视角。文中对三个优先矩阵的分析也揭示了操作排序子问题的本质，有利于PP问题的进一步研究。然而，该PP模型的研究仍存在一定的局限性。少数情况下无法找到最优解，计算效率也不总是令人满意，这意味着所提出的方法可以进一步改进。为进一步的研究工作，迫切需要一些简化和加速策略。表9实验4的比较结果。情况客观价值间隙计算时间SAGAPSOMILP1303303303292a0%的百分比0.082359359359351a0%的百分比191.503502502498486百分之四十五点五3600.005314314314280a0%的百分比26.456409409408399百分之四十点五3600.007304304304304a0%的百分比27.028358358358353a0%的百分比63.449393392391391百分之三十八点一3600.0010264264264264a0%的百分比1.2711271271271264a0%的百分比22.2412442442442433百分之三十四点九3600.0013216216216215a0%的百分比10.6914269269269244a0%的百分比56.77153583573573535.1%3600.0016248248248244a0%的百分比3071.2817314314314300a0%的百分比3600.0018361361360356a0%的百分比3600.00a表示找到了最佳解决方案。表10实验5的比较结果。情况客观价值间隙计算时间SAGAPSOMILP1267267267266a0%的百分比19.552165165163162a0%的百分比30.063299297296268百分之三十三点七3600.004268268267267百分之二十点二3600.005204204204199a0%的百分比463.206204204204189a0%的百分比268.337137137137116a0%的百分比0.948181181181178a0%的百分比0.2011151150149149a0%的百分比69.8814120120120120a0%的百分比11.0616170167167167a0%的百分比620.38a表示找到了最佳解决方案。Q. Liu，X.Li和L.高工程7（2021）807817表11模型的下标下标定义MILP模型j、j.业务k，k机器rOR节点l友情链接参考文献中报告的模型[16个]i，i特点j，j操作集k、k业务l，l机器rOR节点h地点，可分配确认本研究得到了国家自然科学基金（51825502和51775216）和华中科技大学学术前沿青年团队计划（2017QYTD04）的部分资助。遵守道德操守准则刘奇浩、李新宇和高亮声明，他们没有利益冲突或财务冲突需要披露。引用[1] 周军，李平，周勇，王宝，臧军，孟立.迈向新一代智能制造。工程2018;4（1）：11-20.[2] ZhongRY，Xu X，Klotz E，Newman ST. 工业4.0背景下的智能制造：综述。Engineering 2017;3（5）：616-30.[3] Zhou J，Zhou Y，Wang B，Zang J.新一代智能制造背景下的人-网-物系统（HCPS）。工程2019;5（4）：624-36。[4] Leo Kumar SP.人工智能系统在工艺规划和制造中的应用现状。Eng Appl ArtifIntell2017;65：294-329.[5] Miljkovic 'Z，Petrovic' M.改进多目标粒子群优化算法在柔性工艺规划中的应用。IntJComput Integrated Manuf 2017;30（2-3）：271-91.[6] 徐霞，王磊，纽曼，ST。计算机辅助工艺设计- - Int J Comput IntegratedManuf2011;24（1）：1-31.[7] 李新，高立，潘清，万立，赵康明。一种有效的混合遗传算法和可变邻域搜索算法在包装机车间集成工艺规划和调度。IEEE Trans Syst Man Cybern Syst 2019;49（10）：1933-45.[8] 李X，高玲，文X.一种高效的改进粒子群优化算法在工艺规划中的应用。Int J AdvManuf Technol 2013;67（5-8）：1355-69.[9] 甘佩英，李康生，张永芳.基于分枝定界算法的塑料注射模架工艺设计系统。国际先进制造技术杂志2001;18（9）：624-32.[10] 文X，李X，高磊，桑华.工艺规划问题的蜜蜂交配优化算法。J Intell Manuf 2014;25（3）：459-72.[11] Zhang J，Xiao Mi，Gao L，Pan Q.一种求解工程优化问题的新型元启发式算法。应用数学模型2018;63：464-90。[12] 刘强，李新，高莉，李英.集成工艺设计中一种新的编码和解码方法的改进遗传算法和调度问题. IEEE Trans Cybern. Epub 2020 Oct15.[13] Li WD，Ong SK，Nee AYC.基于约束的禁忌搜索方法优化工艺计划。Int J ProdRes 2004;42（10）：1955-85.[14] 刘X，易H，倪Z.蚁群优化算法在工艺规划优化中的应用。J Intell Manuf 2013;24（1）：1-13.[15] 李晓艳，邵晓艳，高磊.基于遗传规划的柔性工艺规划优化。 Int J Adv ManufTechnol 2008;38（1-2）：143-53.[16] 金丽，张春. 从一个新的角度看工艺规划与能耗降低优化：数学建模与类动态规划启发式算法。IEEE Access2019;7：7381-96.[17] 姜智，姜亚，王勇，张宏，曹宏，田刚。粗糙集与范例推理混合之再制造制程规划方法。J IntellManuf 2019;30（1）：19-32.[18] 金丽，唐清，张春，邵晓，田刚. 用于集成工艺规划和调度的更多MILP模型。Int JProd Res 2016;54（14）：4387-402。[19] LiWD，Ong SK，Nee AYC. 基于混合遗传算法和模拟退火算法的棱柱形零件工艺方案优化。Int J ProdRes 2002;40（8）：1899-922.[20] 华刚，周X，阮X.基于遗传算法的棱柱形零件加工方案选择与工序排序优化综合方法。Int J AdvManuf Technol 2007;33（5-6）：594-603.[21] Shin KS，Park JO，Kim YK.基于共生进化算法的柔性制造系统多目标工艺规划。Comput Oper Res2011;38（3）：702-12.[22] 王永芳，张永芳，傅俊华.基于混合粒子群的工艺规划优化方法。Int J Prod Res2012;50（1）：277-92。[23] Shabaka AI，ElMaraghy HA.可重构制造系统中最优工艺计划的生成模型。 Int JComput Integrated Manuf 2008;21（2）：180-94.[24] Floudas CA，Lin X.过程调度中的混合整数线性规划：建模、算法与应用。AnnOper Res 2005;139（1）：131-62.[25] 李X，高莉，邵X，张春，王春. 集成工艺规划与调度的数学建模与进化算法。Comput Oper Res 2010;37（4）：656-67.[26] 夏Q，艾蒂安A，丹坦J，西亚达特A.新制造模式下零件多样性的可重构加工工艺规划：定义、模型与框架。计算机工业工程2018;115：206-19。[27] LeeK，Jung M. Petri网在柔性工艺规划中的应用计算机工业工程1994;27（1-4）：505-8.[28] SormazD，S