考虑员工负荷均衡率和交货期...单工作组多目标任务调度模型_谢乃明.pdf

第第2525卷第卷第2 2期期20232023年年4 4月月VolVol.2525 No No.2 2AprApr.20232023南京航空航天大学学报南京航空航天大学学报（社会科学版社会科学版）Journal of Nanjing University of Aeronautics and Astronautics Journal of Nanjing University of Aeronautics and Astronautics(Social SciencesSocial Sciences)考虑员工负荷均衡率和交货期的单工作组多目标任务调度模型谢乃明，李斌（南京航空航天大学 经济与管理学院，江苏 南京 211106）摘 要：工作组是装备制造过程的常见生产方式，通过不同技能水平的人员搭配和组内相互学习从而实现任务的高效处理，考虑员工负荷均衡率、交货期等因素可以更好地配置工作组资源实现工作组任务优化调度。以最大完工时间、员工负荷均衡率、总延迟时间为目标构建单工作组多目标任务调度模型，用数学化语言对交互学习效应和人员加工可中断现象进行科学表征，基于帕累托解集设计了融合启发式规则和双层关联编码的改进多目标遗传算法，并设计不同规模、不同人员结构的测试算例验证所构建模型和算法的有效性。实验结果表明，所构建的模型和算法能够实现工作组任务优化调度。关键词：团队交互学习效应；工作组任务调度；员工负荷均衡率；交货期；多目标遗传算法中图分类号：N945.1 文献标识码：A 文章编号：16712129(2023)02003812一、引 言 工作组生产制造模式是装备制造等行业的常见生产方式，如航空航天装备制造、船舶制造、精密设备制造行业受限于技术成熟度、生产工艺和加工技术的复杂性等因素影响，广泛采用以工作组为生产单元的任务调度模式，有利于工作组相互学习和配合，更好地完成任务处理。传统生产过程任务调度问题研究对象主要为单机或并行机系统，生产单元以机器（或工人）为主，而单工作组调度问题指具有一个工作组单元，且该单元由多个工人组成的调度问题，其包括如何在确定的人员结构下合理安排任务处理顺序，并且为每个任务合理分配工人，以提升整个工作组的加工效率。针对单工作组调度问题中如何在特定的人员结构下进行任务调度等相关内容已有诸多研究，从多技能工人在工作组内部的分配1，再到劳动密集型生产单元优化建模2，部分研究将工作组问题转化成二维装箱问题进行优化建模3-4，通过将人员分配和任务调度抽象成矩形在一定空间内部的排布问题实现计算复杂程度的降低，部分研究将运筹优化方法与智能算法相结合，实现医疗资源调度5、复杂装备制造6、物流网络调度7等复杂系统高价值资源或者关键资源的建模与求解，多阶段重调度8、多智能体9、分布式建模10等方法也被应用于具有工作组特征的生产系统建模过程。学习效应对复杂装备制造系统生产调度有不可忽视的影响，尤其是对工作组这类以人员为核心调度资源的生产系统。学习效应模型的研究根据任务调度场景、求解目标等有不同的侧重点，具体分为依赖于任务分配的位置11-12、依赖于位置和任务13、依赖于任务处理的标准加工时间14、依赖于任务处理的实际加工时间15、依赖于任务处理的标准加工时间和任务16、依赖于任务处理的实际加工时间和任务17等，在以往考虑学习效应调度的研究中，学习效应模 型 被 学 者 广 泛 应 用 于 医 疗 系 统18、半 导 体 制造19、装备制造20以及项目管理21等领域，但大都忽略了任务加工单元内部对外部学习能力的影响。在实际生产制造环境中，考虑工作组场景的柔性、复杂性、鲁棒性要求，通常在建模阶段设置多个目DOI：10.16297/j.nuaass.202302007基金项目：国家自然科学基金资助项目（72171116）；中央高校基本科研业务费资助项目（NP2020022）；江苏省“333高层次人才培养工程”计划资助项目。收稿日期：2022-05-10作者简介：谢乃明，男，教授，主要研究方向为灰色系统理论、复杂装备研制管理、工业工程。第 2期谢乃明,李斌：考虑员工负荷均衡率和交货期的单工作组多目标任务调度模型标以保证解的可用性。Allahverdi等研究无等待流水车间调度问题，考虑在总完工时间有限的情况下最大限度减少总延迟时间22；孔玲爽等为研究一类在线任务调度问题，根据生产系统的实际情况建立多目标规划模型，并对模型进行字典序优化以控制多质量指标下的配料方案优化23；刘佳等以最小化拆卸成本投入和最小化环境危害程度为目标构建双目标任务调度优化模型，计算解集的帕累托前沿面对模型进行求解24。现有研究缺少针对组内相互学习现象的集成考虑，大部分研究也多围绕单目标问题展开分析，随着国家大力推动高端装备制造业发展和传统产业优化升级，结合工作组特性（团队交互学习效应、人员加工可中断、多目标等）开展的任务调度研究无疑会成为未来智能制造过渡和发展的重点。本文在考虑学习效应和人员加工中断的工作组单目标任务调度模型25的基础上，考虑员工负荷均衡率和任务交货期构建单工作组多目标任务调度模型，通过启发式规则的融合和编码策略的改进，构建基于精英保留策略的非支配排序遗传算法。实验结果表明，任务能在工作组中得以科学分配，实现工作组内部不同技能水平工人的有效利用和调度目标最优，通过不同规模的算例分析对以工作组为生产单元的制造模式提出管理建议。二、单工作组多目标任务调度问题的数学描述 在大多数以工作组为生产制造单元的生产制造系统中，任务调度的方案往往综合多个目标，相互权衡后才会实施，如在生产制造场景中，考虑以最小数量的机器、人员、物料完成特定数量的任务，以保证成本最低和利润最大，在物流配送等任务调度场景中，为使顾客满意度最高，在利润和成本的可接受范围内，需要保证延迟/提前时间、延迟/提前任务数目的目标最优。研究考虑限制工作组任务调度问题的多个目标，如最小化最大完工时间、最大化工人学习均衡率、最小化总延迟时间，及其相关约束构建面向工作组任务调度问题的多目标任务调度模型。模型的建立基于以下假设：工人加工过程中断后，学习水平不退化；学习过程可在不同任务间迁移和延续；单工作组不允许多个任务同时加工，当该任务加工完成时，分配到该任务的工人才可以释放；任务正在加工时，若该任务尚未完工，则工人不进行学习时间的更新。1.参数定义（1）符号和变量Gi为工作组的编号，i=1，2，n，n为工作组的数量研究面向单工作组任务调度，i=1；Gij为工作组内部人员的编号，j=1，2，mi，mi为工作组Gi的总人数；GHi为工作组Gi内部的高水平工人数目，GHij表示工作组Gi内的高水平工人编号，j=1，2，GHi；GLi为工作组Gi内部的低水平工人数目，GLij表示工作组Gi内的低水平工人编号，j=1，2，GLi；Bi为工作组Gi的学习均衡率；Jk为任务编号，k=1，2，l，l为任务总数量；STk为某一工作组子集开始处理任务Jk的准备时间；Sk为任务Jk的开始处理时间；Ck为任务Jk的完工时间；Pk为任务Jk的处理时间；Pk为任务Jk的理想处理时间；Cmax为最大完工时间；JMk为任务Jk基本需求加工人数；JMHk为任务Jk分配的高水平工人数目，JMHk=|GHimiJMk；JMLk为任务Jk分配的低水平工人数目，JMLk=|GLimiJMk；（2）决策变量Xik为 0-1决策变量，若任务Jk被分配到工作组Gi处理，则为 1；否则为 0。Xijk为 0-1 决策变量，若任务Jk由工作组Gi中的工人Gij处理，则为 1；否则为 0。2.优化目标（1）最小化最大完工时间该优化目标表示最小化任务的最大完工时间，用公式表示为：min Cmax=min()max Ck,k=1,2,l(1)（2）最大化员工负荷均衡率该优化目标表示最大化工作组工人的员工负荷均衡率，员工负荷均衡率由B表示，用公式表示为：39第 25卷南京航空航天大学学报(社会科学版)http:/maxB=1-j=1mi|k=1lXijk-j=1mik=1lXijkGHi+GLij=1mik=1lXijk,k=1,2,l;j=1,2,mi(2)该目标与最小化最大完工时间是存在冲突的。在工人组成小组分配到任务的阶段，存在为最小化最大加工时间而重复利用某几位工人的情况，通过固定工人的重复劳动加快学习进程，以缩短后续任务的完工时间，部分工人的重复利用导致工人学习进程的差距加大，进而降低工作组内部工人学习均衡率。反之为提升均衡率而重复利用部分工人，导致最大完工时间增加的情况同样存在。（3）最小化总延迟时间该 优 化 目 标 表 示 最 小 化 所 有 任 务 的 延 迟 时间总和，设任务交期为Dk，k=1，2，l，Tk表示任 务 k 延 迟 时 间，Tk=Ck-Dk，Ck-Dk 00，Ck-Dk 0，k=1，2，l，用公式表示为：min T=k=1lTk(3)3.约束（1）基本约束i=1nXik=1,i=1,2,n,k=1,2,l(4)i=1nj=1miXijk=JMk,k=1,2,l(5)CkXijk-PkXijk CkXijk+STkXijk,i=1,2,n,j=1,2,mi,k(k)=1,2,l,Ck-Pk Ck-Pk(6)CkXik-PkXik CkXik+STkXik,i=1,2,n,k(k)=1,2,l,Ck-Pk Ck-Pk(7)JMHk=|GHiXikmiXikJMk(8)JMLk=|GLiXikmiXikJMk(9)基本约束中，式（4）限制一个任务最多只能分配到一个工作组；式（5）限制一个任务最多只能分配到一个工作组全部人员的真子集；式（6）限制每个已分配的工作组人员真子集同一时刻只能处理一个任务；式（7）限制同一工作组处理某一任务的开始时间不早于此任务开始前的准备时间和上一项任务的完成时间之和；式（8）限制为任务分配的工作组子集中低水平人员数目；式（9）限制为任务分配的工作组子集中高水平人员数目。（2）完工时间相关约束Ck=Sk+Pk,k=1,2,l(10)Ck-1 Sk,k=1,2,l(11)Si Xijk+Pi Xijk+Pi+1 Xi,j+1,k+Pj Xi,j-1,k Sj Xijk,i=1,2,n;j=1,2,mi;i 00,Ck-Dk 0,k=1,2,l(13)式（13）限制Tk的取值范围，当Ck-Dk 0时，Tk=Ck-Dk；当Ck-Dk 0时，Tk=0。三、融合规则和双层关联编码策略的改进多目标遗传算法设计 1.双层关联编码基于启发式规则的进化算法25在处理工作组任务调度问题时具有一定的随机性和不可逆性，弱化了任务处理顺序和工人分配方案间的相互影响，因此它提出双层关联编码的思路，通过单染色体向多染色体的转变综合考虑任务处理顺序和工人分配方案间的相互影响，在满足需求人数限制的基础上保证人员学习的进程差距在可接受范围内。思路如下：（1）任务处理顺序染色体编码任务处理顺序染色体编码采用排列编码方式，随机生成任务加工顺序编码，如图 1所示。图 1 任务处理顺序染色体编码40第 2期谢乃明,李斌：考虑员工负荷均衡率和交货期的单工作组多目标任务调度模型（2）工人分配方案染色体编码工人分配方案染色体编码采用二进制编码方式，10 个位置分别代表 10 个工人的分配情况，0 表示工人不会被分配到该任务加工处理，1 表示工人将会分配到该任务进行加工处理。每个任务的工人分配方案占据 10 个编码为 1 组，按照任务处理顺序染色体上的编码顺序后延（如图 2所示）。（3）关联阶段在该阶段，工人分配方案染色体的 10组编码将分别求和，并和对应任务的需求加工人数做关联，如果求和值大于关联的需求加工人数，则随机挑选该组编码为“1”的值修改为“0”，挑选数量为“该组求和值-任务需求加工人数”；如果求和值小于关联的需求加工人数，则随机挑选该组编码为“0”的值修改为“1”，挑选数量为“该组求和值-任务需求加工人数”；如果求和值等于关联的需求加工人数，则该组编码不作变动。经过以上三步可以得到表示任务调度方案的双层关联编码，其中第一层编码为任务的处理顺序，编码长度等于待调度任务总数量，第一位编码的序号代表首先进行任务处理的任务编号；第二层编码代表为每个任务分配的任务处理人员，编码长度等于待调度任务总数量和工作组人员总数的乘积。两层编码的交叉、变异过程独立进行并会对交叉变异后的新编码进行重关联，以保证编码逻辑的正确（如图 3所示）。2.启发式规则面向多目标工作组任务调度问题设计的外部启发式规则通过人员加工中断点的识别计算任务的处理时间，进而实现种群个体适应度值的计算，基本步骤如下：步骤 1：更新工人总学习时长，以学习水平为基础将工人划分为高水平和低水平两个类别；步骤 2：根据任务基本需求人数JMk确定JMHk和JMLk，计算人员加工不发生中断的理想加工时间；步骤 3：判断工人Gij的第e个中断区间开始时刻aehXijk或结束时刻behXijk和acount+APacountk 的关系，其中num=j=1mi2 ijXijk；步骤 4：寻找中断加工的工人，更新中断点集合，重新计算理想加工时间，重复步骤 2；步 骤 5：count=f=maxe|aehykh Ck时，更新所有工人的加工时间，更新中断区间列表。3.快速非支配排序假设算法初始化的种群中调度方案个体的数目为 P，每个个体编码代表了一种工作组任务调度方案，为得到帕累托最优解集，需要计算每个调度方案 p 的目标值，并以此为基础寻找调度方案 p 的支配个体和被支配个体。该环节的计算复杂度为O(m(2N)2)，包括计算调度方案 p 支配的其他个体支配集合Sp，并计算所有支配方案 p的解的数目np，算法伪代码见表 1。4.超平面上个体与参考点的关联基于帕累托的多目标优化精英保留策略主要思想是，基于每个调度方案个体的帕累托等级、调图 2 2人分配方案染色体编码图 3 多染色体双层关联阶段示意图41第 25卷南京航空航天大学学报(社会科学版)http:/度方案解集拥挤度距离挑选父代优秀个体进入新集合组成子代种群。但是高维目标很难通过拥挤度距离判断解集的分布情况，一方面是目标空间维度增加，另一方面是拥挤度距离的计算代价指数级增加。NSGA-III 算法通过在目标空间中按照一定规则分布的参考点筛选优秀个体进入子代集合。主要步骤包括以下 3步：步骤 1：对不同维度的目标函数进行标量化后确定目标空间的超平面，在超平面上按照既定规则确定参考点，连接一条从理想点指向参考点的参考线用于确定所有调度方案个体到参考点之间的距离。步骤 2：定义当某个体到参考线的距离最短时，称该个体与参考线对应的参考点有关。遍历所有个体到所有参考线的距离（点到直线的最短距离），找出所有与参考点有关的个体，将该个体加入集合Ci，设满足帕累托等级相对较低但是个体数目超过需求个体数目的对应帕累托等级个体集合为S，将集合 S 包含的个体在集合Ci中剔除，剔除后的集合定义为Ci；步骤 3：找出Ci中包含个体数量最少的集合min Ci，分下列情况讨论：如果min Ci=，min Ci，即除去集合 S包含的个体后，没有任何个体与该参考点有关，但是集合 S 中有个体与该参考点有关，则在集合 S 中抽取到参考线距离最短的个体加入新集合组成子代种群；如果min Ci=，min Ci=，即除去集合 S包含的个体后，没有任何个体与该参考点有关，集合 S 中也没有个体与该参考点有关，则剔除该参考点和对应的参考线，重复步骤（3）；如果min Ci，即除去集合S包含的个体后，有至少一个个体与该参考点有关，则在集合 S中抽取到参考线距离最短的个体加入新集合组成子代种群，若集合 S不存在个体与其相关，则在其他个体中抽取到参考线距离最短的个体加入新集合组成子代种群。5.选择、交叉、变异在交叉策略选择中，针对二进制编码的工人分配方案染色体采取“均匀分布交叉”策略，针对排列编码的任务处理顺序染色体采取“部分匹配交叉”策略。选择策略为“锦标赛选择”策略。在变异策略选择中，针对二进制编码的工人分配方案染色体采取“二进制变异”策略，针对排列编码的任务处理顺序染色体采取“逆转变异”策略。在基于双层关联编码的多染色体 NSGA-III 算法执行过程中，交叉、变异操作后需要执行“双层关联编码”阶段的关联操作，以满足任务需求加工人数的限制，保证个体的合法性。6.融合规则和双层关联编码策略的改进多目标遗传算法步骤算法步骤如图 4所示：步骤 1：初始化并生成问题对象，读取工作组基本信息和任务基本信息；步骤 2：通过双层关联编码策略生成初始种表表 1 Algorithm 快速非支配排序算法Input:初始种群 POutput:计算调度方案 p支配的其他个体支配集合Sp，并计算所有支配方案 p的解的数目np1:for p in P do2:Sp=3:np=04:for q in P do5:if p q then#如果 p支配 q6:Sp.append(q)#把 q添加到Sp7:else8:np+=1#把np加 19:end if10:end for11:if np=0 then#如果该个体的np为 012:p_rank=1#则该个体为 Pareto第一级13:F1.append(p)14:end if15:end for16:i=117:while Fi do18:Q=19:for p in Fi do20:for q in Sp do#对Sp个体进行排序21:np-=122:if np=0 then23:qrank=i+124:Q.append(q)25:end if26:end for27:end for28:i+=129:Fi=Q30:end42第 2期谢乃明,李斌：考虑员工负荷均衡率和交货期的单工作组多目标任务调度模型群，在编码规定的范围内随机生成具有 P 个个体的初始种群；步骤 3：适应度计算，通过人员加工中断点识别的启发式规则计算个体适应度；步骤 4：判断是否为初始种群，如果是初始种群，则进行快速非支配排序确定种群个体的帕累托等级，并进行选择、交叉、变异，进行关联编码操作，符合规则后生成子代种群，将父代、子代个体合并；步骤 5：对不同维度的目标函数进行标量化后确定目标空间的超平面和参考点；步骤 6：遍历所有个体到所有参考线的距离（点到直线的最短距离），找出所有与参考点有关的个体，通过自然选择筛选与参考点距离最近的个体，直至新父代满足种群规模要求；步骤 7：形成新父代个体后进行交叉、变异生成子代个体，进行关联编码验证，重复步骤 3。四、仿真实验结果与分析 1.案例情景设计某工厂任务处理过程以 10 人制工作组为调度单元，工人独立加工任务的基本人时在 30，80 随机分布，多目标问题求解中高水平工人学习率为40%（学习因子=-0.4），低水平工人学习率为 20%（学习因子=-0.2）。由于学习能力越强的工人加图 4双层关联编码的多染色体 NSGA-III算法流程43第 25卷南京航空航天大学学报(社会科学版)http:/工时间越短，用学习因子代替学习率以便于单工作组团队交互学习效应表征公式的计算，因此学习因子为负值表示学习效应，正值表示退化效应。每个工人有 3 个中断区间，10 人制工作组的中断区间在0，41 内以固定步长 0.5分布，加工编号为 110的任务，任务的交期在 4，40 内以固定步长 4 分布。现 有 一 批 共 10 个 同 零 件 族 任 务Jk，JMk和Pk见表 2。2.算法性能分析（1）评价指标遗传算法、粒子群算法、差分进化算法等智能进化算法在解决任务调度多目标优化问题时都可以得出满足约束且表现较好的解集。不同类型的多目标进化算法适用于不同场景的多目标优化问题，尤其在求解高维复杂问题时不同算法会在不同的算法性能指标范围内相互领先，不存在完全最优的多目标进化优化算法，各有擅长之处。本文针对考虑团队交互学习效应的多目标人员加工可中断任务调度问题求解过程复杂，没有已知的帕累托前沿面可以作为性能度量的参考，因此确定以下两个指标作为算法性能评价指标。分布性评价指标。间距（Spacing）被称为 SP指标。在多目标优化遗传算法求解的最优解集中，不同解分布在二维、三维、更高维目标空间中。当解集元素集中分布在目标空间的某个区域时，说明最优解在某个目标下整体较差；当解集元素均匀分布在目标空间中时说明解集分布均匀，解集元素的解可以在不同情景下根据实际情况选择最优解。因此 SP 指标表示解集中的各个元素在目标空间中的分布情况，可以对算法所求帕累托最优解集各个元素的分布和覆盖程度进行描述。计算公式为：SP=|1ni=1n()di-d212-dn为种群中个体的数目，di是帕累托最优解集中第 i 个解元素与帕累托前沿之间的最小实际距离。SP 指标值和帕累托最优解集的均匀程度成反比，SP 越小，算法所求帕累托最优解集的分布越均匀，解集质量越高。多 样 性 和 收 敛 性 评 价 指 标。超 体 积 度 量（Hypervolume）被称为 HV 指标。HV 可以综合评价多目标算法的两个主要性能收敛性和多样性。抽象来看，HV 指标用于度量目标空间的超体积，目标空间需要满足至少存在一个非占优解集 X中的个体优于目标空间中的其他非占优个体。若 P 记为真实帕累托前沿参考，由于考虑团队交互学习效应的多目标人员加工可中断任务调度问题的复杂性，没有已知的帕累托前沿面可以作为性能度量的参考，因此将独立目标最优值组合成参考向量。计算公式为：HV(X,P)=x XXv(x,P)v(x，P)表示非占优解 x 与帕累托前沿参考 P形成空间的超体积，HV 指标值和帕累托最优解集的收敛性和多样性表现成正比，HV 越大，帕累托最优解集的收敛性和多样性表现更加接近真实帕累托前沿，质量越高。（2）性能分析由于模型非线性，加工时间随人员分配的变化而变化，约束数量与分配人员对应的中断区间和总学习时长有关，因此精确式求解方法难以解决该问题。研究以高水平：低水平人员是 4：6 为例验证设计的基于双层关联编码的多染色体 NSGA-III算法（种群规模 NIND=20；最大迭代数 MAXGEN=200；交叉概率 XOVR=0.8；变异概率 Pm=0.2）与基于启发式规则的 NSGA-II算法25、RVEA 算法的优势。NSGA-III 通过引入参考点来保持种群多样性，针对工作组调度问题设计的双层关联编码能更好地匹配单工作组任务调度问题中人员分配和任务顺序调度的实际背景。本文分别通过目标值对表 2任务基本需求人数和基本工时编号12345678910人数（个）36568107594任务 k基本加工时间（h）1214222817131819182344第 2期谢乃明,李斌：考虑员工负荷均衡率和交货期的单工作组多目标任务调度模型比（最小最大完工时间、最大工人学习均衡率、最小总延迟时间）、性能指标对比（非支配个体数目、运行时间、HV、SP）分析设计的基于双层关联编码的多染色体 NSGA-III 算法有效性。实验仿真环境为：Window 10 64 位 操 作 系 统，CPU 为 Intel（R）Core（TM）i5-6300HQ，处 理 器 主 频 为 2.30 GHz，12G内存，编程环境为 Python 3.7.7。计算结果见表 3、表 4。由表 3 可以看出，采用双层关联编码的改进 NSGA-III算法和 RVEA 算法解的质量都显著高于基于启发式规则的改进 NSGA-II算法；在最大化工人学习均衡率目标 Obj2里，改进 NSGA-III算法更优于 RVEA 算法。说明在本研究中的高维目标工作组任务调度问题中，采用双层关联编码的改进 NSGA-III算法可以求得较好的解集。但是在目标值的方差上，基于启发式规则的改进 NSGA-II算法方差较小，能够保持求解质量的稳定性。表 310个任务规模算例下改进 NSGA-III、改进 NSGA-II25、RVEA目标值对比算例规模10个任务NIND=20MAX_GEN=200均值方差次序12345目标值OBJ1改进NSGA-III31.144834.307333.388533.734632.688233.05271.1849改进NSGA-II45.343344.983945.203246.649146.768345.78960.5777RVEA31.819832.397633.231831.205332.495432.23000.4641OBJ2改进NSGA-III0.91360.89010.91980.91050.91760.91030.000113改进NSGA-II0.89000.88720.89080.89210.89240.89050.00000RVEA0.84880.86090.78160.85260.86950.84270.000983OBJ3改进NSGA-III10.782627.008022.681122.792722.010421.055029.5074改进NSGA-II108.286594.5397109.2923112.6764117.5540108.469858.9952RVEA19.419315.059434.986513.127117.521620.022860.5436表 410个任务规模算例下改进 NSGA-III、改进 NSGA-II、RVEA性能指标对比算例规模10个任务NIND=20MAX_GEN=200均值方差算例规模10个任务NIND=20MAX_GEN=200均值方差次序12345次序12345性能指标 1运行时间改进 NSGA-III32.483533.476835.349033.399031.955233.33271.3419性能指标 2SP改进 NSGA-III0.825211.26153.63162.80042.77224.258213.1117改进 NSGA-II35.699035.194835.866336.116535.983035.77190.1021改进 NSGA-II6.12304.99975.13873.80604.49694.91290.5843RVEA39.362836.905138.752038.975237.311938.26140.9409RVEA2.79271.77577.69343.00111.35063.32275.1539HV改进 NSGA-III0.01000.07520.03360.03820.04090.03960.0004非支配个体数改进 NSGA-III141515151414.60000.2400改进 NSGA-II0.07200.06510.06540.06100.05930.06460.0000改进 NSGA-II202020202020.00000.0000RVEA0.02960.03960.04440.00850.03690.03180.000159RVEA886486.80002.560045第 25卷南京航空航天大学学报(社会科学版)http:/由表 4 可以看出，采用双层关联编码的改进NSGA-III 算法运行速度最快，且解的分布情况较好。虽然找到的非支配个体数目明显少于改进 NSGA-II算法，但是改进 NSGA-III算法的求解质量要远高于改进 NSGA-II算法，而 RVEA 算法虽然也采用了双层关联编码进行优化，但无论是求解时间还是寻找的非支配个体数目都落后于同样采用双层关联编码进行优化的改进 NSGA-III算法。在算法的收敛性和多样性上，采用双层关联编码优化后，收敛性和多样性得到显著改善，且将非支配解的均匀性维持在可接受的程度。NSGA-III 与 NSGA-II的不同在于如何选择帕累托等级中分布均匀的个体加入下一代父代个体，NSGA-II是运用拥挤度距离来对相同帕累托等级的个体进行选择（拥挤度距离越大越好），而 NSGA-III是运用广泛分布的参考点在三维甚至更高维的目标下来维持解集个体分布的均匀程度。当面对高维目标优化问题时，采用拥挤度距离筛选子代个体的 NSGA-II 算法的收敛性和多样性会不好，容易陷入局部最优。且由于所优化目标函数较多，帕累托前沿难以表示解的分布，此外性能指标的计算代价过大，算法结果不易评价。（3）不同目标下的调度方案分析不同目标下调度方案分析结果见图 5、图 6、图7，由图 5（a）可以看出，不同人员组合下帕累托解集的最优方案中最小最大完工时间在 10h-50h 区间内分布，随着高水平人员比例的增加，最大完工时间也在逐渐缩短，不同人员组合的最大完工时间曲线无明显交叉。由图 5（b）可以看出，不同人员组合下帕累托解集的最优方案中最大工人学习均衡率在 80%-98%区间内分布，分析原因为双层关联编码的随机性远大于启发式规则的随机性，且最小化总延迟时间的调度目标也会对均衡率目标的表征有一定影响。由图 5（c）可以看出，总延迟时间呈现和最大完工时间一致的规律，随着高水平人员比例的增加，总延迟时间也在逐渐缩短，且不出现延期任务的数目也逐渐增多。图 5 不同人员组合下 OBJ1、OBJ2、OBJ3的变化趋势图46第 2期谢乃明,李斌：考虑员工负荷均衡率和交货期的单工作组多目标任务调度模型由图 6 和图 7 不同人员组合下多目标 pareto 最优解集的调度路线可以分析在不同的非支配解中调度路线的变动。高水平：低水平人员比例在 0：10时，任务 2、6 基本保持在顺序 1 和 7，同一顺序下整体任务波动较为平均，说明该比例下各个任务对调度方案效果的影响均较为重要，其中顺序 3 上任务波动范围最大；高水平：低水平人员比例在 1：9 时，任务 6、9、10稳定在顺序 9、10、8上加工，顺序 5的加工任务在 4、5 上波动。高水平：低水平人员比例在2：8 时，顺序 10 的加工任务在 6、9 上波动，任务 2、3图 6 不同人员组合下三目标 pareto最优解集的调度路线 partA图 7不同人员组合下三目标 pareto最优解集的调度路线 partB47第 25卷南京航空航天大学学报(社会科学版)http:/有 50%的概率在顺序 5、6 上加工；高水平：低水平人员比例在 3：7时，整体波动较大，无法确定稳定任务或者稳定路线；高水平：低水平人员比例在 4：6时，顺序 6 的加工任务在 3、4、5 上波动，任务 9 稳定在顺序 1 上加工；高水平：低水平人员比例在 5：5时，整体波动较大，无法确定稳定任务或者稳定路线；高水平：低水平人员比例在 6：4 时，顺序 1 的加工任务在 2、6上波动，顺序 2的加工任务在 1、3、4上波动，顺序 8 的任务在 5、7、8 上波动；高水平：低水平人员比例在 7：3 时，任务 6 的加工顺序稳定在顺序 1 上加工，顺序 8 的加工任务在 5、7 内波动；高水平：低水平人员比例在 8：2 时，任务 6 稳定在顺序 1上加工，任务 10 稳定在顺序 10 上加工；高水平：低水平人员比例在 9：1 时，任务 6 的加工顺序稳定在顺序 1上加工，任务 1主要在顺序 2上加工；高水平：低水平人员比例在 10：0 时，任务 6 的加工顺序稳定在顺序 1上加工，任务 1主要在顺序 2上加工。通过对不同水平下帕累托解集调度路线的分析，我们可以发现在该三目标问题下最有价值的任务和关键顺序，比如任务 6 在不同人员水平下多次稳定在固定顺序加工；顺序 1、2、10的加工任务波动范围相对较小，说明该加工顺序对调度方案的目标具有相对重要的影响。据此可以在人员组合不确定的情况下优先调度关键任务，优先锁定关键顺序；在人员组合确定的情况下，根据已知的调度路线合理安排处理顺序，满足不同目标的需求。五、结论 研究提出了考虑员工负荷均衡率和交货期目标的单工作组多目标任务调度问题，面向该问题构建了考虑团队交互学习效应和人员加工可中断的单工作组多目标调度模型，给出了融合启发式规则和双层关联编码策略的 NSGA-III 模型求解方法，最后通过不同规模的算例仿真验证了所构建模型和算法的有效性。主要贡献如下：第一，分析和表征了考虑员工负荷均衡率和交货期目标的单工作组多目标任务调度问题，考虑实际问题中出现的人员加工可中断现象，实现工作组关键资源的优化匹配。第二，构建了单工作组多目标调度模型和算法，实现单工作组人员分配和任务调度的有机结合，提 高 以 工 作 组 为 加 工 单 元 的 生 产 系 统 加 工效率。第三，利用 python 实现融合启发式规则和双层关联编码策略的 NSGA-III 模型求解方法，并对比不同规模的算例结果验证了模型及算法的有效性。考虑团队交互学习效应的单工作组多目标任务调度问题是区别于其他工作组调度问题的一类新问题，研究对工作组生产系统做了简化，对单工作组的研究可以进一步拓展到多工作组、多工位的分布式工作组调度场景。同时，工作组调度多出现在复杂任务处理过程中，生产环境复杂，考虑因素多，可结合更高维度的目标对该问题进行深入探讨。参考文献:1CAMPBELL G M，DIABY M.Development and evaluation of an assignment heuristic for allocating cross-trained workersJ.European Journal of Operational Research，2002，138（1）：920.2 SUER G A，COSNER J，PATTEN A.Models for cell loading and product sequencing in labor-intensive cellsJ.Computers&Industrial Engineering，2009，56（1）：97105.3SU B，XIE N.Single workgroup scheduling problem with variable processing personnel J.Central European Journal of Operations Research，2020，28（2）：67184.4SU B，XIE N，YANG Y.Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problemJ.Journal of Intelligent Manufacturing，2021，32（4）：957-969.5LING H F，SU Z L，JIANG X L，et al.Multi-objective optimization of integrated civilian-military scheduling of medical supplies for epidemic prevention and controlC/Multidisciplinary Digital Publishing Institute.Healthcare，2021，9（2）：126.6GYRGYI P，KIS T.Minimizing the maximum lateness on a single machine with raw material constraints by branch-and-cut J.Computers&Industrial Engineering，2018，115：220225.7ZAROUK Y，MAHDAVI I，REZAEIAN J，et al.A novel multi-objective green vehicle routing and scheduling model with stochastic demand，supply，and variable travel timesJ.Computers&Operations Research，2022：105698.8MATSUURA H，TSUBONE H，KANEZASHI M.Sequencing，dispatching and switching in dynamic ma