基于扩展双资源约束型航空构件制造车间调度方法

娄航宇，张吉善，赵云博

(东北大学 工商管理学院，辽宁 沈阳 110819)

0 引言

近年来随着国家科研水平整体提升，高端制造业蓬勃发展。航空构件作为航天设备的重要组成部分，其制造过程是航天工业的关键环节。航空构件属于典型的单件小批量、多品种的生产方式，不同品种甚至同种品种不同型号的构件间工艺路线相差巨大[1-2]。实际航空构件制造中有如下特征：

(1)制造工艺复杂，加工精度要求高。不同构件间工艺顺序不同，加工时间存在较大差异。

(2)双资源约束。航空构件因其特殊性，在制造过程中需严格把关，关键构件需高精度设备与高技能员工协同完成。

(3)按设备组加工，数控设备居多。航空构件制造车间常按机群方式布置，不同设备组配备不同员工且其能力均具有柔性，数控设备除上下料外无需人员辅助。

综上述所述，本文考虑将其抽象为扩展双资源约束柔性作业车间调度问题(Extend Dual Resource Constraints, EDRC)。

双资源约束柔性作业车间调度(Dual Resource Constraints, DRC)问题在柔性作业车间调度(Flexible Job shop Scheduling Problem, FJSP)的基础上增加了设备与人员资源约束，是一种更复杂的NP-Hard问题[3]。鉴于此类问题的随机性与复杂性，受到国内外学者的广泛关注。Nelson[4]首次关注设备与人员资源问题，并将问题定义为双资源约束问题。Li等[5]采用改进分支种群算法求解DRC问题，使得完工时间及成本最小化。Cao等[6]针对DRC问题采用基于工序的二段式编码方式，设计一种包含能动解码方式及有效交叉算子的改进免疫遗传算法求解以提高算法的搜索能力，在实例仿真阶段假设所有工序均为机加工序且由普通机床加工。陈呈频等[7]设计了一种改进智能水滴算法求解双资源约束问题以使成本最小化，假设员工可操纵任一台设备即具备全部柔性，但在实际生产中员工较难满足全部柔性。多数已有文献在模型构建上普遍理想化，例如，假定工件工序均为普通机加工序，工序加工全程需员工参与；员工具备全部柔性；忽略数控设备参与工件加工等，上述假设条件很难运用于实际生产环境。近年来，动态环境及准备时间等影响因素受到重视。黄媛等[8]针对动态条件下的DRC问题设计了三层调度系统及染色体还原机制，降低了随机扰动对调度的影响。Wu等[9]利用混合遗传算法求解考虑员工具有学习遗忘效应的DRC问题。

近十几年来，越来越多基于模拟自然现象及生物进化的元启发式算法应用于DRC问题，如遗传算法(Genetic Algorithm, GA)[10]、粒子群算法(Particle Swarm Optimization, PSO)[11]、变邻域搜索算法(Variable Neighborhood Search, VNS)[12]、模拟退火算法(Simulated Annealing, SA)[13]及果蝇优化算法(Fruit Fly Optimization Algorithm, FOA)[14]等。教与学优化(Teaching-Learning-Based Optimization, TLBO)算法是由Rao等[15]于2010年提出的一种新型基于群体智能的进化算法，并广泛应用于各类组合优化问题。Zheng等[16]研究多技能资源约束项目调度问题并利用TLBO算法求解，在教和学两阶段均采用交叉操作进行学习。Tuncel等[17]利用TLBO算法优化工业装配系统中的双边线平衡问题，以提高产线效率。Xu等[18]率先采用TLBO算法求解具有模糊作业时间的柔性作业车间调度问题，以完工时间为优化目标并获得较优调度方案。

本文结合航空构件在制造过程中的实际情况，在DRC问题基础上考虑数控设备参与加工、装夹准备时间、构件工艺上存在机加/非机加工序交替和重要工序需特定设备与人员资源要求，提出一种扩展双资源约束柔性作业车间调度问题(EDRC)并构建调度模型。目前，采用TLBO算法求解DRC问题的相关文献较少，本文首次采用并设计了多小组协同教与学优化算法(Multi-group TLBO, MTLBO)求解EDRC问题，以确定工序维、设备维和人员维的选择排序问题。最后，在避免设备及人员使用冲突的情况下，使得完工时间、总拖期、能耗和成本最优。

1 扩展双资源约束柔性作业车间调度模型

