摘要：用运筹优化技术处理复杂场景下的机加工工艺设计问题，建立大规模混合整数规划模型，用Cplex求得最优解，实现机加工工艺的自动编排。首先，分析机加工工艺设计场景的复杂性和问题类型，确定建模方法；然后抽象出业务约束，对问题分解为“先将特征分配到工序”和“再在工序内部排序”两个问题，并建立大规模混合整数规划模型；最后通过分支定界法，利用Cplex商业求解器求得最优解。结果表明该模型可以实现机加工工艺的自动规划和编排，百万级约束的大规模整数规划模型在40 min内可以得到最优的加工方案。相比于之前工艺规划过程只能通过手工规划，整个过程费时费力，且无法得到最优解的方式，利用机加工工艺的整数规划模型可以缩短工艺规划时间80%,机加工成本显著降低。

　　关键词：智能制造,混合整数规划,模型,最优解

　　0引言

　　目前汽车发动机、变速箱等产品的机加工工艺规划过程需要专业资深工程师参与，由于考虑因素众多，整个规划过程耗时、费力，且无法靠人工找到既满足所有约束又使得工艺成本最低的最优方案。如果能通过智能化的方式，将机加工工艺的编排转为数学模型求解，直接找到成本最低的方案，实现机加工工艺的自动编排，必定会提升企业的运营效率、大幅降低企业的生产成本。

　　随着互联网人工智能技术的发展，越来越多的企业意识到智能制造的重要性。越来越多的企业尝试使用人工智能技术提升企业运营效率，从而提升企业竞争力。

　　张锐等[1]基于数学建模和改进的遗传算法对多目标的拆卸线平衡问题进行研究。钟棱充等[2]研究集装箱码头混合零空闲柔性流水作业调度优化问题。张思奇等[3]基于多目标候鸟算法对车间布局研究。李晨辉[4]对机器人的路径规划技术进行研究。张琳娜等[5]基于混合整数线性规划研究含ZIP负荷有源配电网重构方法。殷旅江等[6]用整数规划模型解决多类指派约束下汽车总装装配线平衡优化的问题。孙颖等[7]利用混合整数规划模型解决路政应急管理中资源布局的题。张之臻等[8]建立整数规划模型，对堆垛机立体库的最优布局解决方案进行研究。

　　童小英等[9]在仿真环境下基于遗传算法求解混流装配线最优排产方案。王凌等[10]对分布式车间调度优化算法做了综述研究。TaslimiBijan等[11]以最小化和计划时间表的总偏差为目标建立混合整数规划模型，获得列车的估计行程时间。Ham Andy等[12]提出了一种混合整数规划模型，解决了一个柔性车间调度问题，以最大限度地减少完工时间和总能耗。Ibriksz Norbert等[13]利用整数规划模型帮助工程师查找线路瓶颈、确定工人重组策略。目前汽车企业对于发动机、变速箱等产品的机加工方案设计工作主要依赖于有经验的工程师，尝试通过人工智能的方法实现机加工工艺的自动编排的企业较少。

　　针对以上问题，本文以某企业发动机缸体的工艺规划过程为研究对象，将复杂的设计过程转化为约束和目标，建立混合整数规划模型，结合问题分解、提前约束冲突检查等方法，利用Cplex最终求得最优解。以某款发动机缸体产品实际应用结果为例，说明本文提出的模型能够应用于机加工产品的工艺规划过程，从而解决手工工艺设计效率低、一致性差、质量不稳定、不易达到优化等问题，提高企业智能化水平，达到降本增效目的。

　　1机加工工艺组合优化问题建模

　　1.1问题描述

　　一般机加工工艺规划需要考虑六大因素：(1)定位基准的选择，在工艺规划过程中，正确的选择定位基准，对保证产品加工要求、合理安排加工顺序有至关重要的影响；(2)表面加工方法的选择，同一种表面可以选择多种不同的加工方法，但每种加工方法所能获得的加工质量、所用的加工时间和费用却各不相同；(3)加工阶段的划分，一般都要经过粗加工、半精加工和精加工等3个不同的加工阶段，逐步达到加工要求；(4)工序的集中和分散，有些加工特征需要集中一起共用一把刀，有些加工特征需要独占一个工序；(5)工序顺序安排，待加工特征之间有加工先后顺序要求，如先加工定位基准的面，再加工其他面，或者先加工面再加工孔等；(6)机床设备与工艺装备的选择，所选机床设备的尺寸规格应与待加工产品的形状尺寸相适应，精度等级应与本工序加工要求相适应。

