CN114912346A - 基于学习能力的技能规划配置和车间调度集成优化方法 - Google Patents

Abstract

本发明公开了一种基于学习能力的技能规划配置和车间调度集成优化方法，按如下步骤：步骤1，建立考虑学习能力异质的员工技能培训决策和调度集成优化模型；步骤2，采用遗传模拟退火算法对步骤1建立的模型进行求解，得出最终最优解，输出最佳目标值和最佳调度方案。本发明针对存在员工异质性的车间调度问题，引入员工培训决策对员工技能实现提前规划，并考虑生产过程中员工的学习效应，构建考虑员工培训和学习效应的车间调度优化模型，并以完工时间、制造成本和员工负载为优化目标，采用三层编码的遗传模拟退火算法进行求解，通过数值案例进行仿真验证；结果表明员工培训能够扩大员工工作范围，增加员工灵活性，降低完工时间和员工负载，提供更加准确以及优秀的调度方案。

Description

基于学习能力的技能规划配置和车间调度集成优化方法

技术领域

本发明涉及一种基于员工学习能力的技能规划配置和车间调度集成优化方法。

背景技术

在企业的生产调度过程中，不仅设备资源是基本要素，工人资源也是基本要素之一。我国制造业仍较为普遍地采用劳动密集型的生产模式，工人仍是生产中的主力，且行业存在招工难、留工难的问题，面临用工荒的难题^[1]([1]孙宝凤,任欣欣,郑再思,等.考虑工人负荷的多目标流水车间优化调度[J].吉林大学学报(工学版),2021,51(03):900-909.)。对工人资源进行分析，对工人的技能需求问题进行研究仍具有较大的意义^[2]([2]董伟,张美,王世斌,等.智能制造行业技能人才需求与培养匹配分析研究[J].高等工程教育研究,2018(06):131-138.)。员工培训是员工从企业内获得技能的一种方式，在制造企业内部，通过员工培训可获得操作不同设备或者拥有某项技能的能力，增加员工分配方案，能够对工人进行更加灵活的配置，实现更加灵活的调度。

员工培训一直都是企业实际生产中的重点，许多学者对此展开研究，如Davis^[3]认为员工灵活性带来的大部分好处是由员工交叉培训带来的([3]Davis D J,Kher H V,Wagner B J.Influence of workload imbalances on the need for workerflexibility[J].Computers&Industrial Engineering,2009,57(1):319-329.)，并对此展开研究，在高工作量且不平衡的情况下，更广泛的工人交叉培训可以显著提高车间绩效；Slomp^[4]进行研究认为在单元化制造环境中进行员工交叉培训非常有必要([4]Slomp J,Bokhorst J,Molleman E.Cross-training in a cellular manufacturing environment[J].Computers&Industrial Engineering,2005,48(3):609-624.)；Li^[5]将员工满意度这一情感因素融入到培训中([5]Li Q,Tang J.Multi-objective optimal cross-trainingconfiguration models for an assembly cell using non-dominated sorting geneticalgorithm-II[J].International Journal of Computer Integrated Manufacturing,2012,25(11):1-15.)，研究如何确定最适合培训方案；Koltai^[6]研究了装配线平衡问题([6]Koltai T.Formulation of multi-level workforce skill constraints inassembly line balancing models[J].International Federation of AutomaticControl,2013,46(9):772-777.)，并将员工技能分为三种类型，低技能、高技能以及排他性技能。并建立一个员工技能获取的培训模型，展示如何在技能缺失的情况下完成简单的装配线平衡模型；Wang^[7]通过员工培训对工人实行技能丰富([7]Wang Y,Tang J.Optimizedskill configuration for the seru production system under an uncertain demand[J].Annals of Operations Research,2020(1):1-21.)，获得一个能够有效响应随机需求的稳健生产系统。以上研究人员通过研究证明了员工培训给企业生产带来益处，但还未有学者考虑将车间调度与员工培训结合进行研究，通过培训实现员工技能资源的提前规划并获取优质的调度结果。且由于员工在产品的生产过程中受到学习效应的影响，员工能力会发生变化，因此考虑学习效应能够获得更加准确的调度结果。许多学者对学习效应进行研究，并将其运用到车间调度中。如Wright^[8]在对航空制造业生产率影响因素的分析中首次提出了学习效应曲线的概念([8]Wright T P.Factors affecting the cost ofairplanes[J].Journal of Aeronautical Sciences,1936,3(4):122-128)，并构建出相应模型来研究其对生产效率的影响；随后，Biskup^[9]提出了基于位置的学习效应模型([9]Biskup D.A state-of-the-art review on scheduling with learning effects[J].European Journal of Operational Research,2008,188(2):315-329.)，该模型影响了许多的学者，Cheng、Mousavi和Wang^[10-12]提出对数-线性模型、S型模型、高原模型以及Dejong模型^[13]([10]Mousavi S M,Mahdavi I,Rezaeian J,et al.An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling withlearning effect and setup times[J].Operational Research,2018,18(1):123-158.、[11]Wang J.Scheduling jobs with a general learning effect model[J].AppliedMathematical Modelling,2013,37(4):2364-2373.、[12]Cheng T,Wu C,Lee W.Somescheduling problems with sum-of-processing-times-based and job-position-basedlearning effects[J].Information Sciences,2008,178(11):2476-2487.、[13]侯丰龙,叶春明,耿秀丽.基于多目标萤火虫膜算法的学习效应生产调度问题[J].系统管理学报,2018,27(04):704-711.)。在这些学者研究的基础上，国内外的许多学者对其进行不断的补充应用，如Jiang和Kuo^[14,15]将实际的时间依赖和作业依赖学习效应引入到单机调度问题中([14]Jiang Z,Chen F,Kang H.Single-machine scheduling problems with actualtime-dependent and job-dependent learning effect[J].European Journal ofOperational Research,2013,227(1):76-80.、[15]Kuo W.Single-machine schedulingwith an actual time-dependent learning effect by D-L yang and W-H kuo reply[J].Journal of the Operational Society,2009,60(3):435-440.)，提出依赖加工时间的学习效应模型，该模型被大量应用于单机、平行机、流水车间等调度问题；Mosheiov和Sindey^[16]提出基于位置和工人的学习效应([16]

Mosheiov G,Sidney J B.Scheduling with general job-dependent learningcurves[J].European Journal of Operational Research,2003,147(3):665-670.)；肖倩乔等^[17]研究双资源生产过程中的设备资源与工人资源与员工的学习能力在这个长期动态过程中的关系([17]肖倩乔,李益兵,左少雄,等.考虑学习曲线的精益生产制造系统双重资源配置方法[J].计算机集成制造系统,2016,22(12):2800-2808)，并建立一个多目标车间调度优化模型；胡金昌^[18]在单人单工序多机器的调度过程中研究员工学习能力的影响([18]胡金昌,刘紫薇,马文凯,等.考虑学习效应的单人作业车间多目标调度算法[J].计算机集成制造系统,2021,27(05):1361-1370.)；李斌^[19]研究团队成员间的交互学习效应如何影响调度过程([19]李斌,谢乃明.考虑团队交互学习效应的单工作组可中断任务调度模型[J].计算机集成制造系统,2022,28(01):161-174.)；曹磊等^[20]考虑到员工之间存在异质性([20]曹磊,叶春明,黄霞.基于员工学习行为的多目标柔性车间调度[J].计算机集成制造系统,2018,24(08):2023-2034.)，并对其进行细分研究，对Dejong的学习效应模型进行修正。上述研究人员在车间调度领域对学习效应展开研究，但未考虑员工培训对车间调度结果产生的影响。

