系统科学与数学
繫統科學與數學
계통과학여수학
JOURNAL OF SYSTEMS SCIENCE AND MATHEMATICAL SCIENCES
2011年
7期
794-803
,共10页
钟雪灵%王国庆%程明宝%李晓春
鐘雪靈%王國慶%程明寶%李曉春
종설령%왕국경%정명보%리효춘
平行机排序%强制工期%空闲时间%提前完工时间和
平行機排序%彊製工期%空閒時間%提前完工時間和
평행궤배서%강제공기%공한시간%제전완공시간화
讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.
討論瞭在m檯同型平行機上,加工帶彊製工期的n箇可中斷工件,在機器可空閒條件下,確定一箇工件排序,使得提前完工時間和最小.先攷慮瞭問題的複雜性,通過3-劃分問題歸約,證明瞭其是彊NP-hard的.而後,討論瞭彊製工期相等的特殊情形,由于工件不允許延遲,問題可能會無可行排序.先討論瞭可行性,接著針對可行問題,提齣一箇算法在多項式時間內穫得最優排序.
토론료재m태동형평행궤상,가공대강제공기적n개가중단공건,재궤기가공한조건하,학정일개공건배서,사득제전완공시간화최소.선고필료문제적복잡성,통과3-화분문제귀약,증명료기시강NP-hard적.이후,토론료강제공기상등적특수정형,유우공건불윤허연지,문제가능회무가행배서.선토론료가행성,접착침대가행문제,제출일개산법재다항식시간내획득최우배서.