　　本文假设需要加工的特征为248个，可用的机床按夹具类型分为12种，每种机床可以加工某一部分特征。

　　从特征角度，每个特征有多种加工方案，每种加工方案有多个有序加工步骤，每个加工步骤只能使用一种刀具，刀具之间存在可替换的关系。需要输出：需要几个工序，每个工序需要什么类型的机床，每个机床装哪些刀具，每个特征的加工方案，特征被加工的顺序。

　　此问题的关键点有3个：一是需要确定每个工序的机床类型和每个机床安装什么刀，相当于准备“工人”的能力；二是为每个特征选择一种加工方案，相当于为“每个任务”选择一种操作方案；三是安排哪些机床加工哪些特征及加工这些特征的顺序。此问题的难点是这三步相互影响，为求总体最优成本，需一起考虑，无法单独分开求解。原因如下：第一步机床装的刀具类型会影响第三步，即会影响特征可以用哪些机床加工；第二步特征选择的加工方案也会影响刀具之间的合并关系，即会影响特征的顺序。

　　由此可见机加工工艺的编排过程根本是含有多重指派和调度需求的组合优化问题。类似的简化问题还有旅行商问题、生产调度问题、0-1背包问题、装箱问题等都属于组合优化问题，这类问题的特点是描述较简单，并且有很强的工程代表性，但最优解求解非常困难。

　　Huichuan L[14]和Dong W[15]基于旅行商问题的特点和属性，分别设计了新的启发式求解算法。Chaofan T等[16]提出了一种使用深度强化学习超启发式的解决在线装箱问题的新通用框架。Eneko O等[17]用包含12个实例的数据集提出了一个实际装箱问题的基准。Mujin G等[18]提出一种有效的近似算法来求解二维装箱问题，还制定了两个遗传算法，并将其与整数线性规划模型进行了比较。

　　并说明了这个数学模型的精确解只适用于小规模实例。

　　对于其他实例，在短时间内达到最优值是困难的，也从侧面显示了此类问题的求解难度。其主要原因是求解这些问题的算法需要较长的运行时间与较大的存储空间，即所谓的“组合爆炸”。求解组合优化问题的数学模型一般为混合整数规划模型。目前，对于大规模混合整数规划问题的最优解求解，主要依赖于商业求解器或商业求解器和启发式算法结合的方法。因此机加工工艺全局优化最关键的问题是需要对业务逻辑合理抽象为数学模型并求解。

　　1.2详细约束

　　机加工工艺设计包括以下要求：加工顺序、生产节拍、最大刀具数等。详细约束如表1所示。

　　1.3优化目标

　　优化目标有多种情况。根据实际需求，常是以下一种优化目标或以下几种优化目标的组合：总成本最优的目标、在控制成本的情况下节拍最均衡、在固定机床类型下的加工方案最优等。不同目标对应的约束略有不同，不再详述。本文选择以对企业获益最大的总成本最优目标进行详细介绍。

　　1.4建模方案分析

　　如果直接建立一个整数规划模型，给出上述1.1节要求的输出，模型规模约束量将在千万级别，直接求解是非常困难的。由于给出需要几个工序、每个工序的机床类型、每个机床可以装的刀等属于指派问题，而具体每个特征在每个工序的加工顺序又属于旅行商问题。所以将问题进行分解，第一个模型先把特征分派到工序中，给出需要几个工序、每个工序的机床类型、每个机床可以装的刀、哪些特征在哪个工序加工；第二个模型再在每个工序内部对特征的加工排序排序。这样在不改变最优解的情况下，把问题分解为相对较小的两个模型。由于工序内部排序模型考虑因素较少，属于经典的TSP问题，建模求解相对容易，限于篇幅，本文重点介绍第一个模型。

　　1.4.1参数设置

