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

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

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

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