动车组高级检修车间调度问题的优化模型及算法

王忠凯，史天运，林柏梁，张惟皎，李　樊，王　辉

(1.中国铁道科学研究院 电子计算技术研究所，北京　100081；2.北京交通大学 交通运输学院，北京　100044)

随着我国高速铁路的快速发展，2016年计划高级检修动车组数量将超过1 000组。高级检修车间的检修压力日益增大，在既有检修设备资源一定的条件下，如何优化高级检修过程，提高检修车间的检修吞吐量已成为亟待解决的问题。

文献[1—9]研究了不同类型的车间调度问题，建立了数学模型，设计了求解算法；文献[10—13]应用蚁群算法，通过构造析取图，将车间调度问题转换为在析取图上求解调度路径问题。然而动车组的高级检修车间调度问题与以上传统的车间调度问题不同，需要同时考虑检修工艺流程约束和部件装配 (Bill of Material, BOM) 结构约束。随着动车组高级检修工艺的不断细化，工艺数量不断增加(以CRH380CL型动车组为例，其三级修流程包括105项工艺)，加之动车组部件数量多、BOM结构复杂，使得对动车组高级检修车间的调度优化成为复杂的组合优化问题。

目前动车组的检修车间以人工编制高级检修计划的方式为主，效率较低，不利于进一步释放高级检修车间的检修能力。本文围绕高级检修过程的优化问题，开展优化模型和求解算法的研究。

1　问题描述

将X型动车组高级检修时O级修程的调度问题描述为：在给定检修工艺流程中的节点集合和节点之间的先后约束条件以及检修工艺可使用的检修设备集合、给定检修工艺涉及的目标动车组部件集合和部件之间的BOM结构约束条件后，提供最优的动车组高级检修过程调度方案。

1.1　检修工艺流程约束

动车组的高级检修按修程包括三级检修、四级检修和五级检修。尽管不同修程的检修深度和范围有所差异，但是各级修程的检修工艺流程主要包括目标部件分解，检修和装配调试的过程。图1描述了编号为M1-1的动车组转向架(简称转向架M1-1)高级检修基本工艺流程。

图1　动车组转向架M1-1的高级检修工艺流程图

在制定动车组高级检修调度方案的过程中，根据检修部件的类别，可将检修工艺分为3类。①分解类工艺：父级部件经分解类工艺后，产生多个不同类型的子部件。②检修类工艺：针对同一部件进行的技术检测和故障维修，其检修前后的部件类型相同。③组装类工艺：多个子部件经组装类工艺后，产生1个父级部件。

轮对分解为分解类型的工艺。图2描述了经该工艺后，转向架M1-1将产生3个子部件：编号为M1-1的构架(简称构架M1-1)，编号为M1-1的轮对(简称轮对M1-1)和编号为M1-2的轮对(简称轮对M1-2)。

图2　轮对分解工艺图

轮对踏面修型为检修类型的工艺。图3描述了轮对M1-1经该工艺后未产生新的部件。

图3　轮对踏面修型工艺图

图4描述了组装类工艺——“轮对组装”工艺，可见构架M1-1，轮对M1-1和轮对M1-2经该工艺后，将产生上级部件——转向架M1-1。

图4　轮对组装工艺图

转向架M1-1经“空气弹簧分解”工艺后，产生2个空气弹簧和1个转向架M1-1，对2个空气弹簧分别完成“空气弹簧检修”工艺后待最后组装；转向架M1-1经“轮对分解”工艺后产生1个构架和2个轮对；构架M1-1经“轴承分解”、“轴承润滑”、“轴承组装”工艺后待组装；轮对M1-1和轮对M1-2经“轮对踏面修型”、“轮对探伤”工艺后待组装；完成检修的轴承、构架、轮对、空气弹簧按照工艺顺序进行组装，从而完成转向架M1-1的检修。

在以上动车组的高级检修中，需要考虑的工艺流程约束条件有：①需要满足工艺流程约束，按照安装工艺流程的先后次序完成目标部件的检修；②不同的检修工艺有其特定的部件类型约束条件；③任何一个工艺流程节点需要一定的检修耗时，实际调度过程中的检修时间必须大于等于该检修耗时。本文以时间片个数描述检修耗时，并为时间片编号。

1.2　BOM结构约束

动车组BOM结构表明了动车组中主要部件的详细信息及部件之间的层次关系，可以将该结构展开成树形结构。表1为动车组转向架M1-1的BOM结构。

表1　转向架M1-1的BOM结构

由表1可知：转向架M1-1的下级部件为构架、轮对、牵引拉杆和空气弹簧。

在制定动车组高级检修调度方案时，BOM结构会影响分解类和组装类检修工艺所涉及部件的类型和数量。目前动车组高级检修车间多采用2种模式的检修工艺，分别如下。