发明内容

基于上述现状，本发明考虑在车间调度过程中引入员工培训，通过培训实现员工技能的增加，并结合员工的学习效应分析其对车间调度的影响，提出了一种基于学习能力的技能规划配置和车间调度集成优化方法。

本发明采取如下技术方案：

基于学习能力的技能规划配置和车间调度集成优化方法，按如下步骤：

步骤1，建立考虑学习能力异质的员工技能培训决策和调度集成优化模型；

步骤2，采用遗传模拟退火算法对步骤1建立的模型进行求解，得出最终最优解，输出最佳目标值和最佳调度方案。

优选的，步骤1中，考虑学习能力异质的员工技能培训决策和调度集成优化模型描述为：有N种不同批量的工件在M台位于车间不同位置具有不同类型和作业能力的设备上由W名不同熟练度水平的工人进行加工，W≤M；当订单到来时，某调度周期内有N种工件待加工，每种工件的需求量为D_i，且工件有N_i道工序，一共有J种工序，每道工序可以在多台设备上进行加工；

选取产品完工时间、生产成本和员工作业负载均衡作为模型的目标函数；

(1)完工时间最小：将最小化所有产品完工的最大时间作为衡量的目标

f₁＝min(maxT_is) (4)

(2)制造成本最低：分为设备的使用成本、工人工资成本、员工培训成本三大部分

(3)员工工作负载均衡：将员工工作负载均衡系数作为一个衡量目标

模型中产品完工时间、制造成本和负载均衡系数三个目标间量纲不同，因此需要在求解的过程中进行归一化处理消除量纲进行目标函数的比较，如下式：

其中f_max和f_min为目标函数的最大值和最小值；

将以上目标加权结合成为：

f＝α·f₁+β·f₂+γ·f₃ (8)

其中，α、β和γ为完工时间、制造成本和员工负载均衡系数的权重，且α+β+γ＝1；

约束条件如下：

(1)任意批次的工件的工序在条件允许的情况下均在0时刻开工

S_ijskw≥0 (9)

(2)每批工件的工序完工时间由该批次工序的开工时刻和该批次实际加工时间决定

E_ijskw≥S_ijskw+d_ix_ijskwT_ijkw (10)

(3)对于任意一种工件的任一工序的完成时间为考虑学习效应的完工时间

(4)是否培训约束，若将工人分配到设备k上，若拥有操作设备k的能力，不需要培训，若不具有该能力则需要培训

(5)确保每个批次中分配到每台设备的工人w具有操作设备的能力

x_ijskw＝x_ijsk[x_kw+(1-x_kw)y_kw] (13)

(6)对于同一批次的同种工件的不同工序，只有上道工序完工后才能进行下道工序的操作

S_ijskw≥E_i(j-1)slo (14)

(7)对于工件i的工序j只能从能加工该工序的设备集合中选取一台进行加工，操作该设备的工人只能从能选工人集合中选择一人操作设备

(8)每位工人在生产中的总加工时间

(9)设备唯一性约束，一台设备在某一时刻不能够同时加工两道工序

S_ijskwX_ijskw-E_i'j'skoX_i'j'sko≥0 (17)

(10)工人唯一性约束，同一名工人在某一只能操作一台设备，不能同时操作多台设备

S_ijskwX_ijskw-E_i'j'slwX_i'j'slw≥0 (18)

(11)二元变量约束

x_ijsk＝{0,1}，x_ijskw＝{0,1}，y_wk＝{0,1} (19)。

优选的，步骤2中，采用遗传模拟退火算法对模型进行求解，具体步骤如下：

S1：使用遗传算法产生初始化种群；

S2：计算种群个体的适应度值，令迭代次数g＝0；

S3：通过比较个体适应度值，通过选择、交叉和变异遗传操作得到临时种群；

S4：在临时种群中进行模拟退火算法操作，确定模拟退火算法的初始温度，产生初始解S，计算解S对应的目标函数值；

S5：通过扰动策略产生新解S'，计算新解对应的目标函数值，并对其使用Metropolis准则判断是否接受，接受则转S6，不接受则转S4；

S6：检测该温度下是否进行充分搜索，若已充分搜索转S7，若未充分搜索则转S4；

S7：判断是否满足模拟退火终止条件，若是，则在记忆表中记忆当前最优解转S8继续迭代；若否，则进行退火操作转S4；

