附件C：譯文

制造流程優(yōu)化中的進(jìn)化算法新發(fā)展：
問題、對策及比較

作者：Christos Dimopoulos and Ali M. S. Zalzala
摘要——由于大部分的制造流程優(yōu)化問題是組合性和NP難度問題，所以近十年來制造領(lǐng)域中智能技術(shù)的應(yīng)用得到增長。本文考核了制造流程優(yōu)化中的進(jìn)化算法新發(fā)展。文中對不同領(lǐng)域的優(yōu)秀論文做出標(biāo)記，并對可行數(shù)據(jù)給出比較結(jié)果。本文包括較寬范圍的問題，從作業(yè)車間和流水車間調(diào)度到工藝規(guī)劃和裝配線平衡。
關(guān)鍵詞——裝配線平衡，單元制造，設(shè)計(jì)，進(jìn)化算法，遺傳算法，制造流程優(yōu)化，工藝規(guī)劃，調(diào)度
１引言
從２０世紀(jì)５０年代開始，一些作者開始引用基于達(dá)爾文的進(jìn)化論的概念來解決優(yōu)化問題。［1］—［3］?；谕瑯拥睦碚?，過去30年里，眾多算法得到發(fā)展，這些算法通常稱為遺傳算法，其中一大部分是簡單遺傳算法（GAs）［4］，［5］，進(jìn)化策略［6］,進(jìn)化規(guī)劃［7］，分類器系統(tǒng)［8］，和進(jìn)化規(guī)劃［9］，Bäck 等人［10］綜述了進(jìn)化算法并突出了該領(lǐng)域的一些新情況。對進(jìn)化算法不熟悉的讀者可參考[11］和［12］。
大量的組合問題與制造流程優(yōu)化有關(guān)，其中大部分是完全NP難題，它們不能用多項(xiàng)式來求解，除非被證實(shí)P=NP［13］，通常是用啟發(fā)式算法來解決。越來越多的研究員采用巨集啟發(fā)式算法（智能啟發(fā)式算法）來對大型組合問題求解。進(jìn)化算法即是一種巨集啟發(fā)式算法，它能在解空間對大區(qū)域進(jìn)行搜索，而不致陷入局部最優(yōu)。其他熟知的巨集啟發(fā)式算法還有模擬退火(SA)[14]和禁忌搜索。
本文的目的是說明進(jìn)化算法在制造流程優(yōu)化領(lǐng)域的新發(fā)展?？紤]了寬范圍的優(yōu)化問題，從經(jīng)典作業(yè)車間和流水車間調(diào)度問題到裝配線平衡和集約生產(chǎn)計(jì)劃。我們主要關(guān)注新的出版物，不過對重要的早期方法也有說明。這樣，對具體問題感興趣的讀者可以將本文作為一個起點(diǎn)。文中不同的進(jìn)化計(jì)算方法統(tǒng)稱為“進(jìn)化算法”（EA’s）。
本文的結(jié)構(gòu)如下:第二部分為進(jìn)化算法關(guān)于作業(yè)車間調(diào)度問題中的新情況，第三部分關(guān)于流水車間調(diào)度問題，第四部分關(guān)于動態(tài)調(diào)度問題，第五部分關(guān)于工藝規(guī)劃問題，第六部分關(guān)于單元化制造優(yōu)化問題，第七部分關(guān)于匯編優(yōu)化問題，第八部分關(guān)于設(shè)計(jì)優(yōu)化問題，第九部分綜述其他制造流程優(yōu)化領(lǐng)域力的一些新發(fā)展，第十部分為本文的結(jié)論。