Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2016, Vol. 43 Issue (6): 685-688    DOI: 10.3785/j.issn.1008-9497.2016.06.012
数学与计算机科学     
具有服务等级的可拒绝平行机排序问题
荣建华
石家庄铁道大学四方学院 基础部, 河北 石家庄 051132
Parallel machine scheduling with service hierarchy and rejection
RONG Jianhua
Department of Basic, Shijiazhuang Tiedao University Sifang College, Shijiazhuang 051132, China
 全文: PDF(456 KB)  
摘要： 研究了将服务等级与拒绝费用2种模型复合起来的平行机排序问题.设有2台平行机M1，M2，加工速度相同；n个工件J1，J2，…，Jn分别按列表在线到达，每个工件Jj含有3个参数：加工长度tj、拒绝费用pj以及服务等级gj=1，2.当工件到达时，可以接收加工，占用一定的加工时间；亦可拒绝，付出相应的罚值.目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.进一步，当且仅当g（Mi）≤gj时，工件Jj可以分配给机器Mi加工，即机器M1可以加工所有工件，机器M2只能加工等级为gj=2的工件，允许中断加工.设计了在线算法PH，并证明其竞争比为1+(√2)/(2)≈1.707，下界为1.618，上下界差约为0.089.
关键词： 在线排序;  平行机;  拒绝费用;  竞争比;  服务等级    
Abstract: The on-line scheduling problem on two parallel machines with rejection and service hierarchy is investigated. Machines M1, M2 are provided with the same capabilities. Jobs come one by one over the list. Every job Jj is associated with its length tj,penalty pj and service hierarchy gj=1,2. When a job arrives, it can either be assigned to a certain machine or be rejected by paying the penalty.The objective is to minimize the sum of the makespan of all accepted jobs and the total penalty of rejection. A job Jj can be assigned to machine Mi if and only if g(Mi)≤gj, i.e, M1 can process all jobs while M2 can only process the jobs with gj=2. Assuming that preemption is allowed, we propose an on-line approximation algorithm PH with competitive ratio 1+(√2)/(2)≈1.707 while the lower bound is 1.618.
Key words: on-line scheduling    parallel machine    penalty of rejection    competitive ratio    hierarchical
收稿日期: 2015-12-18 出版日期: 2017-03-07
CLC:  O223  
基金资助: 河北省高等教育教学改革研究与实践项目(2015GJJG293)；河北省高等教育科学研究课题(GJXH2015-291).
作者简介: 荣建华(1981-),ORCID:http://orcid.org/0000-0002-7147-4866,女,硕士,讲师,主要从事组合优化、排序理论研究,E-mail:rongjianhua2006@126.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
荣建华

引用本文:

荣建华. 具有服务等级的可拒绝平行机排序问题[J]. 浙江大学学报（理学版）, 2016, 43(6): 685-688.

RONG Jianhua. Parallel machine scheduling with service hierarchy and rejection. Journal of ZheJIang University(Science Edition), 2016, 43(6): 685-688.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2016.06.012    或    https://www.zjujournals.com/sci/CN/Y2016/V43/I6/685

[1] BARTAL Y, LEONARDI S, MARCHETTI-SPACCAMELA A, et al. Multiprocessor scheduling with rejection[J]. SIAM J on Discrete Mathematics,2000,13:64-78.
[2] HE Y,MIN X.On-line uniform machine scheduling with rejection[J]. Operations Research Transactions,2009,13(1):29-36.
[3] DOSA G, HE Y. Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines[J]. Computing,2006,76:149-164.
[4] JIANG Y W, HE Y, TANG C M. Optimal online algorithm for scheduling on identical machines under a grader of service[J]. Journal of Zhejiang University:Science A,2006,7(3):309-314.
[5] PARK J, CHANG S Y, LEE K. Online and semi-online scheduling of two machines under a grader of service provision[J]. Operations Research Letters,2006,34:692-696.
[6] JIANG Y. Online scheduling on parallel machines with two GoS levels[J]. Journal of Combinatorial Optimization,2008,16:28-38.
[7] ZHANG A, JIANG Y, TAN Z. Online parallel machines scheduling with two hierarchies[J]. Theoretical Computer Science,2009,410:3597-3605.
[8] TAN Z, ZHANG A. A note on hierarchical scheduling on two uniform machines[J]. Journal of Combinatorial Optimization, 2010,20:85-95.
[1] 荣建华, 侯丽英. 带有到达时间和拒绝费用工件的同类机排序问题[J]. 浙江大学学报（理学版）, 2016, 43(5): 545-549.