S8：判断迭代过程是否达到最大迭代次数，若否令迭代次数g＝g+1，转S3进行新一轮的迭代过程；若是则进行S9；

S9：比较记忆表中的所有最优解，得出最终最优解，输出最佳目标值和最佳调度方案。

优选的，步骤S1具体如下：初始化种群规模P，交叉概率P_c，变异概率P_m，退火初始温度T₀，降温速率λ，最大迭代次数G_max，阈值温度T_min，链长L；

在求解需求为D_i的工件的调度时间，通过每个批次的批量确定每种产品的批次数，对分批的产品进行调度；在遗传算法中，计算机不能直接识别模型中的参数，因此需要将其转化为具有多个基因组成的个体，将参数转化为可识别的个体的过程称为编码；染色体分为三部分进行编码：基于批次的工序加工顺序编码、基于设备资源的分配编码、基于工人资源的分配编码；工件工序加工顺序信息、机器设备资源分配信息、工人资源分配信息；染色体长度为

n表示工件数量，N_i表示工件i有N_i道工序，三层编码，每层长度均为

基于批次的加工顺序编码：编码由几组重复数字组成，第一个数字表示工件，第二个数字表示批次，重复数字出现的次数表示每种工件的工序数量，数字出现的顺序表示加工顺序；

基于设备资源的分配编码：按照工件种类和批次进行编码，从工件1到工件n，工件内部的编码为各工件的工序优先顺序和批次顺序；每道工序在多台设备上加工，编码基因数字代表选择的加工设备在可选机器组中的顺序位置；

基于工人资源的分配编码：此层编码与设备资源分配编码相对应，其中数字表示工人，通过对工人的分配使设备资源与工人资源相匹配；本层编码包含两种信息，一是选择操作第二层设备的工人；二是判断该层选择的工人是否需要增添新的技能，若选择的工人拥有操作第二层设备的能力，即x_ijkw＝1且x_kw＝1，该员工不需要培训y_kw＝0，若选择的工人不具有操作第二层设备的能力，即x_ijkw＝1且x_kw＝0，则该员工需要进行培训即y_kw＝1，产生培训成本；

染色体解码过程描述为：从第一层开始逐步确定工序的加工顺序和批次生产顺序、每个批次的工件工序分配的机器设备以及工人。

优选的，步骤S2具体如下：

使用适应度函数来评价技能规划和车间调度优化方案，适应度值越大越有机会被选中作为父代；该模型中使用归一化处理消除各目标函数间量纲的加权目标函数的倒数进行比较，适应度函数如下式

遗传算法通过选择操作选出合适数量的优良个体作为父代繁衍子代，使用轮盘赌方法选出后代，个体的适应度值越高，生存概率越高，被选中作为优良个体繁衍子代的概率越高；选择方式为：假设在种群中存在n个个体，第i个个体的适应度值为F_i，则该个体被选中的概率为：

优选的，步骤S3中的交叉操作具体如下：

采用顺序交叉算子分别对工件工序顺序进行交叉；或者，使用多点交叉算子分别对设备资源分配和工人资源分配进行交叉。

优选的，步骤S3中的变异操作具体如下：

采用逆转变异算子对工件工序顺序进行变异；或者，使用随机单点变异对设备资源分配和工人资源分配进行变异。

本发明针对存在员工异质性的车间调度问题，引入员工培训决策对员工技能实现提前规划，并考虑生产过程中员工的学习效应，构建考虑员工培训和学习效应的车间调度优化模型，并以完工时间、制造成本和员工负载为优化目标，采用三层编码的遗传模拟退火算法进行求解，通过数值案例进行仿真验证；结果表明员工培训能够扩大员工工作范围，增加员工灵活性，降低完工时间和员工负载，提供更加准确及优秀的调度方案。

附图说明

图1是本发明涉及的遗传退火算法流程图。

图2是染色体编码图。

图3是采用顺序交叉算子(POX)分别对工件工序顺序进行交叉图。

图4是使用多点交叉算子分别对设备资源分配和工人资源分配进行交叉图。

图5是采用逆转变异算子对工件工序顺序进行变异图。

图6是使用随机单点变异对设备资源分配和工人资源分配进行变异图。

图7是三种方法下车间调度方案完工时间图。

图8是三种方法下车间调度方案制造成本图。

具体实施方式

下面结合附图对本发明优选实施例做详细说明。

员工的学习过程可分为两个阶段，第一阶段为培训过程中通过学习掌握新技能标准以及操作要点，达到培训结束要求；第二阶段为在岗位上重复进行一种操作，受学习效应的影响，不断学习，积累经验，实现技能熟练度的提升。

其中员工培训是一个企业培养人才的重要途径，是员工从企业内获得技能的一种方式，是从对某一技能不了解到满足该技能的技术规范和技能标准可以独立上岗的过程。员工在该阶段中了解熟练工序操作，实现技能的获取。学习效应则是由于工人不断重复某一操作，经验不断累积，引发后续生产效率不断提高的现象，在生产中普遍存在。

在生产作业过程中，员工学习效应会受到四个因素的影响，分别为：员工初始能力水平、学习能力、任务操作重复次数以及该任务难度。其中员工正式上岗时的初始能力和学习能力受到员工自身制约，且初始能力还受到员工岗前培训的影响，知识底蕴深、接受能力强、动手操作能力高的员工上岗时初始能力越强，反之则弱；工作重复次数由订单需求决定；任务难度则由作业本身决定。1957年Dejong提出了一种学习效应模型，考虑了机器和工人的学习效应，被称为Dejong学习效应模型，较符合当前我国手工作业或者半自动化作业的生产模式，其公式表示如下：

T_ijkw＝A[F+(1-F)X^a] (1)

a＝lg^l/lg² (2)

