来源：期刊VIP网 时间：
作者：魏汉英;原梦迪;苏志雄;
单位：江西师范大学管理科学与工程研究中心;南昌工程学院工商管理学院;
摘要：本文以最小化所有工件的最大延误时间为目标，研究了带有工件释放时间和交付时间的单机排序问题。该问题是机器排序的经典基础性问题，是NP-hard问题。首先，从该问题的结构特征入手，通过揭示工件单机排序结构（各工件的排序位置）与工件最大延误时间（相比交付时间）之间的关联规律，从工件加工顺序链的视角考虑，建立了新的基于工件分配位置变量的0-1混合线性规划模型。该模型的结构特征具备更好的优化潜力。其次，结合Dantzig-Wolfe分解等整数优化理论和方法，对模型进行优化处理，进而开发出该单机排序问题的伪多项式时间精确算法。最后，通过仿真模拟测试验证算法的有效性。结果表明：该算法在计算该单机排序问题算例（特别是大型算例）的精确解方面具备显著的效率优势，例如，该算法能够在3 000秒内计算出包含1 200个工件规模的算例的最优解。
关键词：单机排序;;最大延误;;混合0-1线性规划;;伪多项式时间精确算法;;Dantzig-Wolfe分解
基金资助：国家自然科学基金资助项目（71961020）;; 江西省教育厅科学技术项目（GJJ201920）;; 江西省研究生创新专项资金资助项目（YC2023-S986）
