Please wait a minute...
浙江大学学报(理学版)  2018, Vol. 45 Issue (1): 14-17    DOI: 10.3785/j.issn.1008-9497.2018.01.003
数学与计算机科学     
关于带时间约束的单机排序的一个注记
万绍春1, 张安1, 陈永1, 陈光亭2
1. 杭州电子科技大学 理学院, 浙江 杭州 310018;
2. 台州学院 数学与信息工程学院, 浙江 台州 317000
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
 全文: PDF(982 KB)   HTML  
摘要: 研究单机带时间B-约束的排序问题,即在任意单位时间区间[x,x+1)内至多允许加工B个工件,目标函数是极小化工件的最大完工时间.分析了B=2时最优排序的结构与性质,设计了O(n log n)时间的启发式算法.当工件数较少(≤ 6)时,证明了该算法的最优性.
关键词: 单机排序时间约束最优性启发式算法    
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
收稿日期: 2016-10-24 出版日期: 2017-12-15
CLC:  O224  
基金资助: 国家自然科学基金资助项目(11771114,11571252,11401149);浙江省自然科学基金资助项目(LY16A010015).
通讯作者: 张安,ORCID:http://orcid.org/0000-0002-2622-5158,E-mail:anzhang@hdu.edu.cn     E-mail: anzhang@hdu.edu.cn
作者简介: 万绍春(1995-),ORCID:http://orcid.org/0000-0002-9337-4460,男,本科,主要从事应用数学研究.
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  
万绍春
张安
陈永
陈光亭

引用本文:

万绍春, 张安, 陈永, 陈光亭. 关于带时间约束的单机排序的一个注记[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.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2018.01.003        https://www.zjujournals.com/sci/CN/Y2018/V45/I1/14

[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] 林耿. 一种求解厌恶型p-中位问题的混合进化算法[J]. 浙江大学学报(理学版), 2018, 45(1): 29-36,43.