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

摘要

This paper studies single processor scheduling with time restrictions of B-constraint,which means that no unit time interval [x,x+1)can be allocated to more than B jobs for any real x≥0.By analyzing the structure and properties of optimal schedules for B =2,a heuristic algorithm with running time O(n log n)is presented.For a small number (≤6)of jobs,it is proved that the algorithm is optimal.%研究单机带时间B-约束的排序问题,即在任意单位时间区间[x,x+1)内至多允许加工B个工件,目标函数是极小化工件的最大完工时间.分析了B=2时最优排序的结构与性质,设计了O(n log n)时间的启发式算法.当工件数较少(≤6)时,证明了该算法的最优性.