A note on single processor scheduling with time restrictions
WAN Shaochun1, ZHANG An1, CHEN Yong1, CHEN Guangting2
1. School of Sciences, Hangzhou Dianzi University, Hangzhou 310018, China;
2. School of Mathematics & Information Engineering, Taizhou University, Taizhou 317000, Zhejiang Province, China
Abstract：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.
万绍春, 张安, 陈永, 陈光亭. 关于带时间约束的单机排序的一个注记[J]. 浙江大学学报（理学版）, 2018, 45(1): 14-17.
WAN Shaochun, ZHANG An, CHEN Yong, CHEN Guangting. A note on single processor scheduling with time restrictions. Journal of ZheJIang University(Science Edition), 2018, 45(1): 14-17.
[1] BRAUN O, CHUNG F, GRAHAM R. Single-processor scheduling with time restrictions[J].Journal of Scheduling, 2014, 17:399-403.
[2] LEUNG J. Handbook of Scheduling[M]. Boca Raton:Chapman and Hall, 2004.
[3] EDIS P, OGUZ C, OZKARAHAN I. Parallel machine scheduling with additional resources:Notation, classification, models and solution methods[J].European Journal of Operational Research, 2013, 230:449-463.
[4] ZHANG A, YE F, CHEN Y,et al. Better permutations for the single-processor scheduling with time restrictions[J]. Optimization Letters, 2017, 11:715-724.
[5] BRAUN O, CHUNG F, GRAHAM R. Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions[J].OR Spectrum, 2016, 38:531-540.
2018, Vol. 45 
