Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2016, Vol. 43 Issue (5): 545-549    DOI: 10.3785/j.issn.1008-9497.2016.05.009
数学与计算机科学     
带有到达时间和拒绝费用工件的同类机排序问题
荣建华1, 侯丽英2
1. 石家庄铁道大学四方学院 基础部, 河北 石家庄 050000;
2. 南京农业大学 理学院, 江苏 南京 210095
Uniform machine scheduling with arrival time and rejection
RONG Jianhua1, HOU Liying2
1. Department of Basic, Shijiazhuang Tiedao University Sifang College, Shijiazhuang 050000, China;
2. College of Sciences, Nanjing Agricultural University, Nanjing 210095, China
 全文: PDF(561 KB)  
摘要： 研究了工件带有拒绝费用的m台同类机在线排序问题，m台机器的速度分别为s1=s2=…=sm-1=1，sm=s，当工件到达时，可以接收加工，占用一定的加工时间，也可以拒绝，付出相应的罚值. 目标是被接收工件的最长完工时间（makespan）与被拒绝工件的总罚值之和最小. 对工件2次到达时间问题（零时刻和r时刻各到达一批工件）设计了在线算法H，并证明该算法的竞争比为4-（2s）/（s+m-1）.
关键词： 在线排序;  同类机;  拒绝费用;  竞争比    
Abstract: An on-line scheduling problem on m uniform machines with arrival time and rejection is investigated. The speeds of the machines are respectively s1=s2=…=sm-1=1, sm=s. When a job arrives, it can either be assigned to a certain machine or be rejected by paying penalty. The objective is to minimize the sum of the makespan of all accepted jobs and the total penalty of the rejection. In addition, for jobs that arrive at two different times, namely zero and r, we propose an on-line approximation algorithm H with competitive ratio is 4-(2s)/(s+m-1).
Key words: on-line scheduling    uniform machine    rejection    competitive ratio
收稿日期: 2015-10-29 出版日期: 2016-05-01
CLC:  O223  
基金资助: 南京农业大学青年科技创新基金项目（0506J0116）；河北省高等教育教学改革研究与实践项目（2015GJJG293）；河北省高等教育科学研究课题（GJXH2015-291）.
作者简介: 荣建华(1981-),ORCID:http//orcid.org/0000-0002-7147-4866,女,硕士,讲师,主要从事排序论、近似算法的研究,E-mail:rongjianhua2006@126.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
荣建华
侯丽英

引用本文:

荣建华, 侯丽英. 带有到达时间和拒绝费用工件的同类机排序问题[J]. 浙江大学学报（理学版）, 2016, 43(5): 545-549.

RONG Jianhua, HOU Liying. Uniform machine scheduling with arrival time and rejection. Journal of ZheJIang University(Science Edition), 2016, 43(5): 545-549.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2016.05.009    或    https://www.zjujournals.com/sci/CN/Y2016/V43/I5/545

[1] BARTAL Y, LEONARDI S ,MARCHETTI-SPACCAMELA A,et al. Multiprocessor scheduling with rejection[J]. SIA M J on Discrete Mathematics, 2000,13:64-78.
[2] ZHANG L,LU L,YUAN J.Single machine schedul-ing with release dates and rejection[J]. European Journal of Operational Research,2009,198:975-978.
[3] LU L,NG C T,ZHANG L.Optimal algorithms for single-machine scheduling with rejection to minimize the makespan[J]. International Journal of Production Economics, 2011,130:153-158.
[4] CAO Z, ZHANG Y. Scheduling with rejection and non-identical job arrivals[J]. Journal of Systems Science and Complexity, 2007,20:529-535.
[5] ENGELS D W, KARGER D R, KOLLIOPOULOS S G, et al. Techniques for scheduling with rejection[J]. Journal of Algorithms, 2003,49:175-191.
[6] LU L, ZHANG L, YUAN J.The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan[J]. Theoretical Computer Science, 2008,396:283-289.
[7] LU L,CHENG T C ,YUAN J,et al.Bounded single -machine parallel-batch scheduling with release dates and rejection[J]. Computers & Operations Research, 2009,36:2748-2751.
[8] GAO Q,LU X. Scheduling on single-machine and identical machines with rejection[J]. Operations Research Transactions,2014,18:1-10.
[9] 闵啸,何勇.两台可拒绝同类机在线排序问题近似算法的参数性能比[J].高校应用数学学报:A辑,2000,15(3):326-332. MIN Xiao, HE Yong. Heuristic of scheduling with rejection on two uniform machines[J]. Applied Math-ematics A Journal of Chinese Universities,2000,15(3):326-332.
[10] MIN X,LIU J,WANG Y. Optimal semi-online algorithm for scheduling with rejection on two uniform machines[J]. Journal of Combinatorial Optimization,2011,22:674-683.
[11] 闵啸,刘静.拒绝可缓冲的2台同类机半在线排序问题的近似算法[J].浙江大学学报:理学版,2014,41(4):399-405. MIN Xiao, LIU Jing. Approximate algorithm of semi online scheduling on two uniform machines with a re-jecting buffer[J]. Journal of Zhejiang University:Science Edition,2014,41(4):399-405.
[1] 荣建华. 具有服务等级的可拒绝平行机排序问题[J]. 浙江大学学报（理学版）, 2016, 43(6): 685-688.