在公式中，T_ijkw表示工件i的工序j在设备k上由工人w完成X件时的实际时间，A为第一个工件的加工时间，F为不可压缩因子(0≤F≤1)表示生产线的自动化程度对学习效应的影响，该值越大表示自动化程度越高，工人的学习效应影响越低，X表示工序在加工机器上的加工数量，a为工人的学习因子(a≤0)。在该模型中，当F等于1时为员工不存在学习效应时的工序实际时间计算方法，等于0时为传统的学习效应模型。

考虑到员工之间存在初始能力异质性和学习率异质性，因此对此模型进行修正，本实施例采用曹磊^[20]([20]曹磊,叶春明,黄霞.基于员工学习行为的多目标柔性车间调度[J].计算机集成制造系统,2018,24(08):2023-2034.)的模型来分析存在初始能力异质和学习率异质的员工学习效应对工作时间的影响，修正后的模型为：

公式中，

为员工w操作设备k的初始操作能力，l_wk为员工w在不同设备的学习能力。在这个模型中，员工初始能力及学习率方面存在异质性，不同的工人即使在拥有相同的初始能力的情况下，进行同一项工作，由于学习率的不同，完成时间也会存在差异。为了清楚的表达员工之间存在的异质性，使用员工初始能力矩阵

和学习率矩阵L_wk表示，初始能力矩阵为员工经过培训后独立上岗时的设备操作能力，学习率矩阵为不同员工对每台设备的操作学习能力。

因此根据以上描述，本实施例基于学习能力的技能规划配置和车间调度集成优化方法，其按如下步骤：

步骤1，建立考虑学习能力异质的员工技能培训决策和调度集成优化模型；

步骤2，采用遗传模拟退火算法对步骤1建立的模型进行求解，得出最终最优解，输出最佳目标值和最佳调度方案。

步骤1中，考虑学习能力异质的员工技能培训决策和调度集成优化模型可以描述为：有N种不同批量的工件在M台位于车间不同位置具有不同类型和作业能力的设备上由W名不同熟练度水平的工人进行加工(一般W≤M)。企业内部建立有完善的员工培训机制，可对员工进行任何设备操作的培训，员工间存在异质性，因此经过培训后员工正式上岗时存在初始能力的差异，员工学习率存在差异，受到学习能力异质的学习效应影响，不同员工间存在明显的差异。当订单到来时某调度周期内有N种工件待加工，每种工件的需求量为D_i，且工件有N_i道工序，一共有J种工序，每道工序可以在多台设备上进行加工，设备类型和加工能力之间存在不同，员工可以通过技能培训增加新的技能，通过学习效应来不断提高技能熟练度水平，工序的加工时间随设备的选择和工人的不同而不同，调度方案也会随着不同的设备和人员的匹配方案而发生变化，需要对工人资源、设备资源、工序加工顺序以及员工技能培训决策进行规划使完工时间最短、加工成本最少、设备负载均衡。

对模型进行如下假设：

(1)各工序在设备上由标准工人加工的标准时间已知，实际加工时间只与设备和工人有关和批次无关；

(2)所有原材料和生产资源(机器和工人)均可在0时刻使用；

(3)工人拥有不同的初始能力和学习率，且已知；

(4)所有工件的到达时刻相同，不同工件间工序不存在优先关系，同工件工序优先关系已知；

(5)同一时刻，每台设备只能加工一道工序，且每名工人只能操作一台设备；

(6)不考虑机器故障，且工序加工开始后不能中断；

(7)企业内部建立有员工培训体系，但是员工培训需要成本，假设每个技能的培训成本是相同的，即技能1和技能2的培训成本相同，培训一个技能的成本为C，则培训两个技能的成本为2C；

(8)所有员工均可以参加所有技能的培训。员工间存在异质性，因此通过培训后正式独立上岗时不同的员工具有不同的技能初始能力；

(9)订单的需求相对稳定，不考虑临时插单、订单取消和变更。

下面，首先进行模型的构建：

设计的符号及变量定义如下：

i,i'：待加工工件数{i＝1…N}；

k,l：设备数{k＝1…M}；

w,o：工人数量{w＝1...W}；

j,j'：工序{j＝1…J}；

s：批次索引，表示为工件i的第s个子批，s＝{1…l_i}；

C_k：设备k单位时间内的使用成本；

C_w：工人w单位时间内的薪资成本；

D_i：工件i的需求量；

t_ijk：工人使用设备k加工工件i的工序j的标准时间；

e_wk：工人w使用设备k的熟练度水平；

T_is：第s批次的工件i的完工时间；

T_w：表示一个生产周期内工人w的总加工时间；

d_i：每种产品的每个批次的批量；

l_i：第i种工件的批次数，l_i＝[D_i/d_i]，“[]”表示向上取整；

S_ijskw：工人w使用设备k加工工件i的工序j的第s批次的开始时刻；

E_ijskw：工人w使用设备k加工工件i的工序j的第s批次的结束时刻；

T_ijskw：工人w使用设备k加工工件i的工序j的第s批次的实际加工时间；

x_ijskw：取值为1，表示工人w使用设备k加工工件i的工序j的第s批次，否则为0；

x_ijsk：二元变量，为1表示将工件i的工序j的第s批次分配在设备k上进行加工，否则为0；

x_kw：二元变量，为1表示工人w拥有操作设备k的能力，否则为0；

y_wk：二元变量，工人w是否需要接受设备k的使用培训，为1表示需要，为0表示不需要。

建立目标函数：

在实际的生产过程中，企业会根据自身利益出发对不同的目标寄予不同的期望，会设置一些目标，如质量部门会将产品质量作为目标、生产部门会将完工时间以及产量生产率作为目标、成本部门会将生产的成本作为目标、能源消耗部门会将能耗以及会产生的污染作为目标，企业对根据不同的目的选取不同的目标。本实施例则选取产品完工时间、生产成本和员工作业负载均衡作为模型的目标函数。

(1)完工时间最小：将最小化所有产品完工的最大时间作为衡量的目标。

f₁＝min(maxT_is) (4)

(2)制造成本最低：分为设备的使用成本、工人工资成本、员工培训成本三大部分。