(1)原位原回模式：在分解、检修、组装过程中，子部件仅能组装成原父级部件。

(2)非原位原回模式：在分解、检修、组装过程中，子部件可以组装成其他父级部件。

上述2种方式对动车组高级检修调度方案的影响如下。

(1)在“原位原回”的装配模式下，只有从原转向架上分解下来的子部件在完成检修工艺后，才可能进行该转向架的装配工艺。对于分解工艺，只有该转向架完成相应子部件的分解工艺后，才可能进行其子部件的检修工艺。

(2)在“非原位原回”的装配模式下，BOM结构只约束分解类工艺流程。

因为“原位原回”的装配模式更具一般化，本文只考虑该模式下的优化问题。

1.3　优化目标

随着动车组高级检修量的日益增加，通过优化调度过程可以有效减少检修过程中的不合理延时和等待现象，从而充分利用既有检修设备，最大化检修能力，提高动车组高级检修车间的检修吞吐量。因此，本文的优化目标为尽量减少动车组目标检修部件的实际检修耗时。

2　优化模型

设C为动车组在高级检修时的全部目标检修部件集合，c和d表示部件，且c,d=0，1，…，NC，其中NC为集合C中的部件数量；I为动车组高级检修的全部工艺集合，i，j表示高级检修的工艺，i，j=0，1，…，NI，其中NI为集合I中检修工艺的数量；Ti为工艺i的最小检修耗时；Ic为部件c需要进行的全部检修工艺集合；Ci为工艺i涉及的目标部件集合；Si为可以完成工艺i的检修设备集合(假设集合Si中的设备只能完成工艺i)，NSi为集合Si的检修设备数量，检修设备用s，w表示，s，w=0，1，…，NS，其中NS为全部检修设备的数量。

在高级检修工艺及其拓扑关系和动车组BOM结构一定的前提下，各个目标部件的检修任务及其拓扑关系是一定的。定义集合Pi为工艺i的直接前驱工艺集合，pi为集合Pi中的某项工艺。定义变量φc d描述目标部件c，d之间的BOM结构关系，如果部件c，d之间为直接父子部件或为同一部件，则φc d=1，否则φc d=0。

建立动车组高级检修过程调度问题的优化模型M1的目标函数Z为

(1)

s.t.

(2)

(3)

tci≥Ti∀c∈C,i∈Ic

(4)

∀i∈I,∀j∈Pi,∀d∈Cpi

(5)

∀i∈I,∀c,d∈C,∀s∈Si

(6)

(7)

ys cd≤xcis∀i∈I,∀c,d∈C,∀s∈Si

(8)

ys cd≤xdis∀i∈I,∀c,d∈C,∀s∈Si

(9)

ys cd,xc is=0,1

(10)

式(1)为全部检修部件的实际检修耗时最小化的优化目标，式(2)表示同一个部件的检修开始与结束的时间之差要大于等于检修耗时；式(3)表示任何部件的第1道检修工艺的开始检修时间需要晚于或等于高级检修开工时间；式(4)表示部件的实际检修耗时需要大于或等于给定的最小检修耗时；式(5)表示检修任务需要同时满足工艺之间的拓扑关系约束和动车组部件BOM结构约束；式(6)表示同一检修设备在同一个时间段内只能进行1个部件的检修工艺，其中L为充分大的因子；式(7)表示有且只有1个检修设备完成部件的检修工艺；式(8)和式(9)描述决策变量之间的约束关系；式(10)说明决策变量的取值范围。

在检修车间的检修能力有限的条件下，如果同时安排的目标检修部件过多，可能完不成全部目标部件的高级检修任务，此时模型M1无可行解。为不失一般性，将模型M1约束条件中的式(7)进行松弛处理，得到模型M2的目标函数B为

(11)

式中：λ为充分大的惩罚因子。

模型M2的约束条件为式(2)—式(6)，式(8)—式(10)。

模型M1具有可行解时，将与模型M2等价；模型M1不具有可行解时，由模型M2可以找到可行解。因此，求解时只求解模型M2即可。

3　求解算法

模型M2的求解过程如下。

(1)输入动车组高级检修工艺过程及其拓扑关系，以及动车组目标检修部件及其BOM结构关系，构造动车组目标检修部件高级检修任务的调度拓扑图。

(2)应用最大最小蚁群系统(MAX-MIN Ant System，MMAS)在任务调度拓扑图上优化调度序列，将最优调度序列描述为δ*={…，ni，…，nj，…}。

(3)采用紧凑调度策略，将最优调度序列δ*变换为动车组高级检修计划方案δPART和δPROCEDURE，其中δPART为部件视图，从部件维度描述高级检修计划；δPROCEDURE为工艺视图，从工艺维度描述高级检修计划。

3.1　调度拓扑图构造算法

