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

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

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

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

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

1　问题描述

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