引用本文

 

罗智勇, 王静远, 谢志强, 孙广路, 杨旭. 三层虚拟工作流模型的非线性制造工艺多目标优化算法研究. 自动化学报, 2022, 48(3): 896−908 doi: 10.16383/j.aas.c190090

Luo Zhi-Yong, Wang Jing-Yuan, Xie Zhi-Qiang, Sun Guang-Lu, Yang Xu. Multi-objective optimization algorithm for non-linear manufacturing process based on three-tier virtual workflow model. Acta Automatica Sinica, 2022, 48(3): 896−908 doi: 10.16383/j.aas.c190090

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190090?viewType=HTML

文章简介

关键词

工作流, 制造工艺, 优化调度, 虚拟技术, 生产质量

摘   要

时间、生产质量和成本是加工制造中相互制约的重要参数, 平衡此参数使制造工艺最优是一个NP (Non-deterministic polynomial)难题, 对此出现了许多优秀的调度方法. 然而这些方法的优化对象均为线性工艺, 对于普遍存在的非线性工艺却无法调度优化. 针对此不足, 本文以非线性工艺为优化对象提出了三层虚拟工作流模型Three-VMG (Three-virtual model graph)及其优化算法Three-OVMG (Three-optimal virtual model graph). 该模型和算法首先建立非线性工作流, 采用虚拟技术寻找虚拟结点进行重构, 将其改造为虚拟线性工作流; 其次结合工艺特点对模型进行分段, 采用逆向分层串归约来实现段内最优解, 采用累积最优解来衔接各段间的值; 最后根据优化结果自顶向下完成各层资源的优化调度. 实验表明, 该过程较传统时间最小化优化调度算法具有显著的优化效果, 其性能及可操作性也能满足工程要求.

引   言

伴随着第四次工业革命的步伐, 中国的制造业已经进入供给侧改革和产业升级的关键时期. 产品的制造由传统的简单线性工艺粗加工逐渐向现代的复杂非线性即反馈工艺细加工转变, 其制造过程更具复杂性、多变性和高效性等特点. 复杂产品的非线性细加工涉及生产车间、工艺设计及调度等多部门的协同控制, 其过程具有反复性, 必将产生大量的动态信息, 若不能及时优化这些信息势必会降低产品的竞争力. 提高产品的竞争力, 其核心是解决制造工艺的多目标动态优化问题. 生产时间、产品质量和费用成本是制造工艺的重要参数, 如何动态平衡这些参数使其最优本身就是一个NP (Non-deterministic polynomial)难题, 若增加工艺的多次反馈, 即非线性等因素, 则其优化过程将变得更加困难. “中国制造2025” 和“新一代人工智能” 为复杂产品非线性工艺多目标优化带来了机遇和指明了方向. 智能制造只有在充分融合非线性生产工艺的特点和多目标要求的约束下, 将人工智能、云计算、建模仿真和优化控制等信息处理技术与具体的生产资源相结合, 开发出有效的智能优化调度算法, 才可能使制造业实现跨越式的发展, 满足时代的要求. 科学工作流以其具备建模仿真能力强、资源参数量化准确、智能算法及优化调度易开发等特点, 使其在智能制造领域中具有独特的优势. 因此, 研究如何利用科学工作流实现非线性制造工艺的多目标优化调度具有非常重要的理论和现实意义.

