共生遺傳算法求解作業(yè)調(diào)度研究.pdf

1、　　車間作業(yè)調(diào)度問題是制造系統(tǒng)的一個研究熱點，在理論研究方面也是最為困難的問題之一，此問題具有約束性，非線性，不確定性和大規(guī)模性，已被證明調(diào)度問題是NP-hard問題，很難求得最優(yōu)解。人們研究和發(fā)展了多種優(yōu)化算法來處理此類問題：比如模擬退火，遺傳算法，禁忌搜索，神經(jīng)網(wǎng)絡等。這些優(yōu)化方法模擬或運用自然現(xiàn)象，過程和規(guī)律而得到發(fā)展，其思想涉及數(shù)學，物理，人工智能等多個學科。
　　在車間作業(yè)調(diào)度的過程中，要根據(jù)生產(chǎn)目標和約束條件，為每個加

2、工對象確定具體的加工路徑以及各具體操作的執(zhí)行機器和時間。傳統(tǒng)的作業(yè)調(diào)度問題的提法是：n個工件(job)要在m臺機器上加工，每個工件需要經(jīng)過m道工序(operation)，每道工序可能要求不同的機器。問題的目標是求n個工件在每臺機器上最優(yōu)的加工順序，使最大流程時間達到最小。當然還有其他一些變種，比如規(guī)定n個工件在m臺機器上的加工順序相同或不同。傳統(tǒng)的作業(yè)調(diào)度一般假定對每個工件只有一個可行的加工方案，即作業(yè)處理計劃中沒有柔性，而在現(xiàn)在的制造

3、系統(tǒng)中，出現(xiàn)了各種作業(yè)柔性。大多數(shù)工件(job)具有大量的柔性加工方式和工序。即可以選擇不同的工序序列來完成加工此工件，同時實現(xiàn)某個工序存在由多個機器的組成的集合。在本文中，將對這種適應新的制造系統(tǒng)的作業(yè)調(diào)度運用共生遺傳算法來進行計算，根據(jù)前人給出此種作業(yè)的編碼和解碼模型，以及多種群共生遺傳算法，來改進問題求解的質(zhì)量。
　　在共生遺傳種群中，如何衡量個體在整個調(diào)度中的表現(xiàn)是一個重要的問題，衡量指標選擇的好壞(也就是適應度函數(shù)定義的

4、好壞)直接影響到算法運行的結(jié)果和效率。在本文中，我們提出了一種新的共生個體的適應度函數(shù)的計算方法，通過大量的實驗結(jié)果表明，在同等的測試環(huán)境下，新適應度函數(shù)表現(xiàn)優(yōu)異。
　　在論文中我們還研究其他多種因素對遺傳算法進化的影響。在共生算法中，共生鄰域的大小也是要考慮的因素，我們用實驗檢測了鄰域大小對算法結(jié)果和算法效率的影響，在傳統(tǒng)的單個種群的遺傳算法中，為了提高算法效率，在選擇的過程中，常常引入輪盤賭算法，在本文中，我們用實驗表明了，在