在实际的动车组高级检修车间调度优化问题中，涉及的动车组部件和检修工艺数量较大，同时模型M2的约束条件复杂，直接求解较为困难。鉴于在检修工艺及其拓扑关系和动车组BOM结构一定的前提下各个目标部件的检修任务及其拓扑关系是一定的，可以对输入数据进行预处理，根据检修工艺及其拓扑关系和动车组BOM结构构造调度拓扑图，可以预先消解模型M2中的约束条件式(5)，从而有效提高后续优化迭代算法的效率。

调度拓扑图的构造算法流程如图5所示。

图5　调度拓扑图构造算法流程

3.2　最优调度序列优化算法

本文应用最大最小蚁群系统，在调度拓扑图上迭代寻优，找到优化调度序列，该序列说明了调度拓扑图上节点的检修先后次序。按照该次序制定的调度方案，可以在满足模型M2的约束条件式(6)、式(8)—式(10)的基础上，获得动车组高级检修调度问题的最优方案。

具体的求解原理为：单只人工蚂蚁从调度拓扑图的初始节点开始访问，设置当前节点指针，先取当前节点的后续节点集合，按照节点选择规则在后续节点集合中查找下一跳节点，并设置相关节点为已访问状态，直到完成全部节点的访问；多只蚂蚁的访问序列不尽相同，根据模型M2的优化目标对各只蚂蚁的解进行评价，选择较好的蚂蚁访问路径片段刷新拓扑图状态，使得在后续迭代过程中，较好的路径片段会被更多的选中；随着迭代次数的增加，问题依概率收敛。

最优调度序列优化算法流程如图6所示。

3.3　调度方案转换算法

调度方案转换算法按照最优调度序列和每道工艺的最小检修耗时，将各项检修任务的实际检修时间实例化，从而得到具体的检修开工时间和结束时间。

调度方案转换算法流程如图7所示。

4　算　例

以编号为CRH2215C的CRH2C型动车组的三级检修调度方案为算例，验证本文提出的模型和算法。CRH2C型动车组的三级检修主要针对转向架系统[14]，本文限于篇幅，仅选取关键的分解、检修和组装工艺进行说明。简化后的三级检修工艺见表2。

完工部件集合C包括16个转向架，将第1节动车的1位转向架表示为“转向架M1-1”，第2节拖车的2位转向架表示为“转向架T2-2”，部分部件及装配关系见表1。通过算法3.1生成编号为M5-2的转向架检修任务拓扑图如图8所示。

初始化节点的启发信息λi、初始化信息启发因子α、期望启发因子β、信息素强度Q、信息素挥发因子ρ、算法迭代总次数NMAX、蚂蚁总数M。

设置MMAS的参数：α=3.1，ρ=0.5，NMAX=100，M=50。运行平台为Windows7系统，64位环境。进行15次计算，本算例共生成320个节点，算法可以在1 min之内得到优化结果。表3为高级检修部件调度表。结合表2和表3可见：如编号为M3-1的转向架在第0个时间片开始进行“车体与转向架分离”工艺，并在第26个时间片完成“车体与转向架连接”工艺。

图6　最优调度序列优化算法流程

图7　调度方案转换算法流程

检修部件类别工艺　　前置工艺　　最小检修耗时(时间片数目)转向架车体与转向架分离转向架清理转向架分解开始工艺车体与转向架分离转向架清理212构架　构架检修单体制动试验转向架分解构架检修31轮对　空心轴探伤轮对轴箱检修轮对尺寸测量轮对镟修轮辋轮辐探伤转向架分解空心轴探伤轮对轴箱检修轮对尺寸测量轮对镟修21133转向架构架轮对组装轮辋轮辐探伤单体制动试验2转向架尺寸测量构架轮对组装1转向架静载试验转向架尺寸测量1转向架动态测试转向架静载试验2车体与转向架连接转向架动态测试2

图8　编号为M5-2的转向架三级检修任务拓扑图

部件检修开始时间片编号检修结束时间片编号计划完工时间片数/个转向架T2⁃130107130转向架T2⁃228113135转向架T1⁃126116140转向架T1⁃22498145转向架M3⁃102670转向架M3⁃2229275转向架M1⁃1208680转向架M1⁃2188085转向架M2⁃1167490转向架M2⁃2146895转向架M4⁃11262100转向架M4⁃21056105转向架M5⁃1850110转向架M5⁃2644115转向架M6⁃1438120转向架M6⁃2232125

表4为高级检修的工艺调度表。表中：如M3-1(0)表示编号为M3-1的转向架在第0个时间片开始进行“车体与转向架分离”工艺的检修。

表5为某动车组高级检修车间的调度计划分别采用人工方法和本文方法得到的编制结果对比。

表4　工艺调度表

续表4

表5　编制结果对比表

由表5可见：与人工方法相比，采用本文的模型和算法不但能够快速得到调度方案，减轻人工劳动强度，而且有效提高了设备利用率，通过合理组织动车组的高级检修过程，压缩检修耗时。

