【摘要】研究了机器排序中，带有工件释放时间和交付时间，并且以最小化所有工件的最大延误时间为目标的单机排序问题。该问题是机器排序的经典基础性问题，是NP-hard。从分析该问题的结构特征入手，首先，通过揭示工件单机排序结构（即各工件的排序位置）与工件最大延误时间（相比交付时间）之间的关联规律，从工件加工顺序链的视角考虑，建立了新的基于工件分配位置变量的0-1混合线性规划模型。该模型的结构特征具备更好的优化潜力。其次，结合Dantzig-Wolfe分解等整数优化理论和方法，对模型进行优化处理，进而开发出该单机排序问题的伪多项式时间精确算法。最后，通过仿真模拟测试验证算法的有效性。结果表明：该算法在计算该单机排序问题算例（特别是大型算例）的精确解方面具备显著的效率优势，例如，该算法能够在3000秒内计算出包含1200个工件规模的算例的最优解。