沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
JOURNAL OF SHENYANG NORMAL UNIVERSITY(NATURAL SCIENCE)
2013年
1期
28-33
,共6页
排序%异序车间作业%退化工件%最大完工时间
排序%異序車間作業%退化工件%最大完工時間
배서%이서차간작업%퇴화공건%최대완공시간
文章讨论退化工件2台机器异序车间作业排序问题.在异序车间作业环境中,每个工件由一些工序组成,工序的个数未必与机器数相同.此外,每个工件有各自的工序加工顺序.工件可能多次在某些机器上加工,也可能根本不在某些机器上加工.假设工件的实际加工时间是其开始时间的比例函数,目标函数是极小化最大完工时间.首先证明了具有任意工序的问题是强意义下NP-难的；然后对每个工件最多只有2个工序的问题给出了多项式算法；最后证明了只有2个工序具有准备时间或截止工期的问题是普通意义NP-难的.
文章討論退化工件2檯機器異序車間作業排序問題.在異序車間作業環境中,每箇工件由一些工序組成,工序的箇數未必與機器數相同.此外,每箇工件有各自的工序加工順序.工件可能多次在某些機器上加工,也可能根本不在某些機器上加工.假設工件的實際加工時間是其開始時間的比例函數,目標函數是極小化最大完工時間.首先證明瞭具有任意工序的問題是彊意義下NP-難的；然後對每箇工件最多隻有2箇工序的問題給齣瞭多項式算法；最後證明瞭隻有2箇工序具有準備時間或截止工期的問題是普通意義NP-難的.
문장토론퇴화공건2태궤기이서차간작업배서문제.재이서차간작업배경중,매개공건유일사공서조성,공서적개수미필여궤기수상동.차외,매개공건유각자적공서가공순서.공건가능다차재모사궤기상가공,야가능근본불재모사궤기상가공.가설공건적실제가공시간시기개시시간적비례함수,목표함수시겁소화최대완공시간.수선증명료구유임의공서적문제시강의의하NP-난적；연후대매개공건최다지유2개공서적문제급출료다항식산법；최후증명료지유2개공서구유준비시간혹절지공기적문제시보통의의NP-난적.