1.1 问题描述

通过为各工序选择最合适的“设备—工人”组合，优化各设备上机加工序执行次序，使得完工时间，总拖期，能源消耗及加工成本最小。其他假设条件如下：

(1)设备、工件及员工在零时刻均空闲可用;

(2)每台设备在同一时刻最多加工一个工件，每个工件在同一时刻最多被一台设备加工;

(3)工件加工时间包含运输时间、卡具及刀具更换等辅助时间;

(4)员工能力具有柔性且效率一致;

(5)设备加工期间不允许中断、抢占。

1.2 模型构建

1.2.1 目标函数

(1)完工时间最小 产品制造周期是衡量企业生产效率的重要指标。本文将其定义为所有工件中的最大完成时间。

min(f1)=min(maxCi),∀i。

(1)

(2)总拖期最小 交货期直接影响企业信誉及客户满意度，按期交货有助于企业的资金周转。本文定义总拖期为所有工件的拖期之和。

(2)

(3)总能耗最小 随着能耗成本的攀升与节能思想的深入，企业愈发重视能耗指标。加工过程中能耗可视为由设备空转能耗(Ew)与设备加工能耗(Ed)两部分组成。为更贴近实际生产，设备完成本机全部加工任务后即可停止。

(3)

(4)生产成本最小 生产成本是直接影响企业利润的重要因素，本文视生产成本由机床使用费用(Fm)、员工费用(Fw)、原材料成本(Fs)及电力成本(Fe)四部分构成。

min(f4)=Fm+Fw+Fs+Fe

(4)

结合企业对不同目标的期望差异及不同目标间的重要性，采用式(5)对上述目标加权整合。

min(F)=ω1f1+ω2f2+ω3f3+ω4f4。

(5)

1.2.2 约束条件

(6)

(7)

(8)

XijkXijr(ETijk-STijr)×(STijk-ETijr)≥0；

(9)

XijklXfpkl(ETijkl-STfprl)×(ETfprl-STijkl)>0,

mk或mr为非数控设备；

(10)

(11)

mk或mr为数控设备。

(12)

其中：式(6)表示工序的加工时间由基本加工时间、上料时间和下料时间组成；式(7)表示工序需满足工艺路线要求；式(8)表示每台设备在同一时刻至多加工一个工件；式(9)表示每个工件在同一时刻至多能被一台设备加工；式(10)表示工人操纵非数控设备时，需参与工序的整个加工过程；式(11)和式(12)表示工人只参与数控设备与上料与下料环节，其他时间可参与其他设备加工过程。

2 多小组协同“教”与“学”优化算法

TLBO算法是一种群体智能进化算法，教师与学生组成的班级相当于进化算法中的种群。该算法通过模拟教师授课与学生自学两个阶段来实现群体在优化目标上的整体提升。标准TLBO算法对教师与学生单一分组，在求解过程中速度慢且易陷入局部最优[19]。

本文设计了一种求解EDRC问题的MTLBO算法对学生群体进行分组教学。针对求解离散型问题，对标准TLBO的两阶段连续更新公式进行离散化，在维持核心框架不变的基础上引入多种学习算子，以增强离散解空间内的全局搜索能力。在教阶段，各组设置一名组长对所在小组教学；在学阶段，根据适应度值优劣将学生分为优生与差生，分别执行所设计的纵向局部搜索学习和横向学习策略。最后，当某小组连续L代平均适应度值未提升时，执行基于最优小组的组间交流操作，实现对组内成员的扰动。算法各阶段具体操作在下文详细阐述，算法流程图如图1所示。

2.1 编码机制

与其他优化算法类似，在求解优化过程中需建立个体与实际调度的映射关系。考虑到EDRC问题特性，本文设计了三层编码机制随机初始化每名学生。第一层为工序维OS,采用基于工序编码方式，长度等于总工序数m×n，每个工件的各个工序在OS中由该工件号表示，工件号的第i次出现即表示该工件的第i道工序；第二维为设备维MS，根据工件数分成n个子片段，第i片段第j个数字对应加工数分成n个子片段，第i片段第j个数字对应加工Oij的设备在候选设备集Mij中的位置；第三层为员工维WS，编码方式与MS类似，第i片段第j个数字代表参与Oij加工的员工序号，编码示意图如图2所示。