(3)员工工作负载均衡：员工工作时间是跟员工直接关系的一个因素，员工间因存在技能数量和技能水平的不同，在车间调度过程会造成工人间忙闲不均，部分员工空闲时间过长，通过对不同员工间负载均衡，使不同员工间工作量偏差减少，空闲时间减少。因此将员工工作负载均衡系数作为一个衡量目标。

该模型存在多个目标函数，多目标问题可以转化为单目标问题进行求解，线性加权法是常用的方法，它根据不同目标的重要程度确定每个目标的权重，然后相加构成一个加权目标函数，此方法包含全部的原始数据，能够直接用于实际问题，因此选用线性加权法求解此多目标问题。结合企业自身的期望以及对不同目标的重要程度，但在该模型中产品完工时间、制造成本和负载均衡系数三个目标间量纲不同，因此需要在求解的过程中进行归一化处理消除量纲进行目标函数的比较，方法如下：

其中f_max和f_min为目标函数的最大值和最小值。

可将以上目标加权结合成为：

f＝α·f₁+β·f₂+γ·f₃ (8)

其中α、β和γ为完工时间、制造成本和员工负载均衡系数的权重，且α+β+γ＝1。

约束条件如下：

(1)任意批次工件的工序在条件允许的情况下均可以在0时刻开工。

S_ijskw≥0 (9)

(2)每批工件的工序完工时间由该批次工序的开工时刻和该批次实际加工时间决定。

E_ijskw≥S_ijskw+d_ix_ijskwT_ijkw (10)

(3)因为工人间存在不同的初始能力以及学习率，因此对于任意一种工件的任一工序的完成时间为考虑学习效应的完工时间。

(4)是否培训约束，若将工人分配到设备k上，若拥有操作设备k的能力，不需要培训，若不具有该能力则需要培训。

(5)确保每个批次中分配到每台设备的工人w具有操作设备的能力。

x_ijskw＝x_ijsk[x_kw+(1-x_kw)y_kw] (13)

(6)优先关系约束。对于同一批次的同种工件的不同工序，只有上道工序完工后才可以进行下道工序的操作。

S_ijskw≥E_i(j-1)slo (14)

(7)对于工件i的工序j只能从可加工该工序的设备集合中选取一台进行加工，操作该设备的工人只能从可选工人集合中选择一人操作设备。

(8)每位工人在生产中的总加工时间。

(9)设备唯一性约束,一台设备在某一时刻不能够同时加工两道工序。

S_ijskwX_ijskw-E_i'j'skoX_i'j'sko≥0 (17)

(10)工人唯一性约束,同一名工人在某一只能操作一台设备，不能同时操作多台设备。

S_ijskwX_ijskw-E_i'j'slwX_i'j'slw≥0 (18)

(11)二元变量约束。

x_ijsk＝{0,1}，x_ijskw＝{0,1}，y_wk＝{0,1} (19)

模型求解具体如下：

遗传算法是一种并行搜索算法，它具有全局搜索能力较强、过程简单、良好的并行处理能力、鲁棒性好、通用灵活性较大和搜索速度快等优点，但它也有局部搜索能力较差，存在“早熟”情况，容易过早收敛陷入局部最优，得不到全局最优解的缺点；模拟退火算法应用广泛，能够有效的求解NP完全难题，它具有较强的局部搜索能力，能够以一定的概率接受劣解，跳出局部最优的陷阱获得全局最优解，但其也存在全局搜索能力较差的缺点。由上所述，可以发现，两种算法可以相互弥补对方的弱项，组成一个在全局搜索和局部搜索均具有优势的算法，两者相互嵌套，互相弥补各自的缺陷能够快速的得到全局最优解。

本实施例采用的算法具体描述如下：

遗传模拟退火算法集合了遗传算法的优势和模拟退火算法的优势，弥补了各自的劣势，能够快速得出全局最优解，因此基于以上的优势，本实施例采用遗传模拟退火算法对模型进行求解，其详细步骤如下：

S1：使用遗传算法产生初始化种群；

S2：计算种群个体的适应度值，令迭代次数g＝0；

S3：通过比较个体适应度值，通过选择、交叉和变异等遗传操作得到临时种群；

S4：在临时种群中进行模拟退火算法操作，确定模拟退火算法的初始温度，产生初始解S，计算解S对应的目标函数值；

S5：通过扰动策略产生新解S'，计算新解对应的目标函数值，并对其使用Metropolis准则判断是否接受，接受转S6，不接受转S4；

S6：检测该温度下是否进行充分搜索，若已充分搜索转S7，若未充分搜索则转S4；

S7：判断是否满足模拟退火终止条件，是则在记忆表中记忆当前最优解转S8继续迭代；若否则进行退火操作转S4；

S8：判断迭代过程是否达到最大迭代次数，若否令迭代次数g＝g+1，转Step3进行新一轮的迭代过程；若是则进行S9；

S9：比较记忆表中的所有最优解，得出最终最优解，输出最佳目标值和最佳调度方案。

遗传模拟退火算法流程图如图1所示。

在上述算法步骤中，种群初始化及初始解生成具体如下：

初始化种群规模P，交叉概率P_c，变异概率P_m，退火初始温度T₀，降温速率λ，最大迭代次数G_max，阈值(退火终止)温度T_min，链长L。

在求解需求为D_i的工件的调度时间，可通过每个批次的批量确定每种产品的批次数，对分批的产品进行调度。在遗传算法中，计算机不能直接识别模型中的参数，因此需要将其转化为具有多个基因组成的个体，将参数转化为可识别的个体的过程称为编码。染色体分为三部分进行编码：基于批次的工序加工顺序编码、基于设备资源的分配编码、基于工人资源的分配编码。工件工序加工顺序信息、机器设备资源分配信息、工人资源分配信息。染色体长度为

(n表示工件数量，N_i表示工件i有N_i道工序)，三层编码如图2所示，每层长度均为

