Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2014, Vol. 41 Issue (4): 399-405    DOI: 10.3785/j.issn.1008-9497.2014.04.007
数学与计算机科学     
拒绝可缓冲的2台同类机半在线排序问题的近似算法
Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer
 全文: PDF(547 KB)   HTML ( ) 
摘要： 研究了2个拒绝可缓冲的同类机半在线排序问题. 设有2台同类机M1,M2，速度分别为1和s∈［1,+∞)，加工不允许中断，工件Jj按照列表在线到达,每个工件带有2个参数：加工长度tj、拒绝罚值pj（模型1中）或拒绝获益pj（模型2中），当工件到达时,可以被接受并分给某台机器加工，也可以被拒绝，需付出一定的罚值（模型1）或取得一定的收益（模型2），目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和；第2个模型中要求极大化机器最小负荷和总收益之和. 此外，在接受或拒绝的决策环节上提供一个缓冲区B，其容量为k≥1，任一时刻至多可以存放k个工件，当工件到达时，若缓冲区未饱和，则可暂时存入B；若已饱和，则必须在新工件和缓冲区内工件中选择一个进行接受或拒绝的决策. 本模型所研究的是经典可拒绝模型中的一个松弛问题，属半在线可拒绝模型.最后针对以上2个模型，分别给出了s在区间［1,+∞)上的近似算法，并证明了各自关于s的参数竞争比.
收稿日期: 2013-05-13 出版日期: 2014-04-01
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
闵 啸
刘 静
朱俊蕾
姜 明

引用本文:

闵 啸，刘 静，朱俊蕾，姜 明. 拒绝可缓冲的2台同类机半在线排序问题的近似算法[J]. 浙江大学学报（理学版）, 2014, 41(4): 399-405.

MIN Xiao，LIU Jing， ZHU Junlei， JIANG Ming. Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer. Journal of ZheJIang University(Science Edition), 2014, 41(4): 399-405.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2014.04.007    或    https://www.zjujournals.com/sci/CN/Y2014/V41/I4/399

No related articles found!