东南大学学报（自然科学版）
東南大學學報（自然科學版）
동남대학학보（자연과학판）
JOURNAL OF SOUTHEAST UNIVERSITY
2013年
3期
483-488
,共6页
无等待流水作业%总完工时间%邻域结构%启发式算法
無等待流水作業%總完工時間%鄰域結構%啟髮式算法
무등대류수작업%총완공시간%린역결구%계발식산법
为求解NP-难的总完工时间最小化的无等待流水作业调度问题,提出一种有效复合启发式算法.通过分析基本操作的目标增量性质,构造基于插入-分段(I-S)的邻域结构和操作,提出了基于I-S的复合启发式算法(ISCH).ISCH算法与基于比较的启发式算法(BE)、基于置换的复合启发式算法(PHl(p))、Framinan等提出的复合启发式算法(FNM)和基于可变邻域搜索的混合遗传算法(GA-VNS)的比较结果表明,ISCH算法性能最佳,其平均相对偏差的均值较BE算法降低2.04％,平均运行时间为FNM算法的18.43％.当存在时间约束时,ISCH算法的平均相对偏差较GA-VNS算法降低0.99％.该算法中,目标增量方法的选用降低了运行时间,基于I-S邻域结构的方法则提高了算法性能.
為求解NP-難的總完工時間最小化的無等待流水作業調度問題,提齣一種有效複閤啟髮式算法.通過分析基本操作的目標增量性質,構造基于插入-分段(I-S)的鄰域結構和操作,提齣瞭基于I-S的複閤啟髮式算法(ISCH).ISCH算法與基于比較的啟髮式算法(BE)、基于置換的複閤啟髮式算法(PHl(p))、Framinan等提齣的複閤啟髮式算法(FNM)和基于可變鄰域搜索的混閤遺傳算法(GA-VNS)的比較結果錶明,ISCH算法性能最佳,其平均相對偏差的均值較BE算法降低2.04％,平均運行時間為FNM算法的18.43％.噹存在時間約束時,ISCH算法的平均相對偏差較GA-VNS算法降低0.99％.該算法中,目標增量方法的選用降低瞭運行時間,基于I-S鄰域結構的方法則提高瞭算法性能.
위구해NP-난적총완공시간최소화적무등대류수작업조도문제,제출일충유효복합계발식산법.통과분석기본조작적목표증량성질,구조기우삽입-분단(I-S)적린역결구화조작,제출료기우I-S적복합계발식산법(ISCH).ISCH산법여기우비교적계발식산법(BE)、기우치환적복합계발식산법(PHl(p))、Framinan등제출적복합계발식산법(FNM)화기우가변린역수색적혼합유전산법(GA-VNS)적비교결과표명,ISCH산법성능최가,기평균상대편차적균치교BE산법강저2.04％,평균운행시간위FNM산법적18.43％.당존재시간약속시,ISCH산법적평균상대편차교GA-VNS산법강저0.99％.해산법중,목표증량방법적선용강저료운행시간,기우I-S린역결구적방법칙제고료산법성능.
