重庆师范大学学报（自然科学版）
重慶師範大學學報（自然科學版）
중경사범대학학보（자연과학판）
JOURNAL OF CHONGQING NORMAL UNIVERSITY（NATURAL SCIENCE EDITION）
2010年
1期
1-6
,共6页
排序%加工时间增加%最大完工时间
排序%加工時間增加%最大完工時間
배서%가공시간증가%최대완공시간
本文讨论工件的加工时间是其开工时间的一类线性增加函数有上界的单机排序问题1∣pj(t)(t0, T1, T2)∣Cmax:设工件集J ={J1, J2,...,Jn}中的每个工件需要在一台机器上得到加工;工件集J被划分成两组J=Ω1+Ω2;机器上第一个被加工的工件在时刻 t0>0开始加工;Ω1中工件的加工时间为pj(t)=ajt1(当t≥T1),Ω2中工件的加工时间为Pj(t)=ajt(当t<T2)或Pj(t)=ajT2(当t≥T2)，其中T2>T1>t0均是给定的常数,t表示对应工件的开工时刻;排序的目的是极小化时间表长(最大完工时间)Cmax.在所得的引理2和引理3的基础上,本文给出一个复杂度为n log n的多项式时间算法,从而也证明了所讨论的问题是多项式时间可解得的.
本文討論工件的加工時間是其開工時間的一類線性增加函數有上界的單機排序問題1∣pj(t)(t0, T1, T2)∣Cmax:設工件集J ={J1, J2,...,Jn}中的每箇工件需要在一檯機器上得到加工;工件集J被劃分成兩組J=Ω1+Ω2;機器上第一箇被加工的工件在時刻 t0>0開始加工;Ω1中工件的加工時間為pj(t)=ajt1(噹t≥T1),Ω2中工件的加工時間為Pj(t)=ajt(噹t<T2)或Pj(t)=ajT2(噹t≥T2)，其中T2>T1>t0均是給定的常數,t錶示對應工件的開工時刻;排序的目的是極小化時間錶長(最大完工時間)Cmax.在所得的引理2和引理3的基礎上,本文給齣一箇複雜度為n log n的多項式時間算法,從而也證明瞭所討論的問題是多項式時間可解得的.
본문토론공건적가공시간시기개공시간적일류선성증가함수유상계적단궤배서문제1∣pj(t)(t0, T1, T2)∣Cmax:설공건집J ={J1, J2,...,Jn}중적매개공건수요재일태궤기상득도가공;공건집J피화분성량조J=Ω1+Ω2;궤기상제일개피가공적공건재시각 t0>0개시가공;Ω1중공건적가공시간위pj(t)=ajt1(당t≥T1),Ω2중공건적가공시간위Pj(t)=ajt(당t<T2)혹Pj(t)=ajT2(당t≥T2)，기중T2>T1>t0균시급정적상수,t표시대응공건적개공시각;배서적목적시겁소화시간표장(최대완공시간)Cmax.재소득적인리2화인리3적기출상,본문급출일개복잡도위n log n적다항식시간산법,종이야증명료소토론적문제시다항식시간가해득적.
