摘要
复杂机电产品装配产线多采用模块化设计以实现多型产品并行生产,各模块装配过程中存在部分工序组批处理、多机并行加工等复杂情况,为车间排程方案的制定带来巨大挑战。本文以复杂机电产品柔性装配作业车间为研究对象,多品种小批量生产模式下考虑多机并行批处理,以最小化最大完工时间、最小化拖期时间和最大化平均设备利用率为目标,建立多目标整数规划模型。根据问题特性,设计嵌入启发式规则的快速非支配排序遗传算法求解模型。实验表明,本文提出的排程策略及模型能提供合理的批产机组批方案;改进算法与传统非支配排序遗传算法相比,最大完工时间平均缩短4.25%,总拖期时长平均降低32.30%,平均设备利用率增长0.69%。
随着中国工业技术水平的不断提升,精密器械和高端电子产品领域快速发展。复杂机电产品由多种机械构件、电子器件和控制装置组成,融合了机械和电子产品的特性,体现了我国制造业发展水平,并在装备制造领域中发挥着关键作
复杂机电产品的生产过程包括元件生产组装、组件壳体制造、组件装配、总体装配及测试等多个环节,产品生产周期长且工艺流程复
目前,针对复杂机电产品的相关研究多集中在工艺技术优化方面。王发麟
此外,复杂机电产品作业车间使用混合流水生产模式,侧重资源的重组优化,其产线排程属于典型的NP‑hard问
本文以某装备制造企业复杂机电产品装配作业车间为例,展开考虑不相关并行机及在制品部分工序组批处理情形下,多型产品装配的排程优化问题。针对该问题,建立复杂机电产品作业车间调度问题(Complex electromechanical products‑job shop scheduling problem, CEP‑JSP)整数规划模型,并对传统遗传算法进行改进,设计嵌入启发式规则的快速非支配排序遗传算法(Fast non‑dominated sorting genetic algorithm Ⅱ with heuristic rules, NSGAH‑Ⅱ)对模型进行求解,最后通过实例验证模型和算法的可行性。
本文研究复杂机电产品装配作业车间排程优化问题,该问题描述如下。在生产周期内共有个订单任务,对应相同数量待装配工件,工件集。所有工件需要在台设备上装配,设备集。零时刻,在首个工件开始加工时,部分工件已到达,其他待装配工件在调度周期内到达,且到达时间已知。所有工件均经过道工序进行装配,形成不同型号产品,工序集。不同型号工件有不同的装配工艺路线,且装配过程遵守工序顺序约束。第件工件的第道工序可选设备数量为。每道工序只能选择1台设备进行加工,每台设备具有一定的加工能力,表示同时可加工工件数量。当所有工序完成时,工件装配完成。根据问题描述,做出如下假设:
(1) 工件加工过程不存在质量及设备故障问题,即良品率为100%;
(2) 同时刻每个工件只允许在1台设备上加工;
(3) 所有工件的工艺顺序不可改变,即工序的先后加工顺序不可逆;
(4) 不考虑在制品等待加工时的缓存区容量约束;
(5) 忽略在制品的运输时间;
(6) 忽略不同型产品连续装配的换型时间;
(7) 整个加工过程所需物料充足。
针对提出的问题,以最小化最大完工时间、最小化拖期时间及最大化平均设备利用率为目标,构建了CEP‑JSP模型。
(1) 参数定义
相关符号定义、目标函数及约束条件表征如
参数符号 | 含义 | |
---|---|---|
工件编号 | ||
设备编号 | ||
工序编号 | ||
工件索引 | ||
设备索引 | ||
工序索引 | ||
工件的第道工序 | ||
常量 | /个 | 总订单数量 |
/个 | 设备数量 | |
/道 | 工序数量 | |
工件的第道工序可用设备数量 | ||
设备的加工能力,即可同时加工工件数量 | ||
/min | 工件的第道工序在设备上的加工时间 | |
工件的交期 | ||
变量 | /min | 工件第道工序的开始加工时间 |
/min | 工件第道工序的结束加工时间 | |
/min | 工件的拖期时间 | |
/min | 设备开机时间,即首次使用时间 | |
/min | 设备关机时间,即结束使用时间 | |
设备的组批加工数量 | ||
/min | 工件在设备上第次批处理的可开始加工时间 | |
/min | 设备第次批处理的首个待加工在制品的等待加工时间 | |
工件到达批处理设备后,若则设备停止等待并进行第次批处理,此设备所有待加工工件开始加工;则继续等待 | ||
工件的第道工序在设备上加工,则,否则为0 |
(2) 目标函数
(1) |
(2) |
(3) |
(3) 约束条件
(4) |
(5) |
(6) |
(7) |
(8) |
(4) 组批判断
(9) |
(10) |
(11) |
其中,式(
当工件上道工序加工完成,且本工序所使用设备未加工其他工件时,称该工件处于可加工状态,工件可加工状态持续时间为待加工在制品的等待加工时间。当设备为批处理机,且工件刚处于可加工状态时,对设备进行组批判断。其中,
本文所研究的复杂机电产品作业车间调度模型包含混合流水作业和工件组批处理,属于典型的NP‑hard问
NSGAH‑Ⅱ的基本流程如

图1 算法流程
Fig.1 Flow chart of the algorithm
遗传算法中,染色体编码对模型的求解起到关键作用。由于复杂机电产品排程涉及工件装配顺序和设备选择,故采用工件‑设备双层编码方式,如

图2 染色体双层编码
Fig.2 Chromosome double layer coding
此外,模型求解包含订单排序、设备选择以及批处理组批等复杂要素,故使用启发式规则生成染色体工序层和设备层编码,采用人工经验对初始种群编码进行合理性优化,以提升种群进化效果,降低种群迭代次数。其中,工序层编码如

图3 初始染色体生成示例
Fig.3 Initial chromosome generation example
其中,工序码引入经典调度问题中常用的启发式规则,包括:(1) EDD(Earliest due date)规则:工件按到期时间增序排列;(2) ERT(Earliest release time)规则:按工件到达时间增序排列;(3) 随机排列规则,选择概率分别为0.3、0.3和0.4。而设备码同样采用启发式规则,包括:(1) SPT(Shortest prossing time)规则:选择最短加工时间设备;(2) MLF(Maximum load first)规则:选择负荷能力最大设备;(3) 随机选择,选择概率分别为0.3、0.3和0.4。
基于CEP‑JSP模型,需要对每条染色体解码形成工件加工顺序、各工序设备选择以及批产机组批方案。为求解该模型,本文设计包含前插机制的解码方式,以减少装配等待时间,加速收敛。以

图4 染色体解码示例
Fig.4 Chromosome decoding example
Step 1 获取染色体(取,在
Step 2 计算基于工序约束的工件开始加工时间。将工件上一工序结束加工时间(首次加工则取零)、工件释放时间进行比较取大。
Step 3 计算基于设备约束的工件开始加工时间。若所选用设备为批处理机(),判断批产机在制品等待加工数量,若为0则取设备上次加工的结束使用时间,不为0则取待组批在制品中的最大开始加工时间;若所用设备加工容量为1,则取设备上次加工的结束使用时间。
Step 4 在制品组批。若设备为批处理机,且该批处理机满足组批条件(即)或待加工在制品达到设备容量,则组批开始加工,更新设备开始、结束使用时间,此设备在制品等待数量清零;若不符合组批条件,则停止后续步骤,储存工件可开始加工时间,设备待加工在制品数量加1。
Step 5 生成工件开始加工时间。将Step 2与Step 3所得时间进行比较,取大为。
Step 6 前插操作。若所选设备为单处理机,并且设备约束所得开始时间大于工序约束所得时间。计算开始加工时间之前,所有可加工该工序设备的空闲时间段,若存在空闲时间段大于加工时间,并且空闲时间起点小于工序约束开始时间,则更新开始加工时间为该起点。
Step 7 计算并储存设备结束加工时间。
对染色体进行解码后得到组批排程方案。为求解多目标函数并得到适应度值,采用Pareto寻优方法对种群进行适应度排序。
首先依据Pareto支配规则进行分层,将所有个体标记出层级编号,各层级编号表示其所在的非支配前沿。例如,第一前沿F1即层级为0,包含所有非支配个体,而第二前沿F2即层级为1,包含所有仅被第一前沿支配的个体,以此类推。每层个体在优化过程中同等重要,前沿等级越低,越接近Pareto最优。
而同层个体,需要进行拥挤度计算,从而实现个体排序,拥挤度越大则遗传概率更高,同层中排序更靠前。个体拥挤度是其在所有目标函数中的拥挤距离之和,个体拥挤度计算公式为
(12) |
式中:表示个体在第个目标中的拥挤度;分子和表示相邻个体第个目标的函数值;而分母和分别表示所有个体在第个目标上的最大、最小目标函数值。
考虑交叉后所得染色体的可行性,采用改进模拟二进制交叉(Simulated binary crossover,SBX)方法,针对工序码和设备码采用不同的交叉规则。
如

图5 工序码交叉示例
Fig.5 Example of process code crossover
为保证设备码在交叉过程中,不违反工件可使用设备集约束,对原交叉方式进行改进。如

图6 设备码交叉示例
Fig.6 Example of device code crossover
由于本文采用双层编码,故对原有多项式变异进行改进,如

图7 染色体变异示例
Fig.7 Example of chromosomal variations
本文以实际生产作业车间为案例,通过对比实验验证CEP‑JSP模型的准确性,以及改进后NSGAH‑Ⅱ的求解效果及可行性。实验仿真环境为:Windows64位操作系统,CPU为Intel(R) Core(TM) i5‑8300H,处理器主频为2.30 GHz,8 GB内存,编程环境为Matlab 2020a。
某装备研制企业主要生产多型复杂机电产品,产品更新迭代快,使用离散‑流水混合生产模式,符合多品种小批量生产特点。以该企业总体装配车间为研究案例,其产线采用混合流水作业模式,部分装配工序使用批处理机进行加工,且可同时加工不同型号产品。由于装配工艺复杂,多型产品混线生产,该产线排程方案制定主要依靠车间班组人员。以某月订单需求的四型产品为例,产品、、及所对应的装配工序、可用设备及其参数,如
产品型号 | 可用设备 | 工序1 | 工序2 | 工序3 | 工序4 | 工序5 | 工序6 | 工序7 | 工序8 |
---|---|---|---|---|---|---|---|---|---|
编号 | 1 | 2 | {3,4} | 6 | {7,8} | 9 | {10,11} | 13 | |
加工时间/min | 20 | 20 | 60、50 | 10 | 30、40 | 15 | 240、270 | 25 | |
编号 | 1 | 2 | {4,5} | 6 | {7,8} | 9 | {11,12} | 13 | |
加工时间/min | 15 | 30 | 60、70 | 10 | 40、30 | 15 | 280、300 | 30 | |
编号 | 1 | 2 | {3,5} | 6 | {7,8} | 9 | {11,12} | 13 | |
加工时间/min | 20 | 30 | 70、80 | 10 | 40、50 | 15 | 200、230 | 25 | |
编号 | 1 | 2 | {3,5} | 6 | {7,8} | 9 | {11,12} | 13 | |
加工时间/min | 20 | 30 | 70、80 | 10 | 40、50 | 15 | 200、230 | 25 |
此外,该产线共13台设备,各设备同时可加工在制品数量如
设备编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
加工能力/个 | 1 | 1 | 4 | 3 | 3 | 1 | 4 | 3 | 1 | 3 | 4 | 3 | 1 |
序号 | 编号 | 产品型号 | 到达时间 | 交付时间 |
---|---|---|---|---|
Day1 | 1、2、3 | 0 | 1 440 | |
4、5 | 90 | 1 440 | ||
6、7 | 120 | 1 440 | ||
8 | 150 | 1 440 | ||
9 | 180 | 1 440 | ||
10、11 | 0 | 1 200 | ||
12、13 | 60 | 1 200 | ||
14 | 150 | 1 200 | ||
Day2 | 1、2 | 0 | 1 400 | |
3 | 60 | 1 400 | ||
4、5、6 | 180 | 1 400 | ||
7、8 | 0 | 900 | ||
9 | 60 | 900 | ||
10 | 90 | 900 | ||
11、12 | 420 | 900 | ||
13、14 | 0 | 1 200 | ||
15、16 | 150 | 1 200 | ||
17、18 | 180 | 1 200 | ||
Day3 | 1、2、3、4、5、6 | 0 | 1 440 | |
7、8 | 90 | 1 440 | ||
9、10 | 120 | 1 440 | ||
11、12 | 180 | 1 440 | ||
13、14、15、16 | 0 | 1 200 | ||
17、18 | 90 | 1 200 | ||
19、20 | 150 | 1 200 | ||
Day4 | 1、2 | 0 | 900 | |
3、4、5 | 90 | 900 | ||
6、7、8 | 150 | 900 | ||
9、10 | 0 | 1 400 | ||
11、12 | 60 | 1 400 | ||
13、14 | 210 | 1 400 | ||
15、16 | 300 | 1 400 | ||
Day5 | 1、2、3 | 0 | 900 | |
4、5、6 | 90 | 900 | ||
7、8 | 180 | 900 | ||
9、10 | 0 | 1 200 | ||
11、12 | 120 | 1 200 | ||
13、14 | 0 | 800 | ||
15、16 | 300 | 800 | ||
17、18、19 | 360 | 800 |
本文所提出的NSGAH‑Ⅱ包含4个关键参数,分别为种群规模()、最大迭代次数()、交叉概率()及变异概率()。上述参数对于算法性能会产生较大影响,故通过测试实验选取最佳参数组合,发挥算法最大效用。经过初步测试,最大算例规模()能够在150代内达到收敛状态,因此设定为150。而其余参数在初步测试中难以确定,本文采用正交实验的方法进行调参。在正交实验中,为保持算例规模的一般性,设定订单数量为18,运用正交实验对、和寻找最优参数组合。
根据正交实验规则,每个关键参数各取3个水平,其中, ,。将NSGAH‑Ⅱ在不同参数组合下独立运行20次,各目标函数结果平均值如
实验 | 最大完工时间/min | 拖期/min | 平均设备利用率/% | |||
---|---|---|---|---|---|---|
1 | 100 | 0.7 | 0.10 | 1 508.75 | 2 814.5 | 93.08 |
2 | 100 | 0.8 | 0.15 | 1 516.25 | 2 953 | 93.62 |
3 | 100 | 0.9 | 0.20 | 1 481.5 | 2 550.25 | 93.73 |
4 | 150 | 0.7 | 0.15 | 1 466 | 2 420 | 94.69 |
5 | 150 | 0.8 | 0.20 | 1 462.5 | 2 370.25 | 94.79 |
6 | 150 | 0.9 | 0.10 | 1 483.25 | 2 559 | 94.61 |
7 | 200 | 0.7 | 0.20 | 1 451.75 | 2 036.5 | 94.38 |
8 | 200 | 0.8 | 0.10 | 1 442 | 1 983.5 | 95.12 |
9 | 200 | 0.9 | 0.15 | 1 445 | 2 008.75 | 94.31 |
注: 表中增黑字体表示数据所在列目标函数下,实验组结果表现最优。
分别使用两种算法对5组数据求解排程策略,每组数据各运行20次,目标函数值取测试结果平均值,如
序号 | 算法 | 最大完工时间/min | 拖期/min | 平均设备利用率/% |
---|---|---|---|---|
Day1 | NSGA‑Ⅱ | 1 159 | 0 | 97.69 |
NSGAH‑Ⅱ | 1 132 | 0 | 98.22 | |
Day2 | NSGA‑Ⅱ | 1 509 | 2 965 | 94.52 |
NSGAH‑Ⅱ | 1 413 | 1 775 | 94.99 | |
Day3 | NSGA‑Ⅱ | 1 484 | 654 | 95.32 |
NSGAH‑Ⅱ | 1 418 | 216 | 96.93 | |
Day4 | NSGA‑Ⅱ | 1 309 | 1 615 | 95.05 |
NSGAH‑Ⅱ | 1 236 | 936 | 95.56 | |
Day5 | NSGA‑Ⅱ | 1539 | 5672 | 93.06% |
NSGAH‑Ⅱ | 1499 | 4970 | 93.22% |
目标 | Day1 | Day2 | Day3 | Day4 | Day5 |
---|---|---|---|---|---|
-2.3 | -6.4 | -4.4 | -5.6 | -2.6 | |
0.0 | -40.1 | -66.9 | -42.0 | -12.4 | |
+0.5 | +0.5 | +1.7 | +0.5 | +0.2 |
注: 表中表示最大完工时间,表示拖期时间,表示平均设备利用率;“-”表示降低,“+”表示增长。
以Day2算例测试结果为例,取两种算法最大完工时间中最优结果,对应各目标迭代曲线如

图8 算法迭代曲线对比
Fig.8 Comparison of algorithm iteration curves
在车间生产装配现场,订单计划的执行通过班组调度人员进行管理,调度人员需要根据生产订单、资源可用性、设备加工能力及工艺流程设计排程方案。在Day2中随机选取算法运行结果绘制甘特图,与人工排程方案甘特图进行对比,如

图9 实例运行甘特图对比
Fig.9 Gantt charts from examples
本文针对复杂机电产品装配作业车间排程问题,构建了CEP‑JSP调度模型对作业车间现场进行描述。根据模型设计工序‑设备双层染色体编码方式,以及对应的解码策略。提出基于启发式规则的NSGAH‑Ⅱ算法,对种群初始化策略进行改进。依据模型约束,对遗传算法中各层染色体的交叉、变异过程进行了调整,以实现排程问题的求解。
在实例验证中,与传统快速非支配排序遗传算法相比,NSGAH‑Ⅱ算法可使最大完工时间平均减少4.25%,总拖期时间平均缩短32.30%,平均设备利用率提高0.69%。在小批量日排程结果中,与手工排程方案对比,改进算法的排程效果和效率均得到明显提高。此外,通过迭代曲线得出,改进方案的初始种群质量高于原始算法,针对任务紧急度较高的订单计划,NSGAH‑Ⅱ算法能够显著降低拖期时间。
复杂机电产品多品种小批量的生产模式,也同样使产线排程计划受到各类扰动因素影响。产品的质量返修问题、临时插单问题等,将会是下一步研究的重点。未来可考虑将CEP‑JSP模型及求解方法引入MES系统中,对装配现场提供排程方案指导。
参考文献
荣双龙,赵朋飞,刘艳,等.复杂环境应力下典型机电产品贮存-值班寿命加速试验方法研究[J].装备环境工程,2024,21(7): 19-27. [百度学术]
RONG Shuanglong, ZHAO Pengfei, LIU Yan, et al. Research on accelerated test method of storage-duty life of typical electromechanical products under complex environmental stress[J]. Equipment Environmental Engineering, 2024, 21(7): 19-27. [百度学术]
何靓,郭俊刚,朱攀星,等.航空复合材料智能制造探索与实践[J/OL].航空工程进展,2024.http://kns.cnki.net/kcms/detail/61.1479.V.20240918.1320.004.html. [百度学术]
HE Liang, GUO Jungang, ZHU Panxing, et al. Exploration and practice of intelligent manufacturing of aviation composite materials[J/OL]. Progress in Aeronautical Engineering, 2024. http://kns.cnki.net/kcms/ detail/61. 1479.V.20240918.1320.004.html. [百度学术]
景立挺.复杂机电产品概念设计原理方案博弈决策与优化的研究[D].杭州:浙江工业大学,2020. [百度学术]
JING Liting. Research on game decision-making and optimization of conceptual design principle schemes for complex electromechanical products[D]. Hangzhou: Zhejiang University of Technology, 2020. [百度学术]
王振华.不确定因素下复杂机电产品装配车间重调度问题研究与应用[D].重庆:重庆大学,2022. [百度学术]
WANG Zhenhua. Research and application of rescheduling problem of complex electromechanical product assembly workshop under uncertain factors[D]. Chongqing: Chongqing University, 2022. [百度学术]
晋严尊,王中一,汤辉.智能制造技术在机载武器制造中的应用[J].航空兵器,2021, 28(6): 1-6. [百度学术]
JIN Yanzun, WANG Zhongyi, TANG Hui. Application of intelligent manufacturing technology in airborne weapon manufacturing[J]. Aviation Weaponry, 2021, 28(6): 1-6. [百度学术]
王发麟,郭耀文,龚建华.基于改进快速搜索随机树算法的复杂机电产品线缆装配路径求解[J].计算机辅助设计与图形学学报,2024,36(8): 1298-1310. [百度学术]
WANG Falin, GUO Yaowen, GONG Jianhua. Assembly path solution for cable of complex electromechanical products based on improved fast search random tree algorithm[J]. Journal of Computer-Aided Design & Graphics, 2024, 36(8): 1298-1310. [百度学术]
王帅.面向不同复杂度的机电产品模块化设计若干关键问题研究[D].徐州:中国矿业大学,2022. [百度学术]
WANG Shuai. Research on several key issues of modular design of electromechanical products of different complexity[D]. Xuzhou: China University of Mining and Technology, 2022. [百度学术]
林景亮.基于深度代理模型的复杂机电产品仿真优化方法及应用[D].广州:广东工业大学,2021. [百度学术]
LIN Jingliang. Simulation optimization method and application of complex electromechanical products based on deep agent model[D]. Guangzhou: Guangdong University of Technology, 2021. [百度学术]
GANG Y, XIAOJUN L, CHANGBIAO Z, et al.Multi-objective coupling optimization of electrical cable intelligent production line driven by digital twin[J].Robotics and Computer-Integrated Manufacturing, 2024, 86: 102682. [百度学术]
GUODONG Y, CHUANYUAN Z ,YANPENG C, et al.Rapid planning of an assembly path by reusing the prior path[J].Applied Sciences,2021,11(2): 633. [百度学术]
杨开海,程世明,李仁花,等.基于文献计量的复杂机电产品线缆装配技术研究发展态势分析[J].科技创新与应用,2021,11(16): 55-60,64. [百度学术]
YANG Kaihai, CHENG Shiming, LI Renhua, et al. Analysis of research and development trend of cable assembly technology for complex electromechanical products based on bibliometrics[J]. Science and Technology Innovation and Application, 2021, 11(16): 55-60, 64. [百度学术]
MA J T, LIU J H, DING X Y, et al. Motion planning for deformable linear objects under multiple constraints[J]. Robotica, 2020, 38(5): 819-830. [百度学术]
ELLIPS M,SOMAYÉ G.ASPPR: A new assembly sequence and path planner/ replanner for monotone and nonmonotone assembly planning[J]. Computer-Aided Design, 2020,123:102828. [百度学术]
付红艳.基于遗传算法车间调度研究[D].沈阳:沈阳工业大学,2024. [百度学术]
FU Hongyan. Research on workshop scheduling based on genetic algorithm[D]. Shenyang: Shenyang University of Technology, 2024. [百度学术]
乐细有,余建国.基于改进的NSGA-Ⅱ算法求解作业车间调度问题的研究[J].机电工程技术,2024,53(1): 110-114, 197. [百度学术]
LE Xiyou, YU Jianguo. Research on solving job shop scheduling problems based on improved NSGA-Ⅱ algorithm[J]. Mechanical and Electrical Engineering Technology, 2024, 53(1): 110-114, 197. [百度学术]
FAN J,ZHANG C,YANG F, et al.A matheuristic with re-lot-sizing strategies for flexible job-shop rescheduling problem with lot-streaming and machine reconfigurations[J].European Journal of Operational Research,2024,319(3): 747-762. [百度学术]
赵东方,张晓冬,周宏丽.面向并行制造的多生产单元协同调度研究[J].中国管理科学,2020,28 (8): 188-195. [百度学术]
ZHAO Dongfang, ZHANG Xiaodong, ZHOU Hongli. Research on collaborative scheduling of multiple production units for parallel manufacturing[J]. Chinese Journal of Management Science, 2020, 28(8): 188-195. [百度学术]
周楠,谢乃明,郑绍祥.考虑释放时间和装箱约束的航空复材热压成型单机批调度[J].工业工程与管理,2024,29(5): 1-13. [百度学术]
ZHOU Nan, XIE Naiming, ZHENG Shaoxiang. Single-machine batch scheduling of aviation composite hot pressing molding considering release time and packing constraints[J]. Industrial Engineering and Management, 2024, 29(5): 1-13. [百度学术]