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

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

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

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

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