单线区间列车最优运行次序的排序模型及解法

摘要

讨论在一个单线区间上以一个车站接续最好为目标的列车最优运行次序问题,首先提出了与该问题相关的一个较特殊的单机反顺序排序问题;应用网络理论,推导出该排序问题的一系列消去准则,并通过对网络适当增弧和加权的方法,给出了当部分工件加工次序已确定的条件下求该排序问题的一个较贴切的上界和下界的方法;利用这些消去准则和上下界估计设计了一个求该问题最优解的分枝定界法算法;最后将所给的分枝定界法推广到更一般的单机反顺序排序模型,并证明求单线区间列车最优运行次序问题是机器可加工时间区间为[t_1,t_2]的单机反顺序排序模型的一种特殊情形。