　　模型参数设置如下：f为待加工特征；F为待加工特征集合；ST为加工步骤集合；P为工序集合；M为机床类型集合；SL为加工方案集合；TT为刀具类型集合；TN为刀具名称集合；Amount为最大机床并行数；FT为夹具类型集合；Prior为工序优先级，值越大优先级越高；WorkingTime为加工时间；ChangeTime为换刀时间；ChangeFTime为特征切换时间；Price _ MF为机床和夹具单价；Price_ T为刀具单价。

　　1.4.2变量定义

　　0-1变量定义：x1 f,p,ft,m,sl值为1表示第f个特征在第p个工序加工，且第p个工序中的机床为m类型，且m类型的机床安装的是ft类型的夹具，且f使用的加工方案为sl,其他情况值为0;x2 p,ft,m值为1表示第p个工序使用装了ft类型夹具的m类型的机床，其他情况为0;x3 p,ft,m,tt值为1表示第p个工序使用装了ft类型夹具的m类型的机床，该机床上面安装了刀具类型为tt的刀，其他情况为0;x4f,p,ft,m,sl,tt,tn值为1表示第f个特征在第p个工序加工，且第p个工序安装了m类型的机床，且m类型的机床安装的是ft类型的夹具，且f使用的加工方案为sl,且sl选择的刀具类型为tt,对应的刀为tn,其他情况为0。

　　整数变量定义：Amountp,ft,m表示第p个工序，当使用的机床m安装了夹具类型为ft的夹具时，第p个工序中机床的最大台数。

　　1.5数学模型

　　本文在综合考虑优化目标、约束条件与求解器能力的基础上，对一些非线性约束进行线性化处理，建立机加工工艺混合整数规划模型，数学模型描述如下：

　　式(1)表示只要有一个特征在此机床上加工，就得使用这种类型的机床。式(2)表示每个工序只用一种类型的机床。式(3)表示每个特征只能在一个工序、一种类型的机床、使用一种加工方案加工。式(4)表示特征加工的先后顺序，F1__ F2是特征先后关系表。式(5)表示特征与机床的定位关系，某特征需要加工完成后才能使用某些机床（例如：机床类型M1需要用到特征F1来作为定位特征，那么需要先把特征F1加工完成再使用机床M1),F_ M是特征与机床定位关系表。式(6)表示工序节拍不能超过业务要求时间51 s（节拍51 s可以通过用户输入配置）。式(7)表示如果有一个机床类型用这种类型的刀，这个机床就需要装这把刀，例如：

　　如果变量x4值为1,则变量x3也必须为1,即：如特征f在工序p加工，工序p中的机床类型m;特征使用的加工方案为sl,sl中用的刀具为tt,那么工序p中的机床类型必须为m,且m中装的刀必须有tt。式(8)表示使用一个solution,就使用这个solution的所有刀具，例如：

　　如果特征选择了加工方案sl,那么特征就需要用sl对应的刀加工，不能用其他sl中对应的刀加工。式(9)表示单台机床的最大刀数量不能超过30（可根据机床参数化配置）。式(10)为目标函数，总成本最低。

　　2求解及结果分析

　　2.1模型求解过程

　　Cplex是ILOG（如今被IBM收购）在1987年创立之初就开发出来的一个优化引擎，可以用来求解线性规划、二次规划、带约束的二次规划、二阶锥规划及相应的混合整数规划MIP问题。Cplex Studio提供了快速建立高效优化模型以及全方位解决规划和调度问题的方法。

　　Kaiping L等［19］将0-1数学规划用于工艺规划，并用Cplex求解。Yu H等［20］建立混合整数规划模型，优化能源效率时间表，并用Cplex求解。

　　将数学模型用Cplex Studio自带的OPL语言编写机加工工艺组合优化模型，借助Cplex求解引擎，选用Cplex求解配置的数学规划模块，采用分枝定解法、深度优先搜索策略。由于可行解比较少，MIP强调开关选择“强调整数可行性高于最优化”，可以快速求解。

　　分枝定界法是对有约束条件的最优化问题的所有可行解空间恰当地进行系统搜索的算法，是求解整数规划问题的常用算法。分枝定界法把全部可行解空间反复地分解为越来越小的子集（成为分枝），并为每个子集内的解值计算一个界（如果目标函数是求最大值，则为上界；如果目标函数为求最小值，则为下界）。在每次分枝后，凡是界限超出已知可行解值的那个子集，就不再进一步分枝，而是把它减掉。这样解的很多个子集（不必检查这些子集中的每个解）就可以不考虑了。这种分枝继续进行直到找出可行解为止，而该可行解的目标函数值（对目标函数为求最小值的情况）不大于任何子集的界限。

