沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
JOURNAL OF SHENYANG NORMAL UNIVERSITY(NATURAL SCIENCE)
2013年
3期
353-355
,共3页
到达时间%拒绝工件%不可用区间%时间表长
到達時間%拒絕工件%不可用區間%時間錶長
도체시간%거절공건%불가용구간%시간표장
release dates%rejection%unavailable interval%makespan
考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题.一个工件或者被拒绝加工,或者被接受.若工件被拒绝加工,厂家必须支付一定的拒绝惩罚；若工件被接受,则把工件放在机器上进行加工.在张丽琦工作的基础上增加了一个不可用区间,机器在此区间内不能加工工件,并且在同一时刻至多加工一个工件.目标函数是最小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和.首先给出一个动态规划算法,然后通过构造输入,将拒绝惩罚进行取整运算,再通过动态规划算法,得到拒绝惩罚取整后的一个最优排序,按照这个工件排序得到原问题的一个可行排序,最后借助一个3-因子算法得到一个全多项式时间近似方案.
攷慮的是帶有到達時間、拒絕工件、不可用區間的單機排序問題.一箇工件或者被拒絕加工,或者被接受.若工件被拒絕加工,廠傢必鬚支付一定的拒絕懲罰；若工件被接受,則把工件放在機器上進行加工.在張麗琦工作的基礎上增加瞭一箇不可用區間,機器在此區間內不能加工工件,併且在同一時刻至多加工一箇工件.目標函數是最小化所有接受工件的時間錶長與所有拒絕工件的拒絕懲罰之和.首先給齣一箇動態規劃算法,然後通過構造輸入,將拒絕懲罰進行取整運算,再通過動態規劃算法,得到拒絕懲罰取整後的一箇最優排序,按照這箇工件排序得到原問題的一箇可行排序,最後藉助一箇3-因子算法得到一箇全多項式時間近似方案.
고필적시대유도체시간、거절공건、불가용구간적단궤배서문제.일개공건혹자피거절가공,혹자피접수.약공건피거절가공,엄가필수지부일정적거절징벌；약공건피접수,칙파공건방재궤기상진행가공.재장려기공작적기출상증가료일개불가용구간,궤기재차구간내불능가공공건,병차재동일시각지다가공일개공건.목표함수시최소화소유접수공건적시간표장여소유거절공건적거절징벌지화.수선급출일개동태규화산법,연후통과구조수입,장거절징벌진행취정운산,재통과동태규화산법,득도거절징벌취정후적일개최우배서,안조저개공건배서득도원문제적일개가행배서,최후차조일개3-인자산법득도일개전다항식시간근사방안.