近些年, 将工作流技术应用在线性生产工艺的多目标优化调度, 国内外学者进行了一定的研究. Arabnejad 等面向服务计算, 使用服务质量(Quality of service, QoS)付费的量化约束, 提出了一种异构预算约束调度算法, 该算法可以保证在用户指定的预算范围内执行成本, 并最大限度地缩短用户应用程序的执行时间, 从而较好地完成了制造工艺异构系统的多目标任务优化调度; Lv 等在分析了产品制造工艺流程的制约关系后, 提出了一种工作流优化模型, 该模型可进一步缩短制造工期, 使工艺达到最优, 从而提高了产品竞争力; Mollajafari 等为解决云制造时间成本最优问题, 利用云计算和遗传算法等技术提出了一种新的基因型到表型映射的工作流调度算法, 该算法利用设定的资源调度代价函数有效地解决了限定时间下成本最优的问题, 随后验证了该算法的收敛速度等性能; Koch 等为解决医用模型制造工艺中的磨削精度和可靠性等问题, 通过分析铣削的铸造数据集与主参考数据集的映射变化规律, 提出了一种数字工作流铣削模型, 统计分析发现该模型可有效地解决医用模型制造的多目标动态调度问题; Kianpisheh 等将约束工作流与蚁群算法相结合, 通过定义工期和成本因素变量完成了对云制造工艺的优化调度; Chirkin 等为解决工作流执行时间估计中的常见问题, 提出了一种考虑工作流组件及其运行复杂性和随机方面的解决方案, 该方案将制造工艺参数进行双重随机表示, 并使用特性/分布函数简化了工作流图, 提高了多目标平衡算法的性能和优化效果; Roberts 等为动态平衡危险复合无菌产品的生产时间、员工安全感和工作满意度等参数, 提出一种基于质量约束的辅助工作流系统模型, 该模型限定生产质量, 并根据员工匿名的在线调查动态修改模型参数使其达到最优, 从而有效地解决了生产工艺多目标平衡问题; Lucas 等通过工序上下层之间的关系建立了基于事件的工艺工作流模型, 通过所提出的相关公式完成了对制造系统的优化调度问题; Stender 等为解决不同条件下制造工艺质量提升的问题, 提出了一种有限元分析工作流模型, 该模型可完成热条件影响下制造工艺时间质量的优化调度问题; 敬石开等为解决云制造工艺多服务平衡可靠性等问题, 提出了一种离散粒子群智能优化工作流多目标调度算法, 该算法通过不断优化云制造工艺参数, 并根据智能算法的语义分析实现多服务匹配, 从而确保了云制造多服务选择的可靠性问题; 张玺等采用人工智能理论提出了一种模糊Petri网工作流模型, 对制造车间在不确定环境下的制造工艺进行了资源重调度优化, 实现了时间和成本的动态平衡; 张萌等为更好地解决制造工艺服务级别优选难的问题, 提出了基于工作流的限定区间多目标优化调度算法, 该算法将制造工艺区分成若干个区间, 根据各区间的特点使用非支配排序改进型遗传算法对其进行局部优化, 通过处处选取局部最优解完成整体优化, 从而实现多目标调度的目的.

上述研究成果对于优化线性生产工艺的多目标动态平衡具有一定的先进性. 然而, 生产工艺错综复杂, 尤其是某些工艺具有非线性特点, 即反馈生产工艺. 对于非线性工艺进行多目标多因素的优化调度, 现有的研究成果无法完成. 另一方面, 非线性制造工艺在生产企业中普遍存在, 企业急需对这类工艺进行优化调度. 本文正是为解决非线性工艺优化调度问题而展开研究的, 并在以往研究的基础上, 结合非线性制造工艺特点, 考虑制造时间、质量和费用成本这些参数的制约关系, 采用虚拟技术提出一种三层虚拟工作流模型Three-VMG (Three-virtual model graph)及其优化调度算法Three-OVMG (Three-optimal virtual model graph). 该模型和算法的主要思想是首先建立非线性生产工艺的抽象结点层、虚拟工作流模型层和同构转换层, 其次采用分段优化同构转换层的工艺参数, 并由顶层向底层逐级传递优化解, 最终实现工艺资源的动态平衡, 为制造企业提供科学的决策依据和改进方案. 由于模型采用虚拟技术, 将工艺中的反馈工序结点虚拟为单个结点, 从而将非线性工艺改造为虚拟线性工艺, 实现了其多目标的优化调度. 因此, 该模型可用于解决非线性即反馈制造工艺的多目标优化调度问题. 此外, 该模型的三层结构, 即底层工艺资源抽象层、中层结点工艺偏序层和顶层虚拟组合层, 每层分别代表制造企业的不同关注面, 先由下而上进行抽象优化形成决策, 再由上而下传达决策修改配置参数. 因此, 这种三层模型较其他优化模型更具有建模清晰、高效快捷和简单明了等优势, 值得推广.

图 1  虚拟歧途径的识别过程

图 4  工作流Three-VMG的调度过程

作者简介

罗智勇

哈尔滨理工大学计算机科学与技术学院教授. 主要研究方向为企业智能计算与调度系统, 数据处理, 网络优化. 本文通信作者.

E-mail: luozhiyongemail@sina.com

王静远

哈尔滨理工大学计算机科学与技术学院硕士研究生. 主要研究方向为企业智能计算与调度系统.

E-mail: 727201874@qq.com

谢志强

哈尔滨理工大学计算机科学与技术学院教授. 主要研究方向为企业智能计算与调度系统, 数据处理, 网络优化.

E-mail: xiezhiqiang@hrbust.edu.cn

孙广路

哈尔滨理工大学计算机科学与技术学院教授. 主要研究方向为计算机网络与信息安全, 机器学习与智能信息处理.

E-mail: guanglu_sun@163.com

杨   旭

哈尔滨理工大学计算机科学与技术学院硕士研究生. 主要研究方向为企业智能计算与调度系统.

E-mail: yangxu_hust@sina.com

相关文章

[1]  李慧芳, 黄姜杭, 徐光浩, 夏元清. 基于多维度特征融合的云工作流任务执行时间预测方法. 自动化学报.

http://www.aas.net.cn/cn/article/id/5c0f8248-128b-40e9-96f8-342ee9ab40da?viewType=HTML

