关于带时间约束的单机排序的一个注记

摘要 研究单机带时间B-约束的排序问题，即在任意单位时间区间[x，x+1）内至多允许加工B个工件，目标函数是极小化工件的最大完工时间.分析了B=2时最优排序的结构与性质，设计了O（n log n）时间的启发式算法.当工件数较少（≤ 6）时，证明了该算法的最优性