Please wait a minute...
浙江大学学报（理学版）
Journal of Zhejiang University (Science Edition)  2018, Vol. 45 Issue (1): 14-17    DOI: 10.3785/j.issn.1008-9497.2018.01.003
    
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
Download: HTML ( )    PDF(982KB)
Export: BibTeX | EndNote (RIS)      

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.

Key words： single processor scheduling      time restrictions      optimality      heuristic algorithm     
Received: 24 October 2016      Published: 15 December 2017
CLC:  O224  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
WAN Shaochun
ZHANG An
CHEN Yong
CHEN Guangting
Cite this article:

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.

URL:

https://www.zjujournals.com/sci/EN/Y2018/V45/I1/14


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

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

关键词： 单机排序,  时间约束,  最优性,  启发式算法 
[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.
[1] MENG Xudong. Optimality conditions of approximate efficient solutions to set-valued vector equilibrium problems[J]. Journal of Zhejiang University (Science Edition), 2021, 48(4): 440-449.
[2] LIN Geng. A hybrid evolutionary algorithm for solving the obnoxious p-median problem[J]. Journal of Zhejiang University (Science Edition), 2018, 45(1): 29-36,43.