沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
JOURNAL OF SHENYANG NORMAL UNIVERSITY(NATURAL SCIENCE)
2013年
2期
186-191
,共6页
排序%串行批处理机%加权误工工件数%到达时间与工期同序%动态规划
排序%串行批處理機%加權誤工工件數%到達時間與工期同序%動態規劃
배서%천행비처리궤%가권오공공건수%도체시간여공기동서%동태규화
笔者考虑的工件带有到达时间,且到达时间与工期同序、目标函数为加权误工工件数的单台串行批处理机排序问题是NP-难的,其中批处理机的容量无限.当同一批中的工件都到达后,此批才可以开始加工.同一批中工件的开始加工时间相同,批的加工时间为此批中所有工件的加工时间之和,且完工时间也相同,为这批中最后一个工件的完工时间；每批开始加工之前都有一个固定的调整时间,而批内工件间无调整时间,在批的调整时间内机器不能加工任何工件.研究工件带有2个不同到达时间,且到达时间与工期同序的情况.对于目标函数为加权误工工件数问题,分析了其最优解的性质,给出了拟多项式动态规划算法及其时间复杂性.
筆者攷慮的工件帶有到達時間,且到達時間與工期同序、目標函數為加權誤工工件數的單檯串行批處理機排序問題是NP-難的,其中批處理機的容量無限.噹同一批中的工件都到達後,此批纔可以開始加工.同一批中工件的開始加工時間相同,批的加工時間為此批中所有工件的加工時間之和,且完工時間也相同,為這批中最後一箇工件的完工時間；每批開始加工之前都有一箇固定的調整時間,而批內工件間無調整時間,在批的調整時間內機器不能加工任何工件.研究工件帶有2箇不同到達時間,且到達時間與工期同序的情況.對于目標函數為加權誤工工件數問題,分析瞭其最優解的性質,給齣瞭擬多項式動態規劃算法及其時間複雜性.
필자고필적공건대유도체시간,차도체시간여공기동서、목표함수위가권오공공건수적단태천행비처리궤배서문제시NP-난적,기중비처리궤적용량무한.당동일비중적공건도도체후,차비재가이개시가공.동일비중공건적개시가공시간상동,비적가공시간위차비중소유공건적가공시간지화,차완공시간야상동,위저비중최후일개공건적완공시간；매비개시가공지전도유일개고정적조정시간,이비내공건간무조정시간,재비적조정시간내궤기불능가공임하공건.연구공건대유2개불동도체시간,차도체시간여공기동서적정황.대우목표함수위가권오공공건수문제,분석료기최우해적성질,급출료의다항식동태규화산법급기시간복잡성.