该编码表达3个工件由5名工人在6台设备上加工的调度，其中工件1、工件2和工件3各包含2道工序、3道工序和2道工序。由解码工序维OS可知，工件的加工顺序为O31→O21→O11→O12→O32→O22→O23。针对O31结合MS与WS可知，O31由工人W4在M1上完成，其余工序以此类推。

2.2 解码机制

不同解码方法会对调度结果产生影响，贪婪插入解码[20]及全主动解码[21]两种解码方法可以有效缩短完工时间。本文在贪婪插入解码基础上，综合考虑人员柔性与数控设备属性，设计一种适用于EDRC问题的主动解码方法，具体步骤如下：

步骤1自左向右读取OS向量中的工序Oij，从MS与WS向量中提取其对应设备mk及人员wl。

步骤2获取工序Oij加工时间Pijk，寻找设备mk上所有可用空闲时间[TSmk,TEmk]，员工wl所有可用空闲时间[TSwl,TEwl]。TS，TE分别对应空闲开始时间与结束时间。

步骤3按式(13)计算Oij最早开始加工时间ta：

ta=max(Ci,(j-1),TSmk,TSwl)。

(13)

步骤4判断工序是否满足插入条件。非数控设备按式(14)，数控设备按式(15)判断Oij是否满足插入规则，若不满足，则安排在mk及wl最后一道工序结束后进行加工，开工时间tb由式(16)计算，主动解码示意图如图3所示。

ta+t0+Pjkl+t1≤min(TEmk,TEwl)，

(14)

ta=min{[(ta+t0+Pijl+t1)≤TEmk]∧

[(ta+t0)∈[TSwl,TEwl]]∧

[(ta+t0+Pijl+t1)∈[TSwl,TEwl]]}，

(15)

tb=max(LMk,LWl)。

(16)

其中：LMk表示设备k上最后工序完工时间，LWl表示工人l执行完最后工序的时间。

步骤5重复步骤1～步骤4，直至所有工序均安排完毕。

2.3 “教师”阶段

教师阶段，利用教师与学生之间的差异性向学生传授知识，以提高班级整体学习水平。针对本文所提算法，选出每组中适应度值最优个体作为该组教师，负责本组的教学任务。教学过程如下：

首先由式(17)计算每名学生与教师间的差距D_Mi。

D_Mi=ri×(Mteacher-TF×Mmean)。

(17)

式中：ri=rand(0,1)表示学习步长；TF=[1+rand(0,1)]表示教学因子；Mteacher，Mmean分别表示教师成绩和当代成绩平均水平。

其次，每名学生根据D_Mi按式(18)向教师靠拢。

(18)

对于离散型优化问题，混合采用多种交叉变异算子可提高算法的搜索能力及收敛性能[22]，故针对问题编码特性设计3种离散教学算子，如图4所示，以避免陷入局部最优。根据式(17)计算个体间离散差，教学过程中OS维随机执行优先操作交叉POX(precedence operation crossover)或基于工件交叉JBX(job-based crossover)，MS，WS维执行两点交叉TPX(the two-point crossover)[23]，维持群体多样性同时扩大搜索范围。若教学后成绩提高则接受教学后个体，否则维持原个体不变。

2.4 “学生”阶段

学生阶段模拟学生互相学习的过程，取长补短共同进步。标准教与学算法中单一形式的相互学习不便于区分学生学习能力，难以做到因材施教。本文针对优生与差生的学习能力差异，设计了两阶段差异性学习策略，即优生执行纵向学习策略，差生执行横向学习策略，便于学生充分拓展与发掘知识提高个人成绩。第i次迭代中，学生p向q学习的过程按式(19)和式(20)进行：

(19)

(20)

式中F(Xi,p)表示第i代个体p的适应度值，当F(Xi,p)优于F(Xi,q)时接受新个体，否则维持旧个体不变。

与教师阶段相似，学生阶段在维持学习框架不变的基础上，引入3种自学算子以适应离散型问题，如图5所示。OS维随机执行3点邻域全排列变异或互换变异算子。MS，WS维执行多点变异算子，随机选择3个位置并替换为其他合法值。

该阶段对小组中全部个体进行适应度值评估，排名前1/2的学生定义为优生，其余学生认定为差生。

2.4.1 “优生”纵向自学习策略

