基于改进遗传算法的船舶维修项目调度问题研究.pdf

中 国 修 船2024年4月维修理论基于改进遗传算法的船舶维修项目调度问题研究张博1，陈志敏2，张利平3（1.91776部队，北京100841；2.中国船舶研究设计中心，湖北 武汉430064；3.武汉科技大学 机械自动化学院，湖北 武汉430081）摘要：船舶维修项目调度问题是典型的受优先关系和维修空间限制的资源受限项目调度问题。针对该问题，文章建立了一种船舶维修项目调度数学模型，并提出了改进遗传算法进行求解。基于问题的特征，改进遗传算法主要采用解码与编码策略、选择操作、交叉操作以及变异操作等方法平衡算法的探索和探寻能力。最后，采用工程实例验证了模型的合理性和算法的优越性。关键词：船舶维修；资源受限项目调度；改进遗传算法；数学模型中图分类号：U672文献标志码：Adoi：10.13352/j.issn.1001-8328.2024.02.010Abstract：This paper defined the resources scheduling problem of ship maintenance projects as one of the classical scheduling problems of resource-constrained projects subject to prioritization and maintenance space limitations.In this problem，the paper established a novel mathematical model and proposed an improved genetic algorithm（IGA）to solve the model.Considering the characteristics of this problem，the improved genetic algorithmemployed a coding and encoding strategy，selection operator,crossover operator and mutation operator to balance theexploitation and exploration.Finally，this paper verified the performance of the proposed model and algorithms viacase studies.Key words：ship maintenance；scheduling of resource-constrained project；improved genetic algorithm；mathematical model作者简介：张博（1981-），男，江苏徐州人，副研究员，博士，主要从事装备保障工作。船舶维修项目调度问题涉及一系列具有优先关系和维修空间限制的维修任务和有限的人力资源限制。该问题试图通过合理规划维修任务序列和资源分配实现工期优化。因此，该问题属于典型的具有优先关系和维修空间限制的资源受限项目调度问题。具有优先关系和维修空间限制的资源受限项目调度问题是一类典型的组合优化问题，已经被证实是NP难问题1。由于问题的复杂度，精确算法无法在多项式时间获得算法的可行解，启发式规则尽管能快速获得算法的可行解，但无法获得算法的近优解。元启发式算法以种群迭代优势快速获取大规模问题的最优解，被广泛应用于该问题的求解2。何杰光等3提出变邻域搜索算法优化该问题，并取得较好的效果。王峰等4提出NSGAII算法求解资源受限项目调度问题。部分学者采用布谷鸟搜索算法5、蚁群优化算法6进行求解。当前还有学者研究了不确定条件下的资源受限项目调度7-8。针对船舶维修的维修任务量巨大等特点，本项目提出一种改进遗传算法，可提高算法求解性能，能更好地用于实际维修计划的指导。1问题描述船舶维修项目调度可归为资源受限项目调度问题。该问题具体描述如下：船舶维修项目调度包含J 个维修任务J=1，2，J。任务1和任务中 国 修 船36第37卷第2期维修理论J是虚维修任务，不占用工时和资源，只表达优先关系，是整个维修项目的虚开始和虚结束。维修任务包含 2 类约束：优先关系约束和资源受限约束。优先关系约束是指任意维修任务必须在其所有紧前维修任务完工后才能开始。资源受限约束是指任意时刻所有进行的维修任务均不能超过最大资源供应量。一般而言，资源任意时刻均有上限，且具有可更新性能（例如：设备和人力）。船舶维修项目调度问题的目标就是在满足优先关系约束和资源受限约束的前提下获得最小化的维修工程。为了更好地描述数学模型，首先介绍数学模型中使用的符号。R 为最大资源供应量；j j=1，2，J 为维修任务标号；CTj为维修任务 j 的完工时间；dj为维修任务j的工时；rj为维修任务 j 的资源需求量；Pj为维修任务 j 的紧前维修任务集；xit为 01变量，当维修任务 j被分配在时刻 t时，xit=1，否则xit=0。值得注意的是，T 为一个预设值，一般不能小于维修任务j的完工时间。目标函数：minCTJ。（1）优先关系约束：CTh-dhCTj，h Pj，（2）式中，h为紧前任务集的标号。资源受限约束：j JxjtrjR，t。（3）2船舶维修项目调度的改进遗传算法遗传算法是一种基于自然进化策略的自适应进化算法。在遗传算法进化过程，基因个体通过进化策略不断更新，具有优良基因的个体更倾向于遗传到子代，而较差基因逐渐被抛弃，最终子代获取优良基因，即算法收敛于最优解。分析船舶维修项目调度特征，该问题具有维修任务量巨大、维修流程复杂等特性，本文提出一种改进的遗传算法，该算法主要包括有效的编码和解码策略、选择操作、交叉操作、变异操作。该算法核心思想是通过种群的不断进化，包括选择操作、交叉操作和变异操作，逐步收敛于最优解的过程，改进遗传算法的流程图如图1所示。2.1编码改进遗传算法求解船舶维修项目调度的核心是个体的表达。事实上，如何将问题转化为改进遗传算法的个体，尤其使得该个体能够包含潜在的求解空间是非常重要的。研究发现，船舶维修项目调度的关键决策变量是维修任务序列。若维修任务序列确定，调度方案和资源分配可以依次进行计算。因此，本文设计了一种求解船舶维修项目调度的实数编码，以具有11个维修任务的船舶维修项目调度问题为例，每个个体是整数111的乱序，每个基因表示维修任务的序号。2.2解码解码是把每个个体转化为船舶维修项目的调度方案。该调度方案包括工期、每个维修任务的开始时间和结束时间、任务分配。为了计算方便，虚维修任务1的开始时间设为0。虚维修任务J的结束时间就是整个项目的工期。以个体x1，x2，xj 为例，从左到右，每个维修任务按照优先关系和资源约束依次安排。本文的解码策略如下。1）步骤 1：j=1。2）步骤 2：如果维修任务 xj的紧前维修任务还未完成，交换维修任务xj+1和xj的位置。3）步骤 3：如果维修任务 xj的紧前维修任务全部完成，在满足资源约束的前提下，尽早安排维修任务xj。4）步骤4：如果 j=J，输出调度方案；否则j=j+1，并转至步骤2。2.3适应度函数一般而言，适应度值是引导个体收敛于最优解的重要策略。因为本文的船舶维修项目调度问图1改进遗传算法的流程图开始编码Iter max(Iter)适应度评估初始化选择、交叉、变异评估子代并更新种群NY输出最优解张博，等：基于改进遗传算法的船舶维修项目调度问题研究37中 国 修 船2024年4月维修理论题的目标函数是工期，即虚维修任务 J 的完工时间。因此，本文设计了与虚维修任务J的完工时间相关的适应度函数，适应度函数的计算公式如式（4）所示：F（i）=1CTJ（i），（4）式中，F（i）为个体 i 的适应度值；CTJ（i）为个体i中虚维修任务J的完工时间。2.4进化策略为了更好地探索求解空间，本文设计了选择操作、交叉操作和变异操作改进算法性能。选择操作是通过重组父代不断创造子代种群的过程。本文结合轮盘赌和精英保留策略的优势选择子代种群。精英保留策略是直接选择最优的个体至子代。轮盘赌选择是依据概率选择子代。每个个体的概率计算公式如式（5）所示：P（i）=F（i）i=1NF（i），（5）式中，P（i）为个体 i 的概率；N为种群数量。交叉操作是一种通用的遗传操作，该操作是通过对父代进行基因片段扰动产生子代种群的过程。常见的交叉操作包括单点交叉、两点交叉等。因船舶维修项目调度存在优先关系，三点交叉被用于产生子代并保证子代的可行性。所设计的交叉操作是随机选择3个基因，并交换父代3个基因位的值。以具有11个维修任务的船舶维修项目调度问题为例，随机选择3个基因位 3，7，9，父代1中的3个基因位顺序是3，7，9，则父代2中的基因位顺序9，7，3 取代父代1的3个基因位顺序形成子代 1，交叉操作示意图如图 2所示。同样原理，子代2也如此产生。变异操作是通过扰动产生更大的探索空间，常见的变异操作有单点变异和多点变异。本文采用一种反转变异的方式，即随机选择一段基因片段，反转该基因片段取代原片段。仍以具有11个维修任务的船舶维修项目调度问题为例，位置3到位置7的基因片段3，4，5，6，7被随机选择。该基因片段的反序7，6，5，4，3 取代原基因片段，生成新子代，变异操作示意图如图3所示。3案例分析以某船维修案例的二级网络为例，该案例包括11个维修任务，3类资源限制。3类资源的资源供应量为6，7，6。图4给出了该工程案例的网络关系图。其中维修任务（S）和（T）是虚维修任务。每个维修任务的资源需求量标注于任务上方，每个维修任务的工时标注于任务下方。以维修任务1为例，3，2，1 表示维修任务1需要资源1的数量是3，需要资源2的数量是2，需要资源3的数量是1。d=3表示维修任务1的工时是3天。遗传算法参数对求解性能也有一定的影响，本文通过一系列的试验，使种群大小取100，最大迭代次数是100，交叉概率和变异概率分别为0.8和0.05。通过改进遗传算法求解，该案例的最优个体是1，4，5，6，3，9，10，2，7，8，11，该案例的最短工期是20。表1为每项维修任务的开始时间和完工时间，图5为甘特图。图6为资源负荷图，由图6可知整个工期内的资源负荷情况，其中蓝色、红色、黄色分别对应不图 2交叉操作示意图父代1父代2子代2子代1交叉后交叉前1234567891011987654321101112945678310113876549211011图3变异操作示意图子代父代12345678910111276543891011图 4工程案例的网络关系图872S145391011Td=3d=2d=4d=6d=2d=3d=3d=4d=5d=5d=363，1，12，4，23，2，13，1，13，1，23，2，34，1，0 5，4，22，2，22，0，34，3，11，1，138第37卷第2期维修理论同资源泉（资源 1、资源 2和资源 3）的资源消耗量。由图6可知，每个时间段的资源消耗均小于资源供应量，并且每类资源在整个运行过程波动程度较小，尤其资源2，整个工期内波动最小。4结束语船舶维修资源调度问题具有维修任务多、流程复杂、资源种类多等特点。通过对问题特征的分析，该类问题可归属于一类具有优先关系和维修空间限制的资源受限项目调度问题。为了求解该问题，本文构建了一种新的船舶维修项目调度模型，并提出了一种有效的改进遗传算法。工程案例展示了该模型和算法的优越性。因此，本文所提方法可有效提升船舶维修管理水平，为船舶维修效率提供一种新的途径。参考文献1 王宏.求解资源受限项目调度问题算法的研究D.天津：天津大学，2005.2 Padman R，Dan Z.Knowledge integration using problem spaces:A study in resource-constrained project schedulingJ.Journal of Scheduling，2006，9(2):133-152.3 何杰光，崔得龙.多邻域局部搜索算法求解资源受限项目调度J.广东石油化工学院学报，2018，28(1)：27-32.4 王峰，韩孟臣，赵耀宇，等.基于改进NSGA-II算法求解多目标资源受限项目调度问题J.控制与决策，2021，36(3)：669-676.5 聂慧，刘波，韦向远，等.求解资源受限项目调度问题的改进布谷鸟搜索算法J.桂林理工大学学报，2013(3)：529-536.6 安晓亭，张梓琪.基于改进蚁群优化的多目标资源受限项目调度方法J.系统工程理论与实践，2019(2)：509-519.7 王凌，郑环宇，郑晓龙.不确定资源受限项目调度研究综述J.控制与决策，2014，29(4)：577-584.8 Jingyu Luo，Mario Vanhoucke，Jose Coelho，et al.An efficient genetic programming approach to designpriorityrulesforresource-constrainedproject scheduling problemJ.Expert Systems withApplication，2022，198(6)：1-20.收稿日期：2023-04-11图 5甘特图12108642任务编号18161020工期/天12345678910114681214资源使用量图 6资源负荷图765432120161020工期/天468121418维修任务123456开始时间/天005355结束时间/天3511588维修任务7891011开始时间/天812111517结束时间/天1217151720表1每项维修任务的开始时间和完工时间张博，等：基于改进遗传算法的船舶维修项目调度问题研究2039