重庆师范大学学报（自然科学版）
重慶師範大學學報（自然科學版）
중경사범대학학보（자연과학판）
JOURNAL OF CHONGQING NORMAL UNIVERSITY（NATURAL SCIENCE EDITION）
2012年
6期
15-19
,共5页
单机排序%维修区间%拒绝工件%NP-难%近似算法
單機排序%維脩區間%拒絕工件%NP-難%近似算法
단궤배서%유수구간%거절공건%NP-난%근사산법
考虑带有拒绝工件和机器维修区间的单机排序问题.目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚(被拒绝加工的工件需要支付拒绝惩罚)的和.这个问题是一般意义下NP-难的,因此需要快速寻找满足指定精确度要求的近似解.为了能在较少的运行时间内得到该问题的较好的近似解,利用削减状态空间方法得到了一个全多项式时间近似方案(FPTAS).该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O( n2/ε2),其中n为输入工件的个数,ε＞0为任意小的实数.
攷慮帶有拒絕工件和機器維脩區間的單機排序問題.目標是最小化被加工工件的總完工時間與被拒絕工件的總懲罰(被拒絕加工的工件需要支付拒絕懲罰)的和.這箇問題是一般意義下NP-難的,因此需要快速尋找滿足指定精確度要求的近似解.為瞭能在較少的運行時間內得到該問題的較好的近似解,利用削減狀態空間方法得到瞭一箇全多項式時間近似方案(FPTAS).該FPTAS是一箇具有彊多項式運行時間的較優近似方案,其時間複雜性為O( n2/ε2),其中n為輸入工件的箇數,ε＞0為任意小的實數.
고필대유거절공건화궤기유수구간적단궤배서문제.목표시최소화피가공공건적총완공시간여피거절공건적총징벌(피거절가공적공건수요지부거절징벌)적화.저개문제시일반의의하NP-난적,인차수요쾌속심조만족지정정학도요구적근사해.위료능재교소적운행시간내득도해문제적교호적근사해,이용삭감상태공간방법득도료일개전다항식시간근사방안(FPTAS).해FPTAS시일개구유강다항식운행시간적교우근사방안,기시간복잡성위O( n2/ε2),기중n위수입공건적개수,ε＞0위임의소적실수.
