运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2014年
4期
1-10
,共10页
排序%可拒绝%在线算法%竞争比
排序%可拒絕%在線算法%競爭比
배서%가거절%재선산법%경쟁비
scheduling%rejection%on-line algorithm%competitive ratio
研究了带有拒绝的单机和同型机排序问题.对于单机情形,工件的惩罚费用是对应加工时间的α倍.如果工件有到达时间,目标为最小化时间表长与惩罚费用之和,证明了这个问题是可解的.如果所有工件在零时刻到达,目标为最小化总完工时间与惩罚费用之和,也证明了该问题是可解的.对于同型机排序问题,研究了工件分两批在线实时到达的情形,目标为最小化时间表长与惩罚费用之和.针对机器台数2和m,分别给出了竞争比为2和4-2/m的在线算法.
研究瞭帶有拒絕的單機和同型機排序問題.對于單機情形,工件的懲罰費用是對應加工時間的α倍.如果工件有到達時間,目標為最小化時間錶長與懲罰費用之和,證明瞭這箇問題是可解的.如果所有工件在零時刻到達,目標為最小化總完工時間與懲罰費用之和,也證明瞭該問題是可解的.對于同型機排序問題,研究瞭工件分兩批在線實時到達的情形,目標為最小化時間錶長與懲罰費用之和.針對機器檯數2和m,分彆給齣瞭競爭比為2和4-2/m的在線算法.
연구료대유거절적단궤화동형궤배서문제.대우단궤정형,공건적징벌비용시대응가공시간적α배.여과공건유도체시간,목표위최소화시간표장여징벌비용지화,증명료저개문제시가해적.여과소유공건재령시각도체,목표위최소화총완공시간여징벌비용지화,야증명료해문제시가해적.대우동형궤배서문제,연구료공건분량비재선실시도체적정형,목표위최소화시간표장여징벌비용지화.침대궤기태수2화m,분별급출료경쟁비위2화4-2/m적재선산법.
