首页 > 行业资讯 > 华中科技大学李新宇研究团队：基于网络图拓扑结构的MILP模型求解智能制造系统中的工艺规划问题丨Engineering

华中科技大学李新宇研究团队：基于网络图拓扑结构的MILP模型求解智能制造系统中的工艺规划问题丨Engineering

时间：2022-12-27 来源： 浏览：

华中科技大学李新宇研究团队：基于网络图拓扑结构的MILP模型求解智能制造系统中的工艺规划问题丨Engineering

原创 刘齐浩等 Engineering
Engineering

engineering2015

《Engineering》是中国工程院院刊主刊，工程类综合性期刊，旨在为全球提供一个高水平的工程科技重大成果发布交流平台，报道全球工程前沿，促进工程科技进步，服务社会、造福人类。中国科技期刊卓越行动计划领军期刊。 中英文出版，全文开放获取。

收录于合集

本文选自中国工程院院刊《Engineering》2021年第7卷，原文出自：A Novel MILP Model Based on the Topology of a Network Graph for Process Planning in an Intelligent Manufacturing System

引言

智能工艺规划是智能制造系统中的重要组成部分。从制造流程角度出发，工艺规划（process planning, PP）连接着产品设计和实际生产，有着承上启下的关键作用。PP属于非确定性多项式时间困难（NP-hard）问题，现有的问题模型都是非线性形式，因此不能够通过求解现有模型来得到问题的精确解。从工艺网络图的拓扑结构出发，华中科技大学李新宇研究团队提出了一个全新的混合整数线性规划（mixed-integer linear programming, MILP）数学模型，并通过三种优先关系矩阵讨论了网络图中工序的优先关系。该模型能够凭借常用的数学模型求解器，如CPLEX、Gurobi等，来搜寻并获得大部分算例的最优解。该模型通过在5组公开的著名数据集上的测试，证明了其通用性和有效性。实验结果有力地说明了所提模型能够有效地解决工艺规划问题，并获得比当前最先进算法更好的解。

智能制造包含智能制造技术和智能制造系统。 智能工艺规划（process planning, PP）属于重要的智能制造技术，在智能制造系统中扮演着重要的角色。PP能够有效地缩短生产周期，提高产品质量，并进一步降低资源和能源的消耗。因此，PP在工业应用与研究中获得了较多的关注。然而， 因为PP问题内部存在着大量的柔性，导致在实际生产场景中很难得到最优的工艺规划路线。
解决传统的PP问题通常需要三个步骤：工艺选择、资源分配和工序排序。 通过第一步的工艺选择来确定不同加工特征所需要的工艺及工序，并基本确定工艺路线的总长度。然后，通过分配机器、刀具等资源，来确定各工序的加工资源分配，预获取相关加工参数，如加工时间等。最关键的工序排序一般是最后执行，且排序过程必须遵循该工件工艺网络图中的优先关系约束。例如，粗铣工序和粗磨工序必须安排在精铣工序和精磨工序之前执行，镗孔工序必须排在钻工工序后。
PP问题已经被证明是非确定性多项式时间困难 问题 （nondeterministic polynomial-time-hard, NP-hard），这也意味着仅仅依靠传统的梯度下降法、图论法和仿真方法很难实现PP问题的求解。因此，多数研究者试图引入元启发式算法来求解PP问题。当前主要的求解方法包括遗传算法（genetic algorithm, GA） 、禁忌搜索算法（tabu search, TS）、粒子群优化算法（particle swarm optimization, PSO）、蚁群优化算法（ant colony optimization, ACO） 和蜜蜂配合优化算法（honey-bees mating optimization, HBMO）。这些算法能够在较短时间内获得近优解，更侧重算法的求解效率而不是解的最优性。
在此研究背景下，大部分公开PP问题的最优解至今还未找到。 其中一个重要的原因是当前研究更多关注的是如何提高智能算法的性能，而不是去研究问题的数学模型，尤其是混合整数线性规划（mixed- integer linear programming, MILP）模型。有效的MILP模型能够通过数学规划求解器求解，如CPLEX、Gurobi等，并在一定条件下稳定地获得最优解。但是，模型的求解效率与问题的规模相关，随着问题规模的逐渐增大，模型的求解效率会迅速降低，甚至在相当长的计算时间内无法获得可行解。这也是当前PP的研究重点不在模型上的重要原因。此外， 当前PP的MILP研究还处于一种“妥协”状态，即当前模型都是基于工艺特征建立的 。这种类型的模型通过将原始工艺图转换成工艺特征表来简化表达，但是这种转化会改变工艺网络图的原始信息，甚至改变原问题的解空间结构而导致最优解的丢失。当然， 也有一些建模方法能够规避上述情况的发生，但它需要复杂的前序处理操作，而当工件的工艺网络图较为复杂时，这种前序处理操作会非常繁琐费时 。
为了填补研究工作的空白， 华中科技大学李新宇研究团队提出了一个全新的基于PP网络图拓扑结构的MILP数学模型 ，其主要研究贡献如下：
（1）与现有研究中的模型相比，本研究所提的基于网络图OR节点的MILP模型不需要任何工艺特征转换或前序处理操作。
 
（2）本研究详细讨论 了工序的优先关系 ，并提出了三种优先关系模型来分析论述工序的优先关系约束。
（3）通过通用代数建模系统（general algebraic mode-ling system, GAMS）调用CPLEX求解器对所提模型进行求解，成功得到了现有文献中大部分开放问题的最优解。
实验比较结果验证了所提模型的正确性和优越性。 本研究首次提出了基于OR节点的建模方法，为PP问题研究展示了新的思路（图1）。此外，本研究对三个优先矩阵的分析也揭示了工序排序子问题的本质，有利于进一步理解PP问题。然而， PP模型的相关研究仍存在一些局限性，即少数情况下无法找到最优解，且计算效率有时也不尽如人意。 这意味着本研究所提出的方法还可以进一步改进，模型的简化和加速方法是未来研究工作的重点之一。

图1. OR节点控制功能的讨论示例。

关键词：智能工艺规划；工艺网路图；混合整 数线性规划；CPLEX

扫二维码 | 查看原文

原文链接：http://www.engineering.org.cn/ch/10.1016/j.eng.2021.04.011

以上内容来自：Qihao Liu, Xinyu Li, Liang Gao .  A Novel MILP Model Based on the Topology of a Network Graph for Process Planning in an Intelligent Manufacturing System  [J]. Engineering, 2021, 7(6): 807-817.

版权：如无特殊注明，文章转载自网络，侵权请联系cnmhg168#163.com删除！文件均为网友上传，仅供研究和学习使用，务必24小时内删除。
相关推荐
热门信息