　　具体步骤如下。

　　（1）求整数规划问题（A）的松弛问题（B）最优解，如果最优解为整数，则求解完成；如果最优解不是整数，则开始下一步。

　　（2）分枝定界，任意选一个非整数变量xi，在松弛问题中加入由此变量xi产生的两个整数约束（例如，一个约束为xi≥2，另一个约束为xi≤1），组成新的松弛问题，称为分枝，检查所有分枝问题的解及目标函数值。

　　若某分枝的解为整数，且目标函数值小于等于其他分枝的可行解（对于求最小问题而言），则此整数解为最优解。否则继续分枝，直到找到最优解。

　　另外，在实际项目过程中，为减小搜索空间，将一些约束提前检查，对不满足约束的潜在搜索对象提前删除，而不放在模型中。在经过数据预处理（对不满足基本业务规则的候选组合，提前从潜在解空间中删除）之后，最终进入模型的约束有399万条。

　　2.2输入数据及求解

　　用某款发动机产品的工艺数据做验证，参数设置：

　　最大工序数设置为9，最大节拍为51 s，最大刀具数量30，每个工序最大机床台数上限设置为20。以上参数通过用户前端输入，后台处理后，整理到模型的输入表中，作为约束。数据量：248个特征，15种机床类型，每个特征有多种加工方案，每个加工方案最多有4个步骤，刀具具有合并关系。处理后的某一个特征的一个潜在加工方案样例数据如表2所示。

　　样例数据含义说明：FEATURENUMBER为需要加工的特征，F290为需要加工的一个面；PROCESS为可以选择的工序号，按阿拉伯数字编号process1，process2，…，process10，具体选择几个工序，每个工序做什么事情由模型给出，模型可能选的工序为process2，process5，process1……最终选择的工序按OP10，OP20……顺序重新编号给出；FIXTURETYPE为该工序机床的夹具类型；SOLUTIONNUMBER为特征的加工方案号；STEPSNAME为对应加工方案的加工步骤号；TOOLHOLDER为刀柄类型；TOOLTYPE为刀具类型，相同刀具类型的刀可以相互替代；TOOLNUMBER为对应加工步骤的刀具号；MachineName为可以选择的机床名称；x4为变量，在求解之后输出0或者1，如果值为1，则表示对应的特征选择的详细加工方案，包括在第几个工序，用的加工方案及被哪个机床加工。

　　如图1所示，计算模型求解完成后，会在“值”列输出x4的值，图中对值按倒序排列，为1的即为最终方案。

　　从图中前2行可以看出：特征H936在第5道工序process5加工，process5装的机床为DEF类型的机床，H936使用的加工方案为H936 S1，这个加工方案有两步，分别为H936 S1 ST1、H936 S1 ST2，这两步用的刀分别为H936 S1 ST1 T1、H936 S1 ST2 T1。

　　在求解方面，选用数学规划，选择分枝定界法，MIP强开关设置为“强调整数可行性高于最优化”，MIP试探频率选择“-1”，MIP变量选择策略选择“伪缩减成本”，采用深度优先搜索策略，模型可在355 s后达到最优解，即最低成本的解（图2)。详细参数设置如图3所示。

　　2.3结果分析

　　表3所示为模型编排结果统计情况。可以看出，本次编排共用了40台机床，每台刀具数量满足小于30把的要求；工序节拍均小于51 s,有的工序的节拍达到50.86、50.99 s,这是传统手工方法无法达到的。另外，OP40工序是冲洗工序，属于预留工序，该工序的机床和刀具以及特征都已经给定，所以不需要考虑此工序的结果。

　　表4为手工编排的统计情况。可以看出手工编排的结果工序数比机器编排结果多2个工序；总机床台数多1台机床；单台机床的刀具数量少；总体节拍不够均衡，且离节拍约束不大于51 s较远。

　　所以通过数学模型得到的加工方案编排结果更紧凑，特征分布更合理，节拍更均衡，总成本更低。

　　3结束语

