沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
JOURNAL OF SHENYANG NORMAL UNIVERSITY(NATURAL SCIENCE)
2013年
3期
348-352
,共5页
拒绝工件%退化%全多项式近似方案%维修区间%排序
拒絕工件%退化%全多項式近似方案%維脩區間%排序
거절공건%퇴화%전다항식근사방안%유수구간%배서
rejection job%deteriorating%fully polynomial time approximation scheme%non-availability interval%scheduling
考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题.所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数.该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚；如果被加工,那么工件被排在机器上(机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件)进行加工.目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小.对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP-难的.
攷慮的是機器需要維護,且需要對若榦箇退化工件進行加工的單機排序問題.所謂退化情況是指每箇工件的加工時間是關于它本身的開始時間的一箇線性單增函數.該問題中工件允許被拒絕,如果工件被拒絕,那麽需要支付拒絕懲罰；如果被加工,那麽工件被排在機器上(機器需要在某一箇固定的時間段內進行維脩以提高其加工速度,且在這段時間內機器不能加工任何工件)進行加工.目標是尋找一箇最優排序使得被加工工件的總完工時間與被拒絕工件的總懲罰之和最小.對于單機情形,利用劃分程序的方法給齣瞭一箇全多項式近似方案,併得齣該近似方案的時間複雜性,說明該問題是一般意義下NP-難的.
고필적시궤기수요유호,차수요대약간개퇴화공건진행가공적단궤배서문제.소위퇴화정황시지매개공건적가공시간시관우타본신적개시시간적일개선성단증함수.해문제중공건윤허피거절,여과공건피거절,나요수요지부거절징벌；여과피가공,나요공건피배재궤기상(궤기수요재모일개고정적시간단내진행유수이제고기가공속도,차재저단시간내궤기불능가공임하공건)진행가공.목표시심조일개최우배서사득피가공공건적총완공시간여피거절공건적총징벌지화최소.대우단궤정형,이용화분정서적방법급출료일개전다항식근사방안,병득출해근사방안적시간복잡성,설명해문제시일반의의하NP-난적.