5　结　语

本文围绕动车组高级检修过程的调度问题，以高级检修工艺流程和部件装配结构为约束条件，以动车组目标检修部件的实际检修耗时最小化为目标，建立优化模型。算例分析结果表明，所提出的模型和算法能够有效地解决动车组的高级检修车间调度问题，最优解呈现出流水调度的特点，将检修任务节点的启发信息设定为与部件的计划检修结束时间呈反比关系，尽量按照部件的装配关系，采用紧凑式调度的方案，有利于缩短检修耗时，提高检修能力。

[1]曾强. 离散制造企业批量生产车间调度智能优化研究 [D]. 重庆：重庆大学，2010.

(ZENG Qiang. Research on Intelligent Optimization of Job Shop Scheduling for Batch Production of Discrete Enterprises [D]. Chongqing: Chongqing University, 2010. in Chinese)

[2]DROTOS M, ERDOS G, KIS T. Computing Lower and Upper Bounds for a Large-Scale Industrial Job Shop Scheduling Problem [J]. European Journal of Operational Research, 2009, 197(1): 296-306.

[3]ARTIBA A, RIANE F. An Application of Planning and Scheduling Multi-Model Approach for Chemical Industry [J]. Computers in Industry, 1998, 36(3): 209-229.

[4]BRUCKER P, SCHLIE R. Job-Shop Scheduling with Multi-Purpose Machines [J]. Computing, 1990, 45(4): 369-375.

[5]WIESEMANN W, KUHN D, RUSTEM B. Multi-Resource Allocation in Stochastic Project Scheduling [J]. Annals of Operations Research, 2012, 193(3): 193-220.

[6]PEZZELLA F, MORGANTI G, CIASCHETTI G. A Genetic Algorithm for the Flexible Job-Shop Scheduling Problem [J]. Computer Operation Research, 2008, 35(5): 3202-3212.

[7]陈婧，张树有. 基于关联调度模型的模糊环境下车间动态调度 [J]. 浙江大学学报：工学版，2011，45(2)：240-246.

(CHEN Jing，ZHANG Shuyou. Dynamic Schedule Optimization Based on Correction Scheduling Model[J]. Journal of Zhejiang University：Engineering Science, 2011, 45(2): 240-246. in Chinese)

[8]陈成，邢立宁. 求解柔性作业车间调度问题的遗传-蚁群算法 [J]. 计算机集成制造系统，2011，17(3)：615-621.

(CHEN Cheng, XING Lining. GA-ACO for Solving Flexible Job Shop Scheduling Problem [J]. Computer Integrated Manufacturing Systems, 2011, 17(3): 615-621. in Chinese)

[9]谢志强，杨静，周勇，等. 基于工序集的动态关键路径多产品制造调度算法 [J]. 计算机学报，2011，34(2)：406-412.

(XIE Zhiqiang, YANG Jing, ZHOU Yong，et al. Dynamic Critical Paths Multi-Product Manufacturing Scheduling Algorithm Based on Operation Set [J]. Chinese Journal of Computer, 2011, 34(2): 406-412. in Chinese)

[10]COLORNI A, DORIGO M, MANIEZZO V, et al. Ant System for Job-Shop Scheduling [J]. Belgian Journal of Operations Research, 1994, 34: 39-53.

[11]李莉，王克奇. 基于改进型蚁群算法的MFJSSP研究 [J]. 计算机应用研究，2011，28(5)：1641-1643.

(LI Li，WANG Keqi. Research on MFJSSP Based on Improved Ant Colony Algorithm [J]. Application Research of Computers, 2011, 28(5): 1641-1643. in Chinese)

[12]李兢尧，孙树栋，黄媛，等. 基于自适应参数混合蚁群算法的双资源约束作业车间调度 [J]. 西北工业大学学报，2011，29(1)：54-61.

(LI Jingyao，SUN Shudong，HUANG Yuan，et al. Solving Dual Resource Constrained Job-Shop Scheduling Problem (DRCJSP) Based on Hybrid Ant Colony Algorithm with Self-Adaptive Parameter [J]. Journal of Northwestern Polytechnical University, 2011, 29(1): 54-61. in Chinese)

[13]刘志刚，李言，李淑娟. 基于蚁群算法的Job-Shop多资源约束车间作业调度 [J]. 系统仿真学报，2007，19(1)：216-220.

(LIU Zhigang，LI Yan，LI Shujuan. Multi-Resource Constrained Job-Shop Optimization Scheduling Based on Ant Colony Algorithm [J]. Journal of System Simulation, 2007, 19(1): 216-220. in Chinese)

[14]中国铁道总公司. 铁总运[2013]158号 铁路动车组运用维修规程[S]. 北京：中国铁路总公司, 2013.