摘要：讨论工件具有线性加工时间，工件间具有链约束的单机排序问题。目标函数为极小化加权完工时间和。在这类问题中，工件的加工时间是其开工时间的线性函数。对链不允许中断和链允许中断两种情况分别给出了最优算法。

关键词：排序 单机 链约束 线性加工时间 

单位：沈阳师范大学数学与系统科学学院; 沈阳110034