基于批次的加工顺序编码：编码由几组重复数字组成，第一个数字表示工件，第二个数字表示批次，重复数字出现的次数表示每种工件的工序数量，数字自左向右出现的顺序表示加工顺序，如图2所示，数字12表示工件1的第一个批次，数字12第一次出现表示工件1的工序1的第一加工批次，编码的片段[12 31 21 22]的含义为按照产品工序间的优先关系，加工顺序为：工件1工序1的第二批次、工件3工序1第一批次、工件2工序1第一批次、工件2工序2第2批次。

基于设备资源的分配编码：按照工件种类和批次进行编码，从左至右为工件1到工件n，工件内部的编码为各工件的工序优先顺序和批次顺序。每道工序可以在多台设备上加工，编码基因数字代表选择的加工设备在可选机器组中的顺序位置，如图2所示，例如设备编码第一个数字为1表示，在工件1工序1的第一批次可选设备组[M1、M3、M4]中选第1台设备M1进行加工，第二个数字2表示在工件1工序2的第一批次可选设备组[M3、M4]选取第2台设备M4进行加工。

基于工人资源的分配编码：此层编码与设备资源分配编码相对应，其中数字表示工人，通过对工人的分配使设备资源与工人资源相匹配。在本实施例中，员工除自身具有的技能外，可通过培训获取操作设备的能力，扩大自己的技能范围，因此对于工人资源，除去已有的工人资源，还可通过培训增加新的资源，使工人资源范围发生变化。本层编码包含两种信息，一是选择操作第二层设备的工人；二是判断该层选择的工人是否需要增添新的技能，若选择的工人拥有操作第二层设备的能力，即x_ijkw＝1且x_kw＝1，该员工不需要培训y_kw＝0，若选择的工人不具有操作第二层设备的能力，即x_ijkw＝1且x_kw＝0，则该员工需要进行培训即y_kw＝1，产生培训成本。

染色体解码过程可描述为：从第一层开始逐步确定工序的加工顺序和批次生产顺序、每个批次的工件工序分配的机器设备以及工人。

在上述算法步骤中，适应度值计算及选择具体如下：

使用适应度函数来评价技能规划和车间调度优化方案，适应度值越大越有机会被选中作为父代。该模型中使用归一化处理消除各目标函数间量纲的加权目标函数的倒数进行比较，适应度函数如式(20)所示。

遗传算法通过选择操作选出合适数量的优良个体作为父代繁衍子代，轮盘赌法是最简单也是最常用的一种方法，一种通过比例快速选出所需要个体的一种随机选择方法，本实施例使用轮盘赌方法选出后代，个体的适应度值越高，生存概率越高，被选中作为优良个体繁衍子代的概率越高。选择方式为：假设在种群中存在n个个体，第i个个体的适应度值为F_i，则该个体被选中的概率为：

在上述算法步骤中，交叉及变异具体如下：

(1)交叉操作

交叉的作用是将父代的基因片段遗传给子代，同时起到全局搜索的作用。本实施例采用顺序交叉算子(POX)分别对工件工序顺序进行交叉，如图3所示；使用多点交叉算子分别对设备资源分配和工人资源分配进行交叉，如图4所示。

(2)变异操作

与交叉操作类似，采用逆转变异算子对工件工序顺序进行变异如图5所示；使用随机单点变异对设备资源分配和工人资源分配进行变异，如图6所示。

状态函数产生新个体：

(1)生成初始化解S，并计算解S的目标函数值；

(2)使用邻域搜索技术扰动产生新解S'；