优生相比差生普遍具有更强的自学能力，通过对自身擅长领域进行深入挖掘，提高自身成绩。针对不同优生Xi的成绩，赋予不同的探索次数N(i)。文献[24]研究发现，赋予自学能力强的优生更多探索次数一方面有利于个体到达更远的邻域，另一方面有利于对个体的邻域进行更加细致的搜索以提升算法局部搜索能力，探索次数N(i)由式(21)确定：

(21)

式中：Fi表示该小组内第i个个体的成绩；Fmax、Fmin为小组内最优和最差的成绩；UL为设定的探索次数上限；LL为探索次数下限。考虑到算法执行效率并参考文献[25]，设定UL=15，LL=1。

若经过纵向自学习后的当前个体Xq优于原个体Xp，则接受当前个体，否则维持原个体不变，纵向自学习步骤如图6所示。

2.4.2 “差生”横向互学习策略

鉴于差生自学习能力薄弱的特征，采用组间互学方式向其他学生学习。通过向更优个体学习，有机会搜寻差生擅长的学习领域而成为优生，从而进行纵向自学习，提升整体的学习成绩。具体学习方式为：根据成绩排名，个体Xp随机选取比其排名更优的个体Xq学习，横向学习过程按式(19)及式(20)进行。

2.5 基于最优小组协同交流阶段

为全面提高各小组的学习效果，当某小组的学习成绩得不到进一步提升时，执行组间交流操作与其他小组交流学习心得。本文设定当某小组的最好成绩连续L代未提升时，采用轮盘赌方式在最优小组(平均成绩最佳)中选择H名学生，替换当前小组中最差的H名学生，最优小组中每名学生的选中概率

(22)

算法迭代初期，为充分发挥个体创造力，执行协同交流操作时参与交流的学生数H应较小。随着迭代次数增加，个体的成绩与能力成绩趋于稳定，应适当增加交流人数以增强协同交流强度，小组中参与交流的学生数

H=Gen/C。

(23)

式中：Gen表示当前迭代次数，C为常数。组间交流操作可视为对陷入局部最优的小组进行扰动，有利于维持子代种群多样性，并提升算法的全局搜索能力。

3 实例仿真与分析

实例分析通过两方面展开：①在FJSP问题基准算例的基础上生成EDRC测试算例，通过与其他算法求解结果进行比较验证本文算法的有效性；②从实例应用角度，对某航空设备制造企业的加工数据进行整理，综合车间内部设备与员工能力，通过MTLBO算法得出调度方案，验证算法对解决EDRC问题的有效性及模型的正确性。算法在CPU-i5，3.4 GHz，内存8.00 G的PC机上利用Python 3.6编程实现，算法针对各算例独立运行20次。

3.1 测试算例仿真与分析

本文研究EDRC问题且考虑4个优化目标，在FJSP问题的基准算例MK01-MK10[26]基础上还需增加员工数量等加工信息进行扩充，以证提出算法的有效性，具体加工变量取值如表1所示。

表1 加工变量信息表

基于算例MK01～MK10与表1中加工变量信息随机生成10组测试算例IMK01～IMK10，对算法的有效性进行测试与验证。对规模适中的IMK04算例采用Taguchi[27]正交试验法并参照文献[25]，确定参数设置为：小组个数为4，每组学生规模为100，L=20，C=50，MaxGen=200，ω1=0.6，ω2=0.1，ω3=0.2，ω4=0.1。生成算例通过MTLBO及另外两种算法TLBO[28]，混合遗传算法(Hybird Genetic Algorithm, HGA)[29]求解，其中TLBO，HGA参数设置与其原文献保持一致算例，运行结果比较如表2所示。

表2 算例运行结果比较

由表2中运算结果可知，利用本文提出的MTLBO算法求解算例时，在10个测试算例中相比于其他两种算法均明显占优，表明所设计的两阶段自学策略及分组教学方式可有效提高算法的鲁棒性及搜索能力。因此，MTLBO算法可有效求解EDRC问题并具有较强的竞争力。

由表2运算结果可知，利用本文提出的MTLBO算法求解算例时，在10个测试算例中相比于其他两种算法均明显占优，表明所设计的两阶段自学策略及分组教学方式可有效地提高算法的鲁棒性及搜索能力。因此，MTLBO算法可有效求解EDRC问题并具有较强的竞争力。

3.2 实例应用仿真与分析

