基于遺傳變鄰域算法的置換流水車間調(diào)度問題研究.pdf

1、置換流水車間調(diào)度問題(PermutationFlowShopSchedulingProblem,PFSP)在實際生產(chǎn)制造中廣泛存在,對該類問題進(jìn)行研究可以有效提高企業(yè)的生產(chǎn)效率,從而降低制造成本,更好的實現(xiàn)企業(yè)的經(jīng)濟目標(biāo)。PFSP是一個NP-hard問題,近年來,許多元啟發(fā)式算法在求解該類問題的過程中顯示出了較好的效果。
　　目前,遺傳算法(GeneticAlgorithm,GA)是求解組合優(yōu)化問題的高效智能算法,而變鄰域搜索(V

2、ariableNeighborhoodSearch,VNS)是一種有效的局部搜索算法。本文通過組合GA和VNS的各自優(yōu)勢,提出一種混合優(yōu)化算法來求解PFSP及其拓展問題——帶準(zhǔn)備時間的PFSP,具體研究內(nèi)容如下:
　　對于單目標(biāo)PFSP,本文通過改進(jìn)GA并結(jié)合VNS提出了一種遺傳變鄰域算法(GeneticAlgorithmVariableNeighborhoodSearch,GAVNS)。混合算法基于GA的基本思想,通過引入外部檔

3、案集改進(jìn)GA的信息共享機制,提高求解質(zhì)量,并結(jié)合VNS算法,提高算法的局部搜索能力,使得算法能夠有效跳出局部最優(yōu)。然后對相關(guān)基準(zhǔn)實例進(jìn)行求解,并將所得結(jié)果與其他文獻(xiàn)進(jìn)行比較,驗證了該算法的有效性。
　　對于帶準(zhǔn)備時間的PFSP,將提出的混合GAVNS對帶準(zhǔn)備時間的單目標(biāo)PFSP進(jìn)行求解。并對標(biāo)準(zhǔn)測試實例進(jìn)行實驗比較,驗證了混合GAVNS在求解這類問題上的有效性。
　　考慮到實際生產(chǎn)中往往存在多個目標(biāo)需要同時優(yōu)化的情況,將混合

4、算法結(jié)合多目標(biāo)技術(shù),設(shè)計了一種基于Pareto思想的多目標(biāo)混合遺傳算法(MultipleObjectivehybridGeneticAlgorithm,MOHGA),用來求解帶準(zhǔn)備時間的多目標(biāo)PFSP。多目標(biāo)算法采用錦標(biāo)賽選擇從Pareto解集中選出其中擁擠距離較大的個體存入外部檔案集,使所得最優(yōu)解集具有更好的分散性。最后對標(biāo)準(zhǔn)實例進(jìn)行測試比較,驗證了MOHGA的有效性。
　　最后,進(jìn)行了全文總結(jié),并對遺傳變鄰域算法及流水車間調(diào)度