Zhejiang Daxue xuebao. Lixue ban (Jan 2018)
A note on single processor scheduling with time restrictions(关于带时间约束的单机排序的一个注记)
Abstract
研究单机带时间B-约束的排序问题,即在任意单位时间区间[x,x+1)内至多允许加工B个工件,目标函数是极小化工件的最大完工时间.分析了 B = 2时最优排序的结构与性质,设计了 O(n log n)时间的启发式算法. 当工件数较少(≤6)时,证明了该算法的最优性.
Keywords