(3)使用Metropolis准则判断ΔE＝f(S')-f(S)并执行记忆功能，若ΔE＜0，使用新解S'代替旧解S，若ΔE＞0，随即生成介于[0，1)之间的随机实数rand，计算新解的接受率r＝exp(-ΔE/T),若r＞rand，则可以接受新解S'作为新的当前解。在判断是否接受新解后，设置一个额外的变量用于保存全局最优解，每次迭代对全局最优解保存以避免Metropolis准则判断过程中损失最优解。

退火操作：

遗传算法具有易早熟的问题，易陷入局部最优解中，因此本实施例融入模拟退火操作解决该问题。模拟退火操作为，设置初始温度，判断当前温度是否高于阈值温度T_min，若高于阈值温度T_min，开始降温操作，选用直线降温策略。

达到迭代次数或者得到的最优解保持不变时，迭代终止，输出最优解。

对上述实施例进行仿真及验证：

本发明提出一个考虑员工学习能力异质的技能规划配置和车间调度集成优化问题模型，并提出一种嵌入模拟退火的遗传算法进行求解，下面通过一个算例来验证本实施例提出的优化模型。

案例描述：A公司是一家机械加工企业，现其接到一张订单，分配到其某一车间进行生产，该车间内存在11台设备，8名工人，这11台设备中有5种类型，分为车床、铣床、磨床、镗床、刨床以及可以进行车、铣和钻操作的加工中心，车床2台，铣床2台，磨床1台，镗床1台，刨床2台，加工中心3台。车间内的8名工人，既有工作多年的老员工也有新招进来的临时工或者新员工，每名工人经过培训后拥有不同的初始能力，且由于每名员工间存在学习率异质性，在学习操作设备方面存在差异，不同员工拥有不同的学习效率。

现公司将接到的订单分配到此车间进行生产，该订单中含有7种工件，每种工件均包含车间中的所有操作，现使用车间内的11台设备8名工人对其进行生产，需要进行合理的安排使完工时间最短，制造成本最低以及员工负载最小。订单信息如表2所示、每台设备可加工的操作和每名工人可操作的设备信息如表1所示、员工经过培训后的初始能力和员工的学习效率如表3和表4所示。

表1工件加工信息表

表2员工需求量及生产批量

工件	1	2	3	4	5	6	7
								需求量	80	55	100	200	120	160	50
批量	16	10	20	40	25	30	10

表3员工初始能力

表4员工学习率

表格中加粗字体表示现有员工的初始能力及学习率，未加粗表示经过培训后员工具有的初始能力。

结果分析：

根据以上数据，借助Matlab 2017a软件对本实施例提出的考虑员工学习能力异质的员工技能规划配置和车间调度集成优化模型进行求解，求解算法为遗传模拟退火算法，相关初始化参数设置为：P＝50，G_max＝200，P_c＝0.6，P_m＝0.4，T₀＝100，T_min＝1，L＝100，设备的使用成本为20元/小时，工人薪资为20元/小时，单次培训成本为15元/次，权重α＝0.5，β＝0.3，γ＝0.2。

表5考虑员工学习能力相同调度方案结果

解	总目标值	完工时间(h)	制造成本(元)	负载均衡系数
					1	0.29	137.57	14523.33	2.29
2	0.30	148.44	14363.60	2.51
					3	0.32	152.16	14372.50	2.44
4	0.33	161.93	14239.91	2.52
					5	0.36	137.89	14570.22	2.72
6	0.41	145.32	14542.88	2.86
					7	0.43	151.48	14505.87	2.88
8	0.44	160.52	14435.20	2.74
					9	0.45	164.65	14389.07	2.85
10	0.46	147.81	14628.61	2.82

表6考虑员工学习能力差异的调度方案结果

表7不考虑员工学习效应的调度方案结果

解	总目标值	完工时间(h)	制造成本(元)	负载均衡系数
					1	0.36	159.02	14367.00	2.90
2	0.38	161.68	14375.83	2.89
					3	0.40	163.30	14506.00	2.32
4	0.41	157.68	14476.25	3.00
					5	0.41	155.90	14544.75	2.80
6	0.42	158.95	14573.00	2.48
					7	0.43	171.23	14373.67	2.62
8	0.45	160.46	14547.50	2.80
					9	0.49	161.52	14626.75	2.71
10	0.50	165.69	14556.75	2.81

表5、表6和表7分别为使用遗传模拟退火算法求解得出的结果，表5为考虑员工学习能力相同学习效应的技能培训决策与车间调度集成优化方案，表6为考虑员工学习能力异质学习效应的技能培训决策与车间调度集成优化方案，表7为不考虑员工学习效应的技能培训决策与车间调度集成优化方案。图7和图8比较了三种情况下不同方案的完工时间和制造成本，由图7和图8可知，考虑员工异质性的学习能力对调度结果产生积极影响，调度方案最优，完工时间和制造成本明显优于其余两种方案，不考虑员工学习效应的调度方案最差。

从整体看学习能力对调度结果产生积极影响，能够较明显的减少完工时间和制造成本，且求解结果稳定，由表5、表6、表7和表8以及图7、图8进行三种方案最优结果对比可知，考虑员工异质性学习时的方案最优。

对比三种方案最优结果，考虑员工的学习能力能够有效减少调度方案的完工时间，其中与不考虑学习效应的调度方案相比，考虑员工学习能力相同的技能培训决策与车间调度集成优化方案完工时间减少21.5h约13.4％，考虑员工学习能力异质的调度方案完工时间减少27.7h，约17.4％。此时考虑员工学习能力异质的最优调度方案的设备工人匹配以及员工技能资源规划如表9、表10所示，表9为工序-设备-工人分配方案，表格中第一个数字为选择的设备，第二个数字为与设备匹配的工人；表10为工人技能资源规划后的技能矩阵，1表示需要拥有此技能，0表示不需要，加粗字体表示在技能资源规划前就已用拥有了此技能。

表8三种方法最优调度结果

表9最优调度方案工序-设备-工人分配方案

表10最优调度方案工人技能资源规划

综上所述，本发明构建考虑员工培训和学习效应的车间调度优化模型，设计一种模拟退火算法进行求解。企业通过员工技能培训实现员工技能增加，实现员工的多技能化，增加调度过程中的员工分配方案，提高员工利用率；考虑员工操作过程中的学习效应，能够使计算出的工人操作时间更加贴近实际工作时间，同样有利于工人资源的配置和提升劳动利用率，使获得生产调度方案更加准确和优秀。

以上显示和描述了本发明的基本原理和主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。

Claims (7)

1.基于学习能力的技能规划配置和车间调度集成优化方法，其特征是按如下步骤：

步骤1，建立考虑学习能力异质的员工技能培训决策和调度集成优化模型；

步骤2，采用遗传模拟退火算法对步骤1建立的模型进行求解，得出最终最优解，输出最佳目标值和最佳调度方案。

2.如权利要求1所述基于学习能力的技能规划配置和车间调度集成优化方法，其特征是：

步骤1中，考虑学习能力异质的员工技能培训决策和调度集成优化模型描述为：有N种不同批量的工件在M台位于车间不同位置具有不同类型和作业能力的设备上由W名不同熟练度水平的工人进行加工，W≤M；当订单到来时，某调度周期内有N种工件待加工，每种工件的需求量为D_i，且工件有N_i道工序，一共有J种工序，每道工序可以在多台设备上进行加工；

选取产品完工时间、生产成本和员工作业负载均衡作为模型的目标函数；

(1)完工时间最小：将最小化所有产品完工的最大时间作为衡量的目标

f₁＝min(maxT_is) (4)

(2)制造成本最低：分为设备的使用成本、工人工资成本、员工培训成本三大部分

(3)员工工作负载均衡：将员工工作负载均衡系数作为一个衡量目标

模型中产品完工时间、制造成本和负载均衡系数三个目标间量纲不同，因此需要在求解的过程中进行归一化处理消除量纲进行目标函数的比较，如下式：

其中f_max和f_min为目标函数的最大值和最小值；

将以上目标加权结合成为：

f＝α·f₁+β·f₂+γ·f₃ (8)

其中，α、β和γ为完工时间、制造成本和员工负载均衡系数的权重，且α+β+γ＝1；

约束条件如下：

(1)任意批次的工件的工序在条件允许的情况下均在0时刻开工

S_ijskw≥0 (9)

(2)每批工件的工序完工时间由该批次工序的开工时刻和该批次实际加工时间决定

E_ijskw≥S_ijskw+d_ix_ijskwT_ijkw (10)

(3)对于任意一种工件的任一工序的完成时间为考虑学习效应的完工时间

(4)是否培训约束，若将工人分配到设备k上，若拥有操作设备k的能力，不需要培训，若不具有该能力则需要培训

(5)确保每个批次中分配到每台设备的工人w具有操作设备的能力

x_ijskw＝x_ijsk[x_kw+(1-x_kw)y_kw] (13)

(6)对于同一批次的同种工件的不同工序，只有上道工序完工后才能进行下道工序的操作

S_ijskw≥E_i(j-1)slo (14)

(7)对于工件i的工序j只能从能加工该工序的设备集合中选取一台进行加工，操作该设备的工人只能从能选工人集合中选择一人操作设备

(8)每位工人在生产中的总加工时间

(9)设备唯一性约束，一台设备在某一时刻不能够同时加工两道工序

S_ijskwX_ijskw-E_i'j'skoX_i'j'sko≥0 (17)

(10)工人唯一性约束，同一名工人在某一只能操作一台设备，不能同时操作多台设备

S_ijskwX_ijskw-E_i'j'slwX_i'j'slw≥0 (18)

(11)二元变量约束

x_ijsk＝{0,1}，x_ijskw＝{0,1}，y_wk＝{0,1} (19)。

3.如权利要求2所述基于学习能力的技能规划配置和车间调度集成优化方法，其特征是：

步骤2中，采用遗传模拟退火算法对模型进行求解，具体步骤如下：

S1：使用遗传算法产生初始化种群；

S2：计算种群个体的适应度值，令迭代次数g＝0；

S3：通过比较个体适应度值，通过选择、交叉和变异遗传操作得到临时种群；

S4：在临时种群中进行模拟退火算法操作，确定模拟退火算法的初始温度，产生初始解S，计算解S对应的目标函数值；

S5：通过扰动策略产生新解S'，计算新解对应的目标函数值，并对其使用Metropolis准则判断是否接受，接受则转S6，不接受则转S4；

S6：检测该温度下是否进行充分搜索，若已充分搜索转S7，若未充分搜索则转S4；

S7：判断是否满足模拟退火终止条件，若是，则在记忆表中记忆当前最优解转S8继续迭代；若否，则进行退火操作转S4；

S8：判断迭代过程是否达到最大迭代次数，若否令迭代次数g＝g+1，转S3进行新一轮的迭代过程；若是则进行S9；

S9：比较记忆表中的所有最优解，得出最终最优解，输出最佳目标值和最佳调度方案。

4.如权利要求3所述基于学习能力的技能规划配置和车间调度集成优化方法，其特征是：

步骤S1具体如下：初始化种群规模P，交叉概率P_c，变异概率P_m，退火初始温度T₀，降温速率λ，最大迭代次数G_max，阈值温度T_min，链长L；

在求解需求为D_i的工件的调度时间，通过每个批次的批量确定每种产品的批次数，对分批的产品进行调度；在遗传算法中，计算机不能直接识别模型中的参数，因此需要将其转化为具有多个基因组成的个体，将参数转化为可识别的个体的过程称为编码；染色体分为三部分进行编码：基于批次的工序加工顺序编码、基于设备资源的分配编码、基于工人资源的分配编码；工件工序加工顺序信息、机器设备资源分配信息、工人资源分配信息；染色体长度为

n表示工件数量，N_i表示工件i有N_i道工序，三层编码，每层长度均为

基于批次的加工顺序编码：编码由几组重复数字组成，第一个数字表示工件，第二个数字表示批次，重复数字出现的次数表示每种工件的工序数量，数字出现的顺序表示加工顺序；

基于设备资源的分配编码：按照工件种类和批次进行编码，从工件1到工件n，工件内部的编码为各工件的工序优先顺序和批次顺序；每道工序在多台设备上加工，编码基因数字代表选择的加工设备在可选机器组中的顺序位置；

基于工人资源的分配编码：此层编码与设备资源分配编码相对应，其中数字表示工人，通过对工人的分配使设备资源与工人资源相匹配；本层编码包含两种信息，一是选择操作第二层设备的工人；二是判断该层选择的工人是否需要增添新的技能，若选择的工人拥有操作第二层设备的能力，即x_ijkw＝1且x_kw＝1，该员工不需要培训y_kw＝0，若选择的工人不具有操作第二层设备的能力，即x_ijkw＝1且x_kw＝0，则该员工需要进行培训即y_kw＝1，产生培训成本；

染色体解码过程描述为：从第一层开始逐步确定工序的加工顺序和批次生产顺序、每个批次的工件工序分配的机器设备以及工人。

5.如权利要求3所述基于学习能力的技能规划配置和车间调度集成优化方法，其特征是：步骤S2具体如下：

使用适应度函数来评价技能规划和车间调度优化方案，适应度值越大越有机会被选中作为父代；该模型中使用归一化处理消除各目标函数间量纲的加权目标函数的倒数进行比较，适应度函数如下式

遗传算法通过选择操作选出合适数量的优良个体作为父代繁衍子代，使用轮盘赌方法选出后代，个体的适应度值越高，生存概率越高，被选中作为优良个体繁衍子代的概率越高；选择方式为：假设在种群中存在n个个体，第i个个体的适应度值为F_i，则该个体被选中的概率为：

6.如权利要求3-5任一项所述基于学习能力的技能规划配置和车间调度集成优化方法，其特征是：步骤S3中的交叉操作具体如下：

采用顺序交叉算子分别对工件工序顺序进行交叉；或者，使用多点交叉算子分别对设备资源分配和工人资源分配进行交叉。

7.如权利要求3-5任一项所述基于学习能力的技能规划配置和车间调度集成优化方法，其特征是：步骤S3中的变异操作具体如下：

采用逆转变异算子对工件工序顺序进行变异；或者，使用随机单点变异对设备资源分配和工人资源分配进行变异。

Images