【正文】 其信息流與物質(zhì)流有機(jī)地集成并優(yōu)化運(yùn)行[3][4]。由于大量的調(diào)度問(wèn)題是NP完全問(wèn)題[13]，近幾年各種智能計(jì)算方法逐漸被引入到調(diào)度問(wèn)題中，如遺傳算法、模擬退火算法等，但是目前尚無(wú)有效的求解策略，因此調(diào)度問(wèn)題的研究也具有重要的理論意義[5]。它研究的是如何合理地配置加工過(guò)程的各種資源，減少零件在加工過(guò)程中的各種浪費(fèi)，從而提高設(shè)備利用率和生產(chǎn)率，降低生產(chǎn)成本。1954年，Johnson對(duì)兩臺(tái)機(jī)床FlowShop型調(diào)度問(wèn)題進(jìn)行了研究后，提出了解決車間調(diào)度部分特殊問(wèn)題的優(yōu)化算法，代表理論研究的開(kāi)始。隨著70年代后期調(diào)度理論研究的深入及各種交叉學(xué)科的發(fā)展，又涌現(xiàn)出了許多新的車間調(diào)度理論與方法，如：基于運(yùn)籌學(xué)（OR）方法[6]、基于控制的方法、基于DEDS（離散事件動(dòng)態(tài)系統(tǒng)）的解析模型方法、模擬退火法，啟發(fā)式算法[10]，禁忌搜索法[7]以及拉格朗日約束松弛法[8]等，代表著經(jīng)典調(diào)度理論趨向成熟。此后，很多學(xué)者就遺傳算法在車間調(diào)度問(wèn)題方面的應(yīng)用做了大量研究。目前,研究工作主要集中在清華大學(xué)等CIMS(Computer Integrated Manufacturing System)國(guó)家重點(diǎn)實(shí)驗(yàn)室，這些實(shí)驗(yàn)室的系統(tǒng)開(kāi)發(fā)基本上還處于試用階段，距離開(kāi)發(fā)出成熟的軟件系統(tǒng)還有很長(zhǎng)一段距離，因此還需要投入大量的人力物力進(jìn)行該方面的研究。第二章詳細(xì)闡述了車間作業(yè)調(diào)度問(wèn)題，分析了調(diào)度模型及模型描述，總結(jié)了車間調(diào)度的求解方法。第五章運(yùn)用Matlab遺傳算法工具箱，通過(guò)編碼實(shí)現(xiàn)模擬作業(yè)調(diào)度。每個(gè)工件又要考慮它的加工時(shí)間、安裝時(shí)間和操作順序等因素，因而相當(dāng)復(fù)雜，調(diào)度問(wèn)題往往是通過(guò)等式或不等式等約束條件來(lái)計(jì)算的，屬于典型的NPhard問(wèn)題。如機(jī)器故障、作業(yè)交貨期的變更，如工件到達(dá)時(shí)間的不確定性，實(shí)際工件的加工時(shí)間也有一定的隨機(jī)性。此外，還有人為的附加因素，如機(jī)器負(fù)荷平衡等等約束條件。(2)單臺(tái)處理機(jī)、多臺(tái)并行機(jī)、Job—shop和Flow—shop。(6) 有序加工，無(wú)序加工。調(diào)度的結(jié)果就是確定決策方案，決策內(nèi)容包括分配決策(工件的加工順序)和時(shí)間決策(工件各工序的加工時(shí)間)以及路徑?jīng)Q策(工件工序的加工設(shè)備的分配)。如果車間有足夠多的機(jī)床設(shè)備和其它生產(chǎn)資源分配給每個(gè)工件或每條工藝加工路線，那么一切都會(huì)井然有序，也就不存在調(diào)度問(wèn)題。具有可選的路徑，可以通過(guò)將若干設(shè)備組作為一條或者多條生產(chǎn)線加工一種工件，使得該工件的生產(chǎn)率最大。調(diào)度的目標(biāo)是將作業(yè)合理地安排到各機(jī)床以及合理地使用其它生產(chǎn)資源，并合理安排作業(yè)的加工次序和加工時(shí)間，使約束條件被滿足，同時(shí)優(yōu)化其中的一些生產(chǎn)性能指標(biāo)。采用數(shù)學(xué)規(guī)劃的方法大致可以分為三類：簡(jiǎn)單規(guī)則、復(fù)合規(guī)則、啟發(fā)式規(guī)則。（3）基于知識(shí)的調(diào)度方法近年來(lái)受實(shí)際需要的推動(dòng)，基于知識(shí)的智能調(diào)度系統(tǒng)和方法的研究取得了很大的進(jìn)展，基于只是的調(diào)度方法是用專家系統(tǒng)自動(dòng)產(chǎn)生調(diào)度或輔助人去調(diào)度，它是傳統(tǒng)的調(diào)度方法與基于知識(shí)的調(diào)度評(píng)價(jià)相結(jié)合的方法。b)應(yīng)用仿真進(jìn)行生產(chǎn)調(diào)度的費(fèi)用很高。Petri網(wǎng)具有很強(qiáng)地建模能力，對(duì)于描述系統(tǒng)的不確定性和隨機(jī)性也具有一定地優(yōu)越性，目前Petri網(wǎng)已經(jīng)用于FMS建模和調(diào)度，但尚存在下列問(wèn)題:l)節(jié)點(diǎn)語(yǔ)義的單義性，使得所攜帶的系統(tǒng)信息量不夠豐富。（6）啟發(fā)式圖搜索法在人工智能中啟發(fā)式圖搜索法是圖搜索的重要策略之一，在啟發(fā)式圖搜索法中最引人注目的A*算法，在圖搜索過(guò)程中A*算法能夠通過(guò)選擇合適的評(píng)價(jià)函數(shù)尋找達(dá)到目標(biāo)結(jié)點(diǎn)的最佳路徑。（7）模擬退火模擬退火法（SA）是將組合優(yōu)化問(wèn)題與統(tǒng)計(jì)力學(xué)的熱平衡問(wèn)題類比，通過(guò)模擬退火過(guò)程，可找到全局(或近似)最優(yōu)解。（8）禁忌搜索法對(duì)于復(fù)雜的組合優(yōu)化問(wèn)題，禁忌搜索也是一種通過(guò)領(lǐng)域搜索以獲取最優(yōu)解的方法，Gfover首次敘述了它的基本原理。（10）拉格朗日(LR)松弛算法LR算法由于其在可行的時(shí)間里能對(duì)復(fù)雜的規(guī)劃問(wèn)題提供較好的次優(yōu)解，并能對(duì)解的次優(yōu)性進(jìn)行定量評(píng)估，近年來(lái)已成為解決復(fù)雜生產(chǎn)調(diào)度問(wèn)題的一種重要方法。基于目前的研究，對(duì)于動(dòng)態(tài)調(diào)度的具體策略有:周期調(diào)度，連續(xù)調(diào)度，事件驅(qū)動(dòng)調(diào)度，周期與事件驅(qū)動(dòng)混合調(diào)度，周期與連續(xù)調(diào)度混合的策略等。隨著各種特殊調(diào)度問(wèn)題的攻克和新方法、新設(shè)備的出現(xiàn)，作業(yè)車間調(diào)度研究正在向動(dòng)態(tài)、敏捷、多重入、多資源、智能化的方向發(fā)展。調(diào)度問(wèn)題屬于NPplete問(wèn)題，很難建立準(zhǔn)確的數(shù)值模型，由于調(diào)度規(guī)則是基于經(jīng)驗(yàn)，故沒(méi)有普遍適用的規(guī)則存在，某一規(guī)則只能運(yùn)用于一定的場(chǎng)合，應(yīng)用調(diào)度規(guī)則求得的解也只是問(wèn)題的近優(yōu)解，很難保證其解的有效性。與傳統(tǒng)的搜索方法相比，遺傳算法具有如下特點(diǎn):(1)搜索過(guò)程不直接作用在變量上，而是在參數(shù)集進(jìn)行了編碼的個(gè)體。采用概率的變遷規(guī)則來(lái)指導(dǎo)搜索方向，而不采用確定性搜索規(guī)則。應(yīng)用遺傳算法時(shí)，根據(jù)具體問(wèn)題的特性，進(jìn)行編碼與適應(yīng)度設(shè)計(jì)之后，其余操作按常規(guī)算子自動(dòng)運(yùn)行即可，只等最后輸出最優(yōu)解個(gè)體，而不必關(guān)心求解的實(shí)際過(guò)程，所以遺傳算法非常便于處理那些輸入輸出之間因果關(guān)系復(fù)雜的問(wèn)題。這些概念如下所示：1. 串（String）：串是個(gè)體（Individual）的形式，在算法中為字符串，并且對(duì)應(yīng)于遺傳學(xué)中的染色體（Chromosome）。4. 基因（Gene）：基因是串中的元素，基因用于表示個(gè)體的特征?；虿僮魇窃诖Y(jié)構(gòu)空間中進(jìn)行的。對(duì)于優(yōu)化問(wèn)題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)，遺傳算法對(duì)于適應(yīng)度函數(shù)并不要求可導(dǎo)等條件，只要求適應(yīng)度函數(shù)為可加以比較的非負(fù)函數(shù)。在遺傳算法中為通過(guò)交配原則產(chǎn)生一組新解的過(guò)程。①編碼將問(wèn)題的潛在解用一些參數(shù)表示，這些參數(shù)(基因)排列在一起形成一個(gè)特定的編碼(染色體)，代表一個(gè)個(gè)體，從而將問(wèn)題的狀態(tài)空間與遺傳算法的碼空間相對(duì)應(yīng)，這很大程度上依賴于問(wèn)題的性質(zhì)，并將影響遺傳操作的設(shè)計(jì)。實(shí)數(shù)編碼解決了二進(jìn)制和十進(jìn)制編碼對(duì)算法精度和存儲(chǔ)量的影響，同時(shí)便于優(yōu)化中引入問(wèn)題的相關(guān)信息，譬如梯度信息。根據(jù)求解問(wèn)題特性來(lái)定義反應(yīng)個(gè)體對(duì)問(wèn)題環(huán)境適應(yīng)能力和優(yōu)劣程度的測(cè)定函數(shù)。隨機(jī)遍歷抽樣((stoehastic universal sampling)。④交叉交叉算子是母體空間到個(gè)體空間的映射，記作Tc:S2→S交叉是最主要的遺傳運(yùn)算，它同時(shí)對(duì)兩個(gè)染色體操作，交叉操作用于結(jié)合來(lái)自父染色體和母染色體的特征來(lái)產(chǎn)生新的子個(gè)體，在解空間中進(jìn)行有效搜索，同時(shí)降低對(duì)有效模式的破壞概率。以下以離散交叉為例介紹實(shí)數(shù)編碼的交叉方式。⑤變異變異是一種基本運(yùn)算，它在染色體上自發(fā)地產(chǎn)生隨機(jī)的變化。種群規(guī)模選擇較大時(shí)，可以同時(shí)處理更多的解，因而容易找到全局最優(yōu)解，其缺點(diǎn)是增加了每次迭代所需要的時(shí)間。 變異率(記為Pm)定義為種群中變異基因數(shù)中的百分比。另一種是把算法的運(yùn)行時(shí)間作為停止準(zhǔn)則。在遺傳算法中以各種形式融入模擬退火思想，從而使得遺傳算法在理論上具有全局收斂性，是一個(gè)有意義的研究方向。(Parallel Genetic Algorithm)并行遺傳算法是在遺傳算法的實(shí)施中加入自然生物種群中的空間結(jié)構(gòu)因素，它的目的是可以在大規(guī)模并行機(jī)上運(yùn)行，即使是序列式實(shí)施并行遺傳算法，也可克服經(jīng)典遺傳算法性能上的不足，從而提高算法的效率。島模型考慮的是種群的空間結(jié)構(gòu)，而細(xì)胞模型考慮的是一種群中個(gè)體的空間結(jié)構(gòu)。混亂遺傳算法的理論基礎(chǔ)、算法設(shè)計(jì)及實(shí)驗(yàn)比較，均是有待探討的課題。(6) 一個(gè)工件同一時(shí)間只能在一臺(tái)機(jī)器上加工，一臺(tái)機(jī)器同一時(shí)間只能加工一個(gè)工件，加工的開(kāi)始時(shí)間為O。遺傳算法通?？啥x為一個(gè)五元組GA=（C，F(xiàn)，PO，O，Para），式中C 表示個(gè)體（染色體）的編碼方法；F 表示個(gè)體的適應(yīng)度評(píng)價(jià)函數(shù)；PO表示問(wèn)題的初始解群；O表示一組基本的遺傳操作，包括選擇算子、交叉算子和變異算子；Para 表示一組遺傳算法的參數(shù)，包括群體規(guī)模N、交叉概率Pc 和變異概率Pm等。遺傳算法的編碼技術(shù)必須考慮染色體的合法性、可行性、有效性以及問(wèn)題解空間的表征的完全性。在染色體編碼中，給定所有同一工件的的工序指定相同的符號(hào)，即工件編號(hào)，根據(jù)它們?cè)诮o定染色體中出現(xiàn)的先后順序就可以確認(rèn)是第幾道工序。也就是在一個(gè)給定的合理的染色體的基礎(chǔ)上，產(chǎn)生兩個(gè)隨機(jī)數(shù)作為交換位置，再交換兩位置之間的基因，進(jìn)而產(chǎn)生新的染色體。每次進(jìn)行適應(yīng)度比較的種群規(guī)模為2*N，每次選擇N個(gè)適應(yīng)度最高的個(gè)體遺傳給下一代。 變異算子變異操作在本問(wèn)題中相對(duì)而言比較簡(jiǎn)單。遺傳算法和傳統(tǒng)的搜索算法不同，它從一組隨機(jī)產(chǎn)生的初始解，即為“種群”開(kāi)始搜索過(guò)程。個(gè)體遺傳算子的操作都是在隨機(jī)擾動(dòng)情況下進(jìn)行的。因?yàn)?，在每一代中用“適應(yīng)度”來(lái)測(cè)量染色體的好壞，生成的下一代染色體稱為后代，后代是由前一代染色體通過(guò)“交叉”或者“變異”運(yùn)算形成的。遺傳算法搜索求解的基本步驟是:確定編碼方案并隨機(jī)產(chǎn)生種群，種群中個(gè)體的數(shù)目一定，每個(gè)個(gè)體表示為染色體的基因編碼。按照一定的交叉概率和交叉方法，生成新的個(gè)體。 P機(jī)器總數(shù)；M遺傳算法進(jìn)化代數(shù)：N種群規(guī)模；Pc交叉概率；Pm變異概率；Q機(jī)器序號(hào)矩陣；W操作時(shí)間矩陣；Xp最優(yōu)調(diào)度方案； farm種群。%最優(yōu)決策變量LC1=zeros(1,M)。end OPT_S=zeros(M,pn)。%采用矩陣結(jié)構(gòu)存儲(chǔ)種群for i=1:N for j=1:pn gene=randint(1,1,[1 m])。%設(shè)置迭代計(jì)數(shù)器while counter ~=M (4)交叉newfarm=zeros(N,pn)。%父代個(gè)體 A(i,:)= B(i,:)。 A(i,cp(i,1))=b(i)。 A(i,cp(i,3))=d(i)。 end end %新舊種群合并 POPU=[farm。 I=1+unidrnd(pn2)。 Xp(I1)= mu1。 X(counter,:)=farm(1,:)。.39。 Y1p=zeros(2*N,pn)。 %num用于循環(huán)過(guò)程記錄工件號(hào)出現(xiàn)的次數(shù) for i=1:2*N Xp= POPU(i,:)。 %記錄調(diào)度方案各工序的完工時(shí)間 MS=zeros(1,pn)。 %記錄調(diào)度方案各工序的完工時(shí)間 s3=zeros(1,pn)。 PS(j)=s1(Xp(j))。 PE(j)= s2(Xp(j))。 end Y1p(i,:)=PS。 end [fitness index]=sort(FITNESS)。OPT_M(counter+1,:)=Y3p(index(1),:)。 %收斂曲線1，各代最優(yōu)個(gè)體適應(yīng)值的記錄 LC2(counter+1)=meanfitness。 % M 遺傳進(jìn)化迭代次數(shù)N=50。 % P 機(jī)床數(shù)目%Q mn的矩陣，存儲(chǔ)m個(gè)工件n個(gè)工序?qū)?yīng)的加工機(jī)器Q=[ 3 1 2 4 3 5 。 1 2 5 6 1 4 。 分析結(jié)果①最優(yōu)調(diào)度方案：Xp=[ 4 3 3 5 1 6 1 2 5 3 4 6 2 4 6 3 5 4 5 1 5 3 2 1 6 4 6 1 2 4 2 5 1 2 6 3]由Xp可以得出，1～6（每個(gè)工件代碼）各出現(xiàn)6次，即代表每個(gè)工件的各道工序都在調(diào)度方案中。②最優(yōu)適應(yīng)值收殮曲線（“*”）和各代群體平均適應(yīng)值曲線（“.”）：橫坐標(biāo)為種群進(jìn)化代數(shù)，縱坐標(biāo)為適應(yīng)值。各代群體平均適應(yīng)值在不斷面的變化，這是由于遺傳算法不定向搜索造成的。圖中橫坐標(biāo)表明了這批工件加工的時(shí)間歷程,縱坐標(biāo)表明機(jī)床設(shè)備,用兩個(gè)字符標(biāo)識(shí)的方框代表一道工序。調(diào)度結(jié)果通過(guò)甘特圖的顯示，將調(diào)度結(jié)果圖示化有利于工件在加工前各機(jī)器的準(zhǔn)備工作，目標(biāo)就是降低不必要的等待浪費(fèi)。經(jīng)計(jì)算該程序的運(yùn)行時(shí)間平均值為：t= s。遺傳算法是一種通用而有效的解決最優(yōu)化問(wèn)題的方法，它不僅具有并行搜索、魯棒性強(qiáng)等特點(diǎn)，而且遺傳算法由于其結(jié)構(gòu)的開(kāi)放性，可以更好地綜合多種優(yōu)化方法來(lái)獲得更優(yōu)的性能。分析了當(dāng)前制造業(yè)的生產(chǎn)特點(diǎn)(品種多、批量小)，生產(chǎn)車間調(diào)度情況符合本文給出的生產(chǎn)車間作業(yè)調(diào)度模型，并利用Matlab仿真驗(yàn)證了模型的正確性。Matlab是一個(gè)包含大量計(jì)算算法的集合，具有強(qiáng)大的計(jì)算機(jī)數(shù)據(jù)處理能力和出色的圖形處理功能。但由于調(diào)度問(wèn)題本身的復(fù)雜性，這些成果與實(shí)際的調(diào)度問(wèn)題之間都存在一定的差距，尚不能很好地解決復(fù)雜的實(shí)際生產(chǎn)作業(yè)車間調(diào)度問(wèn)題。在此，沒(méi)有考慮產(chǎn)品完工時(shí)間對(duì)于企業(yè)庫(kù)存壓力的影響，實(shí)際上，如果產(chǎn)品提前完工，一定會(huì)增加企業(yè)的庫(kù)存成本或帶來(lái)其它方面的影響。在這里我首先要感謝我的指導(dǎo)老師侯世旺老師。老師們嚴(yán)謹(jǐn)?shù)闹螌W(xué)，優(yōu)良的作風(fēng)和敬業(yè)的態(tài)度，為我們樹(shù)立了為人師表的典