论文部分内容阅读
[摘 要]随着我国高速铁路的快速发展，动车组得到广泛应用，动车组的检修也备受重视。由于动车组运行的高速性、使用的频繁性，动车组检修区别于一般铁路机车车辆。动车组检修要求效率高、时间短，且检修质量也要得到充分保证。因此需要编制合理的检修计划，根据动车组检修作业内容合理安排作业人员。有效合理的检修作业工单分配是提高检修工作效率的关键。本文就对动车组检修作业工单调度优化模型和算法相关方面进行分析和探讨。
[关键词]动车组检修作业工单；调度优化模型；算法
中图分类号：U269.2 文献标识码：A 文章编号：1009-914X（2018）03-0098-01
1 动车组检修作业工单调度优化模型
1.1 检修约束条件
检修计划必须满足硬性检修（检修时间不可更改）、检修时间调整、检修开始时间、持续检修、顺序检修、互斥检修、同时检修、检修资源和节假日等约束条件，它们对应的表达式依次为：
其中，i、j为检修设备的标示号；xi、xj分别为设备i、j的检修开始时间；x0i为设备i的申请检修开始时间；Ai为设备i不可更改的检修开始时间；Bi为设备i的检修调整时间限值；Di为设备i的检修持续天数；Xi为设备i允许开始检修时间集合；Tim为设备i允许最晚开始检修时间；uit为第t天设备i的运行开关函数，设备正常运行取0，设备停运检修取1；t为检修日期标示号；T为检修月总天数；N为检修设备的数目；σi为设备i检修资源占用量；M为检修资源总量；Ω为法定节假日集合。
1.2 目标函数
本文以检修最小为目标优化月检修计划，目标函数为：
其中，f（x）为检修造成的损失费用；pit为检修时无法转移负荷的设备i在第t天检修所损失费用；ρi为检修设备i费用。
在优化过程中，检修约束的处理方法为：将属于同时检修和顺序检修的设备编为一组，选取同一组中检修持续时间较长的设备检修开始时间作为一个变量；硬性检修设备以及与硬性检修设备存在同时检修或顺序检修约束的设备不参与优化计算；其他约束采用在目标函数中增加惩罚函数项的方法进行处理，即将目标函数式（10）扩展为：
minF（x）=min[f（x）+αfα（x）+βfβ（x）+γfγ（x）+θfθ（x）]（11）
其中，fα（x）、fβ（x）、fγ（x）和fθ（x）分别为违反检修时间调整约束、违反互斥检修约束、违反检修资源约束和违反节假日约束的惩罚函数，违反时取1，否则取0；α、β、γ和θ为相应的惩罚系数。
2 基于病毒遗传算法的作业工单调度
根据病毒进化理论，病毒是一种特有生物，具有一种特有的感染功能，能获得一个个体的染色体基因，并感染另一个个体，使该个体的部分染色体基因发生相应变化，从而改变该个体的遗传信息，这种遗传信息又通过遗传传递给下一代，大大加速生物的进化。
2.1 编码
2.1.1 主个体编码方案
对于n个项目k道工序的问题，染色体包含n×k个基因。每个基因代表项目此道工序分配的人数。如某一染色体X=（132211221231121132212），共21位，表示该染色体为一个3项目21道工序的人力资源数目调度安排。带有下划线（即第9位）为1，表示第二项目第二道工序，安排1名员工完成。
2.1.2 病毒个体编码方案
病毒个体产生于主个体，是主个体的子串。采用一种位长和主个体相等、在主个体编码方案基础上加入通配符“*”的病毒个体编码方案。就解决本文检修流程而言，病毒染色体为（**11**2**11**2**11**2），“*”可以为1—3中任意一位。这个病毒染色体反映了2条有利于提高适应度函数值、取得较优工程解的规则：
（1）最后一道工序派2名员工，以便着重检查该项目所有内容，保证该项目完成质量；（2）非关键路径上的工序只安排一名员工。
2.2 适应度函数设计
任务调度的最终目标是找到一种合理的调度安排工程解，使得完成任务的天数小于或等于项目规定的完成时间，且完成任务的质量较高（即分派给该任务的员工所具备相应的能力系数较高）。为保证任务较高质量完成，人员调配时应保证将处于空闲状态且拥有当前调配任务所需能力值最高的员工分配给当前任务。采用随机方法产生初始種群所有染色体，再用病毒染色体感染所有染色体，从而生成初始种群。
2.3 遗传操作
遗传操作包含以下3个步骤：（1）选择：采用最常用的轮盘赌选择方式，根据每个染色体适应值的比例确定该个体的选择概率或生存概率。（2）交叉：在父体中选择2个染色体，用单点交叉的方式按交叉概率进行交叉，得到2个子染色体，进入下一代集合。（3）变异：对于交叉后得到的群体的每个个体基因，根据预先设定的变异概率Pm（通常取值0.001～0.01）决定是否变异。对于每一个指定的变异点，有2种方式产生变异：一是对基因值做取反操作；二是用其他等位基因值代替。最后使用病毒染色体对子代集合中所有染色体进行感染。
2.4 病毒个体的进化操作
病毒感染（virusinfection）：利用病毒染色体基因替换主染色体中相应的模式基因，从而产生新的主个体。每个病毒个体以概率Pinfect感染每个主个体，如果某个主体感染后的适应度减小，则用感染后的主个体替换感染前的主个体。复制（copy）：随机选择一个主个体，主个体每个模式基因以概率Pcopy代换病毒染色体中相应基因，从而产生新的病毒个体。初始病毒个体也是通过复制产生，即通过一个主染色体以概率Pcopy复制到一个“无感染能力（infectless）”的病毒个体。复制操作的作用是增加其进化计算能力，或产生一个新的部分活动的资源模式。
2.5 算法步骤
根据上述编码方法和主群体遗传操作，基于病毒遗传机制的检修作业工单调度算法步骤如下：（1）初始化所有参数，生成主群体和病毒群体；（2）进行主群体的遗传操作；（3）进行病毒群体的感染操作；（4）评价主群体，将较优的个体保留下来；（5）如果满足中止条件，算法结束，否则转到步骤（2）。
3 结语
总之，采用病毒感染遗传算法，以调配的人力资源数作为编码形式。引入病毒群体感染主群体，将主群体全局进化和病毒群体局部进化动态结合，克服传统遗传算法早熟和收敛慢的缺点。结果证明，算法在求解并行多项目候选人资源调配问题时，能较快得到一个较优的工程解，很好地满足提高任务质量和缩短任务工期的要求。
参考文献
[1] 李慧.基于无线技术的动车组检修作业调度系统的研究[D].大连交通大学，2015.
[2] 陈煜.基于EAM的高速铁路动车段检修作业工单优化模型与方法的研究[D].北京交通大学，2008.
[关键词]动车组检修作业工单；调度优化模型；算法
中图分类号：U269.2 文献标识码：A 文章编号：1009-914X（2018）03-0098-01
1 动车组检修作业工单调度优化模型
1.1 检修约束条件
检修计划必须满足硬性检修（检修时间不可更改）、检修时间调整、检修开始时间、持续检修、顺序检修、互斥检修、同时检修、检修资源和节假日等约束条件，它们对应的表达式依次为：
其中，i、j为检修设备的标示号；xi、xj分别为设备i、j的检修开始时间；x0i为设备i的申请检修开始时间；Ai为设备i不可更改的检修开始时间；Bi为设备i的检修调整时间限值；Di为设备i的检修持续天数；Xi为设备i允许开始检修时间集合；Tim为设备i允许最晚开始检修时间；uit为第t天设备i的运行开关函数，设备正常运行取0，设备停运检修取1；t为检修日期标示号；T为检修月总天数；N为检修设备的数目；σi为设备i检修资源占用量；M为检修资源总量；Ω为法定节假日集合。
1.2 目标函数
本文以检修最小为目标优化月检修计划，目标函数为：
其中，f（x）为检修造成的损失费用；pit为检修时无法转移负荷的设备i在第t天检修所损失费用；ρi为检修设备i费用。
在优化过程中，检修约束的处理方法为：将属于同时检修和顺序检修的设备编为一组，选取同一组中检修持续时间较长的设备检修开始时间作为一个变量；硬性检修设备以及与硬性检修设备存在同时检修或顺序检修约束的设备不参与优化计算；其他约束采用在目标函数中增加惩罚函数项的方法进行处理，即将目标函数式（10）扩展为：
minF（x）=min[f（x）+αfα（x）+βfβ（x）+γfγ（x）+θfθ（x）]（11）
其中，fα（x）、fβ（x）、fγ（x）和fθ（x）分别为违反检修时间调整约束、违反互斥检修约束、违反检修资源约束和违反节假日约束的惩罚函数，违反时取1，否则取0；α、β、γ和θ为相应的惩罚系数。
2 基于病毒遗传算法的作业工单调度
根据病毒进化理论，病毒是一种特有生物，具有一种特有的感染功能，能获得一个个体的染色体基因，并感染另一个个体，使该个体的部分染色体基因发生相应变化，从而改变该个体的遗传信息，这种遗传信息又通过遗传传递给下一代，大大加速生物的进化。
2.1 编码
2.1.1 主个体编码方案
对于n个项目k道工序的问题，染色体包含n×k个基因。每个基因代表项目此道工序分配的人数。如某一染色体X=（132211221231121132212），共21位，表示该染色体为一个3项目21道工序的人力资源数目调度安排。带有下划线（即第9位）为1，表示第二项目第二道工序，安排1名员工完成。
2.1.2 病毒个体编码方案
病毒个体产生于主个体，是主个体的子串。采用一种位长和主个体相等、在主个体编码方案基础上加入通配符“*”的病毒个体编码方案。就解决本文检修流程而言，病毒染色体为（**11**2**11**2**11**2），“*”可以为1—3中任意一位。这个病毒染色体反映了2条有利于提高适应度函数值、取得较优工程解的规则：
（1）最后一道工序派2名员工，以便着重检查该项目所有内容，保证该项目完成质量；（2）非关键路径上的工序只安排一名员工。
2.2 适应度函数设计
任务调度的最终目标是找到一种合理的调度安排工程解，使得完成任务的天数小于或等于项目规定的完成时间，且完成任务的质量较高（即分派给该任务的员工所具备相应的能力系数较高）。为保证任务较高质量完成，人员调配时应保证将处于空闲状态且拥有当前调配任务所需能力值最高的员工分配给当前任务。采用随机方法产生初始種群所有染色体，再用病毒染色体感染所有染色体，从而生成初始种群。
2.3 遗传操作
遗传操作包含以下3个步骤：（1）选择：采用最常用的轮盘赌选择方式，根据每个染色体适应值的比例确定该个体的选择概率或生存概率。（2）交叉：在父体中选择2个染色体，用单点交叉的方式按交叉概率进行交叉，得到2个子染色体，进入下一代集合。（3）变异：对于交叉后得到的群体的每个个体基因，根据预先设定的变异概率Pm（通常取值0.001～0.01）决定是否变异。对于每一个指定的变异点，有2种方式产生变异：一是对基因值做取反操作；二是用其他等位基因值代替。最后使用病毒染色体对子代集合中所有染色体进行感染。
2.4 病毒个体的进化操作
病毒感染（virusinfection）：利用病毒染色体基因替换主染色体中相应的模式基因，从而产生新的主个体。每个病毒个体以概率Pinfect感染每个主个体，如果某个主体感染后的适应度减小，则用感染后的主个体替换感染前的主个体。复制（copy）：随机选择一个主个体，主个体每个模式基因以概率Pcopy代换病毒染色体中相应基因，从而产生新的病毒个体。初始病毒个体也是通过复制产生，即通过一个主染色体以概率Pcopy复制到一个“无感染能力（infectless）”的病毒个体。复制操作的作用是增加其进化计算能力，或产生一个新的部分活动的资源模式。
2.5 算法步骤
根据上述编码方法和主群体遗传操作，基于病毒遗传机制的检修作业工单调度算法步骤如下：（1）初始化所有参数，生成主群体和病毒群体；（2）进行主群体的遗传操作；（3）进行病毒群体的感染操作；（4）评价主群体，将较优的个体保留下来；（5）如果满足中止条件，算法结束，否则转到步骤（2）。
3 结语
总之，采用病毒感染遗传算法，以调配的人力资源数作为编码形式。引入病毒群体感染主群体，将主群体全局进化和病毒群体局部进化动态结合，克服传统遗传算法早熟和收敛慢的缺点。结果证明，算法在求解并行多项目候选人资源调配问题时，能较快得到一个较优的工程解，很好地满足提高任务质量和缩短任务工期的要求。
参考文献
[1] 李慧.基于无线技术的动车组检修作业调度系统的研究[D].大连交通大学，2015.
[2] 陈煜.基于EAM的高速铁路动车段检修作业工单优化模型与方法的研究[D].北京交通大学，2008.