一种基于遗传和禁忌搜索混合算法的维修调度方法
本发明涉及维修调度策略,具体涉及一种基于遗传和禁忌搜索混合算法的维修调度方法。
背景技术:
1、在舰船等大型设备以及复杂工业设施或建筑的维修过程中,需要将有限的高技能人员合理分配到具有严格时序依赖和技能要求的各项维修任务中,当前方法多将维修调度视为单目标优化问题,仅以最短工期为优化目标,忽略了人员负载的均衡性,容易导致高技能人员连续过载、低技能人员闲置浪费,影响维修保障的可持续性,其策略生成过程中,经常采用的纯全局搜索算法(如遗传算法)在强约束下容易陷入局部最优,纯局部搜索算法(如禁忌搜索)则受限于初始解质量,单一算法难以在全局探索与局部精炼之间取得有效平衡。
技术实现思路
1、本发明的目的在于,提供一种能够在多重约束下协同优化工期与人员负载均衡,通过遗传算法与禁忌搜索的递进式融合,实现维修任务的高效、均衡分配的维修调度方法。
2、为实现上述目的,本发明采用如下技术方案。
3、一种基于遗传和禁忌搜索混合算法的维修调度方法,包括以下步骤:
4、步骤1、构建维修调度任务数据集以及双目标优化模型,具体包括:
5、a1、分别建立人员数据集、任务数据集以及调度方案数据集;
6、人员数据集以人员编号为唯一标识存储维修人员的工作效率、技能等级属性;技能等级按维修资质与岗位能力划分为初级、中级、高级、专家级;
7、任务数据集以任务编号为唯一标识,存储任务复杂度、技能要求、前驱任务列表和后继任务列表;任务复杂度衡量完成任务i所需的总工作量;技能要求与技能等级属性匹配,表示完成任务i所需要的最低技能等级,前驱任务列表表示完成任务i所需要的前置任务,后继任务列表数据是指依赖任务i完成后才可执行的任务;
8、调度方案数据集用于存储求解生成的调度结果,包含任务分配方案、任务时间参数、总工期、负载均衡度、专家利用率;
9、a2、数据加载与合法性校验,从人员数据集、任务数据集中加载全部基础数据,执行合法性校验,保障后续调度求解的可行性;
10、a3、以最小化总工期和最小化维修人员负载均衡度为目标,通过权重分配实现目标优先级的量化,建立双目标优化模型,表示为;
11、式中,、分别为最小化项目总工期优化目标和负载均衡优化目标的权重,;表示总工期,为任务i的完成时间;为人员负载均衡度,为全体维修人员的单人最大总工时,为维修人员j的任务总工时;为全体维修人员中,单个人的最小总工时;
12、a4、根据维修任务的相关信息和约束限制,建立建立优化目标模型的约束条件集,约束条件集由括技能匹配约束、任务时序依赖约束、人员单任务独占约束、专家资源独占约束、任务人员数量约束组成;
13、步骤2、基于实数优先级的编码与解码策略
14、b1、种群设置与编码策略
15、定义由独立的调度解个体组成的种群,个体对应一组维修任务调度解,个体的染色体对应维修任务的初始执行优先级序列,染色体的每个基因位对应一项维修任务的初始执行优先级,基因取值为0~1区间内的随机实数,数值大小代表对应任务的初始执行优先级;
16、b2、动态优先级解码,通过动态优先级计算、人员匹配、时间计算逐层完成调度方案生成,具体流程如下:
17、①计算动态优先级,结合任务固有属性修正初始优先级,得到动态优先级;
18、式中,为动态优先级,为随机生成的初始优先级,为复杂度权重系数,为专家级任务优先级补偿值,仅当任务i的技能需求为专家级时生效;
19、②筛选就绪任务:遍历所有未完成任务,筛选出全部前驱任务均已完成的任务,作为当前可调度的就绪任务数据集合;
20、③人员筛选与排序:对当前优先级最高的任务,从全体人员中筛选满足技能匹配约束、符合专家资源独占规则的人员作为候选;候选人员按可用时间升序、工作效率降序排序,优先选用空闲时间早、工作效率高的人员;
21、④人员组队分配:优先选取可用时间最早的人员作为核心执行人员;若其余候选人员的可用时间与团队最早可用时间的差值不超过等待阈值,则同步纳入执行团队;单任务执行团队人数控制在1~3人之间;
22、⑤计算任务时间:任务开始时间取所有前驱任务最大完成时间、团队所有人员最大可用时间两者中的较大值;任务持续时间等于任务复杂度除以团队总工作效率;任务完成时间等于开始时间加持续时间;
23、⑥状态更新:将所有被分配人员的可用时间更新为当前任务的完成时间;标记当前任务为已完成,释放其所有后继任务,若后继任务的全部前驱均已完成,则纳入下一轮就绪任务数据集合;
24、⑦重复上述流程,直至所有任务调度完成,输出完整调度方案;
25、步骤3:遗传-禁忌递进式混合优化求解
26、c1、遗传算法全局种群迭代,以遗传算法为全局搜索主框架,通过迭代进化遍历解空间;
27、c2、精英解筛选与触发机制,设置两层精英保留机制,保障优质解不丢失并触发局部深度优化,具体包括:
28、①代内精英保留:每代种群中适应度最高的前若干个个体直接保留至下一代,不参与交叉与变异操作;
29、②周期性精英筛选:按照迭代次数将进化过程分为三个阶段,在迭代进化前期仅执行全局搜索,积累优质解;在迭代进化中期,每间隔若干代选取当前种群中适应度最高的精英解,触发禁忌搜索进行局部深度精修;若进化前期种群已快速收敛至稳定最优解,可提前触发步骤c3,不做强制迭代间隔限制;
30、c3、禁忌搜索局部精修,获取遗传算法获取的精英解作为初始解,利用移动、交换、增加、移除四类邻域操作以及约束限制校验通过禁忌搜索在邻域内开展局部精细优化;
31、c4、精英解回代与终局优化
32、基于步骤c3的禁忌搜索优化得到优质解,将优化解回代替换遗传算法种群中适应度最低的个体,进行迭代进化操作,若连续若干代未更新全局最优解,则执行一次最终禁忌搜索精修作为兜底优化;
33、c5、输出最优调度方案
34、迭代终止后,输出全局最优调度方案,同步输出对应的总工期、负载均衡度、专家利用率三项核心指标,以及每项任务的人员分配方案、起止时间明细。
35、对前述基于遗传和禁忌搜索混合算法的维修调度方法的进一步改进或者优选实施方式,所述技能等级中,初级承担辅助类维修任务,中级承担常规维修任务,高级承担复杂核心维修任务,专家级承担专属的高难度维修任务;工作效率为影响任务执行速度的量化指标,数值越高则完成同一项任务的耗时越短;
36、任务分配方案记录每个任务被分配的人员编号集合;任务时间包括各任务的开始时间、完成时间和持续时间;
37、专家利用率用于衡量专家级人员的资源利用效率,计算方式为统计所有专家级人员的总工时之和,除以总工期与专家人数的乘积。
38、对前述基于遗传和禁忌搜索混合算法的维修调度方法的进一步改进或者优选实施方式,所述约束条件集中的约束条件具体含义如下:
39、技能匹配约束,是指执行任务的人员j的技能等级必须大于等于任务i的技能要求,表示为,
40、是指决策变量,表示人员是否分配至任务,取值0或1;
41、任务时序依赖约束,是指任意任务的开始时间,必须晚于其所有前驱任务的完成时间,任务i必须在所有前驱任务全部完成后才能启动,表示为;为任务i开始时间,为任务i的前驱任务集合,为前驱任务k的完成时间,若无前驱任务,则最早开始时间为0;
42、人员单任务独占约束,是指同一维修人员在同一时间只能参与一项任务,不可并行执行;
43、专家资源独占约束,是指专家级任务仅可由专家级人员执行,非专家人员不得参与,表示为;
44、任务人员数量约束,是指单任务j分配的执行人员数量最少为1人,最多为3人,表示为
45、;
46、;
47、是指维修人员j的工作效率,是指任务i的持续时间;
48、时间非负性约束要求任务开始时间与完成时间满足非负性和逻辑一致性要求,表示为
49、;
50、。
51、对前述基于遗传和禁忌搜索混合算法的维修调度方法的进一步改进或者优选实施方式,步骤a2中的校验具体包括:
52、人员数据校验:从人员数据集中加载人员编号、工作效率和技能等级数据,统计各技能等级的人员数量,单独识别所有专家级人员;
53、任务数据校验:从任务清单中加载任务编号、复杂度、技能要求及前驱任务列表;校验任务编号的连续性,确保编号从0开始连续无间断;校验所有前驱任务编号的有效性,确保引用的前驱任务均存在于任务清单中;根据任务间的前驱依赖关系构建有向图,进行拓扑排序;若图中存在环路,则报错并终止,确保任务依赖关系为合法的有向无环图;
54、调度可行性校验:对每一项任务,检查是否存在至少一名技能等级不低于任务要求的合格人员;对每一项专家任务,检查是否存在至少一名专家级人员可执行;若任一任务无合格人员,则报错并终止;
55、对前述基于遗传和禁忌搜索混合算法的维修调度方法的进一步改进或者优选实施方式,所述步骤c1、遗传算法全局种群迭代,具体步骤包括:
56、①种群初始化:按设定种群规模随机生成初始染色体种群;
57、②适应度评估:通过解码规则得到每条染色体对应的调度方案,计算总工期与负载均衡度,代入双目标优化模型得到适应度值;适应度值越高则调度方案越优;
58、③执行选择操作:采用锦标赛选择法,每次从种群中随机抽取3个个体,保留适应度最高的个体进入下一代种群,通过多轮选择完成子代种群的初步构建;
59、④执行交叉变异操作逐代迭代,重新计算所有子代个体的适应度,再将子代与父代合并进行精英选择,进入下一代迭代。
60、对前述基于遗传和禁忌搜索混合算法的维修调度方法的进一步改进或者优选实施方式,所述步骤c3、禁忌搜索局部精修具体包括:
61、①单禁忌搜索,获取遗传算法获取的精英解作为初始解,,具体是指:以任务复杂度与贪心系数的加权值作为综合优先级,降序排列后依次为各任务筛选满足技能约束且可用时间最早的人员;
62、②构建移动、交换、增加、移除四类邻域操作,每次操作后首先校验硬约束合法性,将存在技能不匹配、人数超限、专家规则违反的操作判定为非法操作,直接舍弃;仅将约束合法的解纳入候选集合;总工期变长的解属于合法但质量更差的解,不会被判定为非法,仅在择优环节被淘汰;所有操作均以总工期最小化为核心评价准则;
63、其中移动操作是指将一名执行人员从一个任务迁移至另一个任务,仅当目标任务已分配人数小于3人时允许移入,同时需满足技能匹配与专家资源独占约束;
64、交换操作是指交换两个任务中各一名执行人员;交换需同时满足两个任务的技能约束与专家资源独占约束;增加操作是指为一个任务新增一名符合技能要求的执行人员,仅当任务已分配人数小于3人时允许添加,同步校验专家资源独占约束;移除操作是指从一个任务中移除一名执行人员,任务至少保留1名执行人员,专家任务至少保留1名专家级人员。
65、对前述基于遗传和禁忌搜索混合算法的维修调度方法的进一步改进或者优选实施方式,所述步骤三还包括c6、基于总工期、人员负载均衡度及专家资源利用率建立方案评价指标集;其中,专家资源利用率;为的专家级人员的总工时。
66、对前述基于遗传和禁忌搜索混合算法的维修调度方法的进一步改进或者优选实施方式,交叉操作采用单点交叉算子,交叉概率设置为0.85;变异操作采用高斯变异算子,变异概率设置为0.25;变异后对超出0到1区间的基因值进行截断修正,保证所有基因取值合法。
67、对前述基于遗传和禁忌搜索混合算法的维修调度方法的进一步改进或者优选实施方式,遗传算法种群规模200,最大进化代数300,第1-39代仅执行遗传算法全局搜索,积累优质解;第40代后每间隔20代触发一次局部精修;进化至179代后,连续30代无改进则执行最终精修;若连续25代全局最优解相对改进量小于1%,则判定算法已收敛,提前终止迭代;禁忌算法最大迭代65次、禁忌表长度12、邻域规模45、连续无改进阈值18,混合算法精英筛选比例为15%。
68、本发明相比现有方法具有以下优点:
69、第一,实现了工期与负载均衡度的协同优化,在不牺牲工期甚至略微改善工期的前提下,有效改善了人员负载的均衡性。
70、第二,通过结合遗传算法的全局探索与禁忌搜索的局部精炼通过递进式触发和回写机制形成闭环协同,显著提升了求解质量和运行稳定性,提升了算法性能和效率。
71、第三,基于多重约束的前置嵌入使生成的调度方案自动满足所有工程硬性约束,无需人工修正,可直接用于现场作业,有效降低了产业应用的难度,提升了应用前景。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com