重庆师范大学学报（自然科学版）
重慶師範大學學報（自然科學版）
중경사범대학학보（자연과학판）
JOURNAL OF CHONGQING NORMAL UNIVERSITY（NATURAL SCIENCE EDITION）
2013年
1期
17-20
,共4页
到达时间%拒绝工件%不可用区间%时间表长
到達時間%拒絕工件%不可用區間%時間錶長
도체시간%거절공건%불가용구간%시간표장
考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题.若工件被拒绝加工,厂家必须支付一定的拒绝惩罚；若工件被接受,则把工件放在机器上进行加工.机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个工件.本文的目标函数是极小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和.首先给出了一个近似算法,并通过引理1证明出此算法是3-因子算法；其次提出了一个动态规划算法,然后通过修改这个动态规划算法的执行过程来减少运行时间,进而得到了一个全多项式时间近似方案,证明出该方案的时间复杂性为O(n2/ε).
攷慮的是帶有到達時間、拒絕工件、不可用區間的單機排序問題.若工件被拒絕加工,廠傢必鬚支付一定的拒絕懲罰；若工件被接受,則把工件放在機器上進行加工.機器帶有不可用區間,在不可用區間內不能加工工件,併且在同一時刻至多加工一箇工件.本文的目標函數是極小化所有接受工件的時間錶長與所有拒絕工件的拒絕懲罰之和.首先給齣瞭一箇近似算法,併通過引理1證明齣此算法是3-因子算法；其次提齣瞭一箇動態規劃算法,然後通過脩改這箇動態規劃算法的執行過程來減少運行時間,進而得到瞭一箇全多項式時間近似方案,證明齣該方案的時間複雜性為O(n2/ε).
고필적시대유도체시간、거절공건、불가용구간적단궤배서문제.약공건피거절가공,엄가필수지부일정적거절징벌；약공건피접수,칙파공건방재궤기상진행가공.궤기대유불가용구간,재불가용구간내불능가공공건,병차재동일시각지다가공일개공건.본문적목표함수시겁소화소유접수공건적시간표장여소유거절공건적거절징벌지화.수선급출료일개근사산법,병통과인리1증명출차산법시3-인자산법；기차제출료일개동태규화산법,연후통과수개저개동태규화산법적집행과정래감소운행시간,진이득도료일개전다항식시간근사방안,증명출해방안적시간복잡성위O(n2/ε).