通过整理分析某航空设备制造企业生产车间的数据，给出7个工件的工艺流程及约束，每道工序可至少在一台设备上加工，但加工效率与能耗存在差异。表3中给出各工序操作内容及在可选设备上的运行能耗与加工时间。依照工艺将工序划分为机加工序(车、铣、镗等操作)及非机加工序(热处理、钳、检验操作)。车间现有员工6人，设备8台分为4组：普车组、数车组、数铣组及镗床组。每组中设备数量、性能及对应员工均不同，表4列出各工序操作对应的设备组及可选人员。设备M1～M8的空转单位能耗分别为：0.56，0.45，0.48，0.96，1.05，0.30，0.42，0.40。员工单位工时费用为15，平均工业电价e=0.77。

表3 工件工序加工信息

续表3

表4 工序可选设备与员工信息

3.2.1 考虑双资源(DRC)约束下的实例测试

首先，考虑双资源约束情况，即忽略数控设备对调度方案的影响，此时假设设备均为非数控。因某些重要工序需要高精度设备及高能力级别的员工协同加工，故存在设备约束及人员资源约束。采用MTLBO算法进行求解(参数与测试实验中保持一致)。在最佳的调度方案下，案例的各目标值分别为f1=74，f2=19，f3=256.9，f4=6 618.1。在此调度方案下关键设备(M6，M7)的稼动率为89.5%及77.6%。调度方案Gantt图如图7所示，图中M1上第一个“2-1-4”表示工序O21由员工4在设备1上完成。

3.2.2 考虑扩展双资源(EDRC)约束下的实例测试

考虑数控设备对调度方案的影响，数控设备切削过程中按程序运行，不需员工参与，释放了人员资源约束。采用本文提出的多小组协同教与学优化算法进行求解，得到的最佳调度方案Gantt图如图8所示。例如针对图中方框O47和O15均需员工1加工时，其执行过程为员工1在M6上装夹完J4后数控设备M6开始自动切削，员工1～M7上装夹J1，M7开始自动加工，员工1返回M6，下料操作同理，故调度方案避免了人员使用冲突。此外，如O72及O75之间为非机加(钳、检验)工序预留出处理时间，相比于只考虑机加工序及普通机床调度的传统双资源问题更贴近实际生产。图8中调度方案对应的目标分别为f1=67，f2=6，f3=198.8，f4=6 463.0，关键设备稼动率为90.9%和90.5%。相较于不考虑数控设备的情况四个目标值分别下降了9.46%、68.42%、22.62%和2.34%，关键设备稼动率分别提升了1.61%和16.67%。两种情况下的人员利用率如图9所示。

由图8和图9可知，在考虑数控设备的扩展双资源约束情况下，员工工作负荷减轻、空闲时间增多。最优调度方案预留出设备5，且员工存在较多空闲时间，有利于下批工件加工及应对员工病假等其他突发情况。

3.2.3 实例求解算法对比分析

为进一步验证本文提出的MTLBO算法对求解实际复杂车间调度问题的有效性，针对航空构件制造车间调度实例分别采用TLBO算法及HGA算法进行求解，并与本文算法进行比较。3种算法针对实例问题的两种情况，即DRC约束及EDRC约束下的求解结果见表5，在EDRC情况下的迭代收敛图如10所示。

表5 不同算法求解实例结果对比

续表5

由表5可知，MTLBO算法在实例问题的求解结果上均优于其他两种算法。从图10中可以得出，迭代过程中MTLBO算法的收敛速度和求解质量明显优于TLBO算法及HGA算法，TLBO算法因陷入局部最优求解结果并不理想。由此验证了本文提出的MTLBO算法的可行性和有效性，并可有效地运用于航空构件的实际生产中，对企业制定生产计划大纲具有指导作用。

4 结束语

本文研究了一类复杂的扩展双资源约束柔性作组协同教与学算法(MTLBO算法)，这是首次运用MTLBO算法求解此类问题。在算法核心框架不变的基础上，针对求解EDRC离散型问题设计多种学习算子，保证了算法的全局搜索能力。自学阶段优生采取纵向自学策略以对优质区域细致搜索，平衡算法全局开发与局部搜索能力。此外，独特的组间交流策略有利于维持种群多样性，避免算法陷入局部最优。通过求解测试算例验证了算法的可行性及有效性，并应用于实际航空构件生产车间，结果表明算法可有效求解出最佳调度方案并避免设备人员使用冲突，具备一定的工程应用前景。

本文未考虑到动态因素对车间调度的影响，如员工休息、设备故障及新工件到达等，这些问题将在下一步进行研究。