[2]  刘军, 任建华, 冯硕. 一种规模化混杂生产线缓冲区容量优化分配技术. 自动化学报. doi: 10.16383/j.aas.c200578

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200578?viewType=HTML

[3]  桂卫华, 岳伟超, 谢永芳, 张红亮, 阳春华. 铝电解生产智能优化制造研究综述. 自动化学报, 2018, 44(11): 1957-1970. doi: 10.16383/j.aas.2018.c180198

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c180198?viewType=HTML

[4]  汪恭书, 刘静宜, 唐立新. 连铸-轧制混流生产模式下轧批调度问题的分支-定价算法. 自动化学报, 2017, 43(7): 1178-1189. doi: 10.16383/j.aas.2017.c160316

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160316?viewType=HTML

[5]  安玉伟, 严洪森. 柔性作业车间生产计划与调度集成优化求解策略. 自动化学报, 2013, 39(9): 1476-1491. doi: 10.3724/SP.J.1004.2013.01476

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2013.01476?viewType=HTML

[6]  杨培颖, 唐加福, 于洋, 裴金翔. 面向最小碳排放量的接送机场服务的车辆路径与调度. 自动化学报, 2013, 39(4): 424-432. doi: 10.3724/SP.J.1004.2013.00424

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2013.00424?viewType=HTML

[7]  熊福力, 严洪森. 基于跳跃辅助工作策略的混流装配线排产优化. 自动化学报, 2012, 38(2): 259-269. doi: 10.3724/SP.J.1004.2012.00259

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.00259?viewType=HTML

[8]  於春月, 王成恩, 曲蓉霞. 中厚板热轧生产调度优化方法. 自动化学报, 2010, 36(2): 282-288. doi: 10.3724/SP.J.1004.2010.00282

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2010.00282?viewType=HTML

[9]  吴启迪, 乔非, 李莉, 吴莹. 基于数据的复杂制造过程调度. 自动化学报, 2009, 35(6): 807-813. doi: 10.3724/SP.J.1004.2009.00807

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2009.00807?viewType=HTML

[10]  柴天佑. 生产制造全流程优化控制对控制与优化理论方法的挑战. 自动化学报, 2009, 35(6): 641-649. doi: 10.3724/SP.J.1004.2009.00641

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2009.00641?viewType=HTML

[11]  杨建军, 刘扬, 魏立新, 战 红. 多源注水系统泵站优化调度的双重编码混合遗传算法. 自动化学报, 2006, 32(1): 154-160.

http://www.aas.net.cn/cn/article/id/15792?viewType=HTML

[12]  王中杰, 吴启迪, 李亚捷. 网格技术在半导体生产调度中的应用研究. 自动化学报, 2006, 32(3): 456-461.

http://www.aas.net.cn/cn/article/id/15835?viewType=HTML

[13]  翟桥柱, 管晓宏, 郭燕, 孙岚, 范炜. 具有混合动态约束的生产系统优化调度新算法. 自动化学报, 2004, 30(4): 539-546.

http://www.aas.net.cn/cn/article/id/16199?viewType=HTML

[14]  刘全利, 王伟, 朱瑞军, 李宁, 金吉凌. 罩式退火炉生产优化调度方法及其应用. 自动化学报, 2004, 30(6): 974-979.

http://www.aas.net.cn/cn/article/id/16280?viewType=HTML

[15]  万百五. 工业生产的产品质量模型和质量控制模型及其应用. 自动化学报, 2002, 28(6): 1019-1024.

http://www.aas.net.cn/cn/article/id/15621?viewType=HTML

[16]  严洪森, 夏琦峰, 朱旻如, 刘霞玲. 汽车装配车间生产计划与调度的同时优化方法. 自动化学报, 2002, 28(6): 911-919.

http://www.aas.net.cn/cn/article/id/14321?viewType=HTML

[17]  毛宁, 陈庆新, 陈新. 支持虚拟企业建立的项目优化调度算法. 自动化学报, 2001, 27(3): 387-391.

http://www.aas.net.cn/cn/article/id/16421?viewType=HTML

[18]  刘民, 吴澄, 尹文君. 带特殊工艺约束的并行机器生产线调度问题的一种遗传算法. 自动化学报, 2001, 27(3): 381-386.

http://www.aas.net.cn/cn/article/id/16137?viewType=HTML

[19]  陈森发, 林贻鸿. 城市煤气供应系统优化调度. 自动化学报, 1993, 19(6): 699-705.

http://www.aas.net.cn/cn/article/id/14174?viewType=HTML

[20]  仲伟俊, 徐南荣, 陈森发. 城市供水系统调度的分解-协调优化方法. 自动化学报, 1990, 16(3): 217-225.

http://www.aas.net.cn/cn/article/id/14799?viewType=HTML