沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
JOURNAL OF SHENYANG NORMAL UNIVERSITY(NATURAL SCIENCE)
2012年
1期
12-15
,共4页
排序%禁用区间%时间表长%全多项式近似方案
排序%禁用區間%時間錶長%全多項式近似方案
배서%금용구간%시간표장%전다항식근사방안
近几年来,排序问题由于其深刻的实际背景和广泛的应用前景而受到关注,其自身也在不断的发展变化当中.传统模型通常假设机器是可以连续使用的,但实际上机器在加工期间也需要维护,所以有许多人考虑了机器具有禁用区间的排序模型,并指出了当机器具有多个不可用区间时是强NP-难的问题.对于普通NP-难的问题,他们提出了有效的动态规划算法或多项式时间近似算法.研究工件在两台平行机上加工的排序问题,其中第一台机器上有一段禁用区间,另一台机器是可以连续使用的.在整个加工过程中,工件不允许中断,目标函数是极小化时间表长,该问题是NP-难的.给出这一问题的一个全多项式时间近似方案,算法的时间复杂性是O(n4/ε3),其中n是工件的数量,ε是误差界.
近幾年來,排序問題由于其深刻的實際揹景和廣汎的應用前景而受到關註,其自身也在不斷的髮展變化噹中.傳統模型通常假設機器是可以連續使用的,但實際上機器在加工期間也需要維護,所以有許多人攷慮瞭機器具有禁用區間的排序模型,併指齣瞭噹機器具有多箇不可用區間時是彊NP-難的問題.對于普通NP-難的問題,他們提齣瞭有效的動態規劃算法或多項式時間近似算法.研究工件在兩檯平行機上加工的排序問題,其中第一檯機器上有一段禁用區間,另一檯機器是可以連續使用的.在整箇加工過程中,工件不允許中斷,目標函數是極小化時間錶長,該問題是NP-難的.給齣這一問題的一箇全多項式時間近似方案,算法的時間複雜性是O(n4/ε3),其中n是工件的數量,ε是誤差界.
근궤년래,배서문제유우기심각적실제배경화엄범적응용전경이수도관주,기자신야재불단적발전변화당중.전통모형통상가설궤기시가이련속사용적,단실제상궤기재가공기간야수요유호,소이유허다인고필료궤기구유금용구간적배서모형,병지출료당궤기구유다개불가용구간시시강NP-난적문제.대우보통NP-난적문제,타문제출료유효적동태규화산법혹다항식시간근사산법.연구공건재량태평행궤상가공적배서문제,기중제일태궤기상유일단금용구간,령일태궤기시가이련속사용적.재정개가공과정중,공건불윤허중단,목표함수시겁소화시간표장,해문제시NP-난적.급출저일문제적일개전다항식시간근사방안,산법적시간복잡성시O(n4/ε3),기중n시공건적수량,ε시오차계.
