Parallel machine scheduling with service hierarchy and rejection(具有服务等级的可拒绝平行机排序问题)
研究了将服务等级与拒绝费用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.618,上下界差约为0.089....
Main Author: | RONGJianhua(荣建华) |
---|---|
Format: | Article |
Language: | zho |
Published: |
Zhejiang University Press
2016-11-01
|
Series: | Zhejiang Daxue xuebao. Lixue ban |
Subjects: | |
Online Access: | https://doi.org/10.3785/j.issn.1008-9497.2016.06.012 |
Similar Items
-
Uniform machine scheduling with arrival time and rejection(带有到达时间和拒绝费用工件的同类机排序问题)
by: RONGJianhua(荣建华), et al.
Published: (2016-09-01) -
Semi-online multiprocessor scheduling with the longest given processing time(已知工件最大加工时间的平行机排序问题)
by: WUYong(吴用), et al.
Published: (2008-01-01) -
Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法)
by: MINXiao(闵啸), et al.
Published: (2014-07-01) -
Preemptive semi-on-line scheduling on two identical machines with rejection(一个可中断两台可拒绝同型机半在线排序问题)
by: MINXiao(闵啸), et al.
Published: (2007-09-01) -
Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法)
by: MINXiao(闵啸), et al.
Published: (2010-09-01)