沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
JOURNAL OF SHENYANG NORMAL UNIVERSITY(NATURAL SCIENCE)
2014年
4期
466-470
,共5页
平行机排序%不可用区间%中断可恢复%NP-难%全多项式近似方案
平行機排序%不可用區間%中斷可恢複%NP-難%全多項式近似方案
평행궤배서%불가용구간%중단가회복%NP-난%전다항식근사방안
parallel machine scheduling%non-availability interval%resume%NP-hard%FPTAS
讨论带有不可用区间且工件中断可恢复的两台平行机排序问题.其中一台机器带有不可用区间,在不可用区间内不能加工工件.工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工.目标是最小化加权总完工时间.这个问题是一般定义下NP-难的,因此需要寻找满足指定精确度的近似解.首先给出全多项式近似方案的定义,其次提出了一个动态规划的算法,最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS),该近似方案的时间复杂性为O(n5 L5/ε4),其中:n为输入工件的个数;L为输入规模;ε＞0为误差精度.
討論帶有不可用區間且工件中斷可恢複的兩檯平行機排序問題.其中一檯機器帶有不可用區間,在不可用區間內不能加工工件.工件在加工時被不可用區間中斷後,可以在不可用區間之後繼續加工.目標是最小化加權總完工時間.這箇問題是一般定義下NP-難的,因此需要尋找滿足指定精確度的近似解.首先給齣全多項式近似方案的定義,其次提齣瞭一箇動態規劃的算法,最後利用劃分程序的方法得到瞭一箇全多項式近似方案(FPTAS),該近似方案的時間複雜性為O(n5 L5/ε4),其中:n為輸入工件的箇數;L為輸入規模;ε＞0為誤差精度.
토론대유불가용구간차공건중단가회복적량태평행궤배서문제.기중일태궤기대유불가용구간,재불가용구간내불능가공공건.공건재가공시피불가용구간중단후,가이재불가용구간지후계속가공.목표시최소화가권총완공시간.저개문제시일반정의하NP-난적,인차수요심조만족지정정학도적근사해.수선급출전다항식근사방안적정의,기차제출료일개동태규화적산법,최후이용화분정서적방법득도료일개전다항식근사방안(FPTAS),해근사방안적시간복잡성위O(n5 L5/ε4),기중:n위수입공건적개수;L위수입규모;ε＞0위오차정도.
