管理工程学报
管理工程學報
관리공정학보
JOURNAL OF INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT
2014年
2期
182-190
,共9页
调度%两阶段流水车间%等待时间受限%启发式
調度%兩階段流水車間%等待時間受限%啟髮式
조도%량계단류수차간%등대시간수한%계발식
scheduling%two-stage flowshop%limited waiting time constraints%heuristic
等待时间受限的两阶段流水车间调度问题具有强NP难的复杂性,有必要探索问题特征来开发近似求解算法.本文分析了此问题与一般两阶段流水车问调度和无等待两阶段流水车间调度的关系,给出了两类特殊问题的多项式求解方法,探讨了最优调度的工件序列特征.在此基础上,设计了基于排列排序的启发式算法,算法应用Gilmore-Gomory启发式生成初始序列,构造调度解的可替换集合实现迭代寻优,并利用工件序列特征调整工件顺序以优化当前调度.通过对算法的求解性能进行理论分析和实验验证,进一步表明了该算法的有效性.
等待時間受限的兩階段流水車間調度問題具有彊NP難的複雜性,有必要探索問題特徵來開髮近似求解算法.本文分析瞭此問題與一般兩階段流水車問調度和無等待兩階段流水車間調度的關繫,給齣瞭兩類特殊問題的多項式求解方法,探討瞭最優調度的工件序列特徵.在此基礎上,設計瞭基于排列排序的啟髮式算法,算法應用Gilmore-Gomory啟髮式生成初始序列,構造調度解的可替換集閤實現迭代尋優,併利用工件序列特徵調整工件順序以優化噹前調度.通過對算法的求解性能進行理論分析和實驗驗證,進一步錶明瞭該算法的有效性.
등대시간수한적량계단류수차간조도문제구유강NP난적복잡성,유필요탐색문제특정래개발근사구해산법.본문분석료차문제여일반량계단류수차문조도화무등대량계단류수차간조도적관계,급출료량류특수문제적다항식구해방법,탐토료최우조도적공건서렬특정.재차기출상,설계료기우배렬배서적계발식산법,산법응용Gilmore-Gomory계발식생성초시서렬,구조조도해적가체환집합실현질대심우,병이용공건서렬특정조정공건순서이우화당전조도.통과대산법적구해성능진행이론분석화실험험증,진일보표명료해산법적유효성.
