Zhejiang Daxue xuebao. Lixue ban (Jan 2018)

A note on single processor scheduling with time restrictions(关于带时间约束的单机排序的一个注记)

  • WANShaochun(万绍春),
  • ZHANGAn(张安),
  • CHENYong(陈永),
  • CHENGuangting(陈光亭)

DOI
https://doi.org/10.3785/j.issn.1008-9497.2018.01.003
Journal volume & issue
Vol. 45, no. 1
pp. 14 – 17

Abstract

Read online

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

Keywords