　　针对机加工工艺规划手工工艺设计效率低、一致性差、质量不稳定、不易达到最优化等问题，本文综合考虑机加工工艺设计中的各种约束因素，对复杂机加工工艺设计建立大规模混合整数规划模型，并用Cplex求解。

　　用实际数据验证，得出本模型可以用于机加工工艺设计，实现机加工工艺自动编排。本文的创新点在于针对含有多重指派和调度问题的复杂实际场景建立大规模整数规划模型，并成功求得最优解。

　　本文论述的模型在实际应用中证明可以缩短工艺编排时间，提升工艺规划效率，规划结果明显优于手工规划结果，从而可以降低企业成本。模型和方法可以推广到其他机加工产品中，具有推广价值。

　　参考文献：

　　[1]张锐，刘婷婷，郭宏飞，等．多目标的拆卸线平衡问题优化研究[J].机电工程技术，2023,52(4):6-9.

　　[2]钟棱充，李文锋，贺利军，等．集装箱码头混合零空闲柔性流水作业调度优化[J].计算机集成制造系统，2022(11):3421-3432.

　　[3]张思奇，于登辉，郑一明，等．基于多目标候鸟算法对车间布局研究[J].现代制造工程，2022(2):16-23.

　　[4]李晨辉，王泽峰，胡德燕，等．移动机器人的路径规划技术研究[J].机电工程技术，2023,52(1):5-9.

　　[5]张琳娜，乐健，李昊炅．基于混合整数线性规划的含ZIP负荷有源配电网重构方法[J].电力系统保护与控制，2022(8):25-32.

　　[6]殷旅江，何波，杨立君．多类指派约束下汽车总装装配线平衡优化[J].制造业自动化，2014(24):41-44.

　　[7]孙颖，池宏，贾传亮．路政应急管理中资源布局的混合整数规划模型[J].运筹与管理，2006(5):108-111.

　　[8]张之臻，陈健．自动化立体库布局与巷道堆垛机作业特点的研究[J].物流技术与应用，2023,28(5):118-112.

　　[9]童小英，滕瑞飞，孙丽．仿真环境下基于遗传算法的混流装配线排产优化研究[J].制造技术与机床，2018(11):29-35.

　　[10]王凌，邓瑾，王圣尧．分布式车间调度优化算法研究综述[J].控制与决策，2016(1):1-11.

　　[11]Taslimi Bijan,Babaie Sarijaloo Farnaz,Liu Hongcheng.A novelestimation[J].European Journal of Operational Research,2022,300(2).

　　[12]Ham Andy,Park Myoung Ju,Kim Kyung Min.Energy-Aware Flexible Job Shop Scheduling Using Mixed Integer Programming and Constraint Programming[J].Mathematical Problems in Engineering,2021.

　　[13]Ibriksz Norbert,Szalay Tibor,Kutrovácz Lajos.Analysis of an assembly line by mixed integer programming and discrete event-based simulation[J].Procedia Manufacturing,2021,54.

　　[14]Huichuan L.Research on agricultural machinery operation path optimization based on traveling salesman problem(TSP)[J]. Journal of Physics:Conference Series,2021,1976(1).

　　[15]Dong W,Dongmei L,Jiun J S.The Simple Method and Algorithm for Solving Traveling Salesman Problem(TSP)inMonte Carlo Model[J].Basic&Clinical Pharmacology&Toxicology,2020,127.

　　[16]ChaofanT,RuibinB,Uwe A,et al.A deep reinforcement learning hyper-heuristic with feature fusion for online packing problems[J].Expert Systems With Applications,2023,230.

　　[17]EnekoO,EstherV,Sebastián R V.Benchmark dataset and instance generator for real-world three-dimensional bin packing problems[J].Data in Brief,2023,49.

　　[18]Mujin G,Yanru C,Junheng L,et al.Hybrid branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with time windows[J].Computers and Operations Research,2023,157.

　　[19]Kaiping L,Guangya S,Liheng L,et al.0-1 mathematical programming models for flexible process planning[J].European Journal of Operational Research,2023,308(3).

　　[20]Yu H,Wenliang Z,Jin Q,et al.Optimization of energy-efficiency train schedule considering passenger demand and rolling stock circulation plan of subway line[J].Energy,2023,275.