基于適應度地形的組合優(yōu)化與作業(yè)車間調(diào)度問題研究.pdf

1、車間調(diào)度是影響制造業(yè)生產(chǎn)效率的關鍵因素。在制造環(huán)境中，調(diào)度就是對加工過程進行作業(yè)計劃。采用高效的調(diào)度，可以“縮短工期、減少庫存、按時交貨、提高信譽”。隨著全球市場競爭的加劇和客戶需求的個性化，車間調(diào)度問題愈來愈受到重視。 大多數(shù)車間調(diào)度問題是NP難的，求解作業(yè)車間調(diào)度問題的最小加工時間是經(jīng)典的組合優(yōu)化問題之一。算法求解的效率與所要解決的問題特征密切相關，由于目前還缺乏對作業(yè)車間調(diào)度問題復雜性的深入研究，造成了目前求解組合優(yōu)化問題

2、時算法的選擇和參數(shù)設置具有盲目性。 本文在研究背包問題和旅行商問題的適應度地形特征的基礎上，分析了作業(yè)車間調(diào)度問題的復雜性，研究了作業(yè)車間調(diào)度問題的結構與適應度地形及其影響因素，研究了車間調(diào)度問題的Backbone，通過挖掘調(diào)度問題的內(nèi)在結構與性質(zhì)，為作業(yè)車間調(diào)度的研究提供一個新的理論支持；并在此基礎上，提出了相應的調(diào)度框架與調(diào)度方法。為指導組合優(yōu)化問題和作業(yè)車間調(diào)度問題的算法選擇提供了一定的依據(jù)，并為建立衡量組合優(yōu)化問題的近優(yōu)

3、算法效率的標準邁出了探索性的一步。 首先，介紹了組合優(yōu)化問題的一般研究方法以及無免費午餐定理，針對背包問題和旅行商問題，研究了它們的適應度地形，并對這些問題的解的特征、影響適應度地形的因素進行了分析。 然后，研究了作業(yè)車間調(diào)度問題的數(shù)學模型和析取圖模型，分析了作業(yè)車間調(diào)度問題的復雜性，針對該問題分析了解的特征、影響適應度地形的主要因素，以及適應度地形的不規(guī)則性，研究了作業(yè)車間調(diào)度問題的Backbone與解之間距離的關系。