【正文】 調度算法 調度問題特點與分類調度問題的主要特點有:(1)建模、計算復雜性。通過研究與分析車間作業(yè)調度系統(tǒng)，給出了調度的數(shù)學模型，運用Matlab遺傳算法工具箱進行了仿真調度，并分析了結果。Davis是最早把遺傳算法應用于車間調度問題的學者之一，他在使用GA求解車間調度的問題的研究中取得了近似最優(yōu)解。生產(chǎn)調度對企業(yè)來說是至關重要的，在品種多、中小批量生產(chǎn)環(huán)境下的主生產(chǎn)調度問題更加復雜和重要[12]。作為實施CIMS工程中的一個重要組成部分，生產(chǎn)計劃與調度系統(tǒng)是計算機集成制造系統(tǒng)功能結構模型中不可缺少的一個層次。因此，有效的調度方法和優(yōu)化技術的研究和應用，是實現(xiàn)產(chǎn)品高質、低耗，進而使企業(yè)贏得市場競爭的有力武器[2]。制造業(yè)的經(jīng)營重心已從企業(yè)規(guī)模和產(chǎn)品成本轉移到用戶需求和上市時間、產(chǎn)品質量、制造成本和售后服務。實例證明，該程序算法結果較好，能充分利用設備資源組織生產(chǎn)，對于車間的實際生產(chǎn)具有較強的指導意義。有效的車間作業(yè)調度技術，可以增強車間資源優(yōu)、化配置能力、提高企業(yè)的生產(chǎn)效率、減少生產(chǎn)損耗，使企業(yè)在經(jīng)濟全球化的競爭中處于領先地位?，F(xiàn)代制造業(yè)的生產(chǎn)特點是品種多、批量小(甚至是單件生產(chǎn))，而車間資源的有限性制約著能否有效利用車間現(xiàn)有資源完成任務，以最快的速度響應市場需求。關鍵詞：作業(yè)調度，遺傳算法，MATLABJob Scheduling Optimization Based on Genetic AlgorithmABSTRACTIn the manufacturing era of economic globalization, demand for our products of customer requires shorter product life cycle. Modern manufacturing and service rendered to the state of integration. The jobshop scheduling technology is the core technology of the production and management technology, is directly related to the quality of enterprise products and services. Effective job shop scheduling techniques can enhance the workshop resources, optimal allocation of capacity, improve production efficiency, reduce production losses, so that enterprises can locate in the central position in the petition of economic globalization.The feature of modern manufacturing sector is variety, small batch (or even a single piece production). The limited resources of the workshop restricting the effective use of existing workshop resources to plete the task to meet market demand in the fastest pace. The scheduling task is to determine the specific processing route, time, machinery and operation according to production goals and constraints for each processing object. Good scheduling strategy has a great role for the optimal production system, improve economic efficiency. The job shop scheduling problem is a typical NPhard problem,and is the most difficult binatorial optimization problems.In this paper, we study manufacturing job shop scheduling problem. The paper systematically introduces the job shop scheduling theory and its development, optimization algorithm for job shop scheduling theory and its characteristics。制造過程中的生產(chǎn)管理與調度是保證生產(chǎn)質量和生產(chǎn)效率的關鍵，先進的生產(chǎn)管理與調度技術能夠快速響應顧客需求變化的多樣性。 課題的現(xiàn)實與理論意義車間作業(yè)調度問題(JobShop Scheduling Problem，JSP)的求解目標是尋求某種最優(yōu)策略，找到的調度方案能將加工作業(yè)安排到車間制造機器上，并且使加工作業(yè)能夠最高效的完成。當前在自動化程度較高的生產(chǎn)系統(tǒng)中，使生產(chǎn)過程合理、高效運行的調度問題變得非常復雜，需要建立有效的計算機調度控制策略、因此調度問題的研究具有重要的現(xiàn)實意義。 國內外研究現(xiàn)狀綜述車間作業(yè)調度問題是一個經(jīng)典而又傳統(tǒng)的問題，對于它的研究始于20世紀50年代。遺傳算法的優(yōu)越性主要表現(xiàn)在搜索過程中不易陷入局部最優(yōu)，即使在所定義的適應度函數(shù)不連續(xù)的情況下，也能以極大的概率找到最優(yōu)解[9]。本文主要分五章，具體安排如下：第一章說明了課題的提出背景和研究意義，討論了車間調度的國內外研究現(xiàn)狀，最后給出了本文的研究內容和文章的結構安排。車間中工件、機器、操作人員和搬運系統(tǒng)之間相互影響、相互制約。車間的生產(chǎn)能力不僅會受到機床的制約，還會受到工人和輔助工具的制約，各道工序的先后關系不能顛倒，如緩存容量、資源數(shù)量、工件到期時間與操作順序等也是制約因素。(5)靜態(tài)調度、動態(tài)事實調度。切換加工的次數(shù)越多越有利于減少工件的庫存，但導致生產(chǎn)率的下降。每臺機床可加工工件的若干操作，并且在不同的機床上能加工的操作集可以不同。如作業(yè)的平均等待時間、機床的平均利用率、作業(yè)總加工時間等。比如，Petri網(wǎng)作為一種圖形建模工具可以形象地表示和分析FMS（柔性制造系統(tǒng)）中加工過程的并發(fā)和分布本質，以及多項作業(yè)共享資源時的沖突現(xiàn)象。該方法主要需要解決搜索效率和降低內存使用問題，對大規(guī)模的問題需進一步探討。搜索網(wǎng)絡（Hopfield）模型可以求解各種有約束的優(yōu)化問題，隨機Hopfield也可以用于解決jobshop的調度問題。對此類多目標優(yōu)化問題，常用數(shù)學規(guī)劃中的約束法、評價函數(shù)法、分層序列法、功效函數(shù)法等。遺傳算法作為一種快捷、簡便、容錯性強的算法，在各類結構對象的優(yōu)化過程中顯示出明顯的優(yōu)勢。(5)黑箱式結構。3. 群體規(guī)模（Population Size）：群體中個體的數(shù)目成為群體個數(shù)，也稱為群體規(guī)?；蛉后w大小。7. 適應度（Fitness）函數(shù)：適應度表示某個體對于環(huán)境的適應程度。下面對關鍵參數(shù)與操作的設計做簡單介紹。②適值函數(shù)即個體空間S到正實數(shù)空間的映射，適值函數(shù)f為 f:S→R+遺傳算法在搜索進化過程中一般不需要其它外部信息，僅用適應度函數(shù)值來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。錦標賽選擇(tournament selection)。如若選擇交換第k個分量以后的所有分量，則兩個后代為sz =( v1（1），v2(1)，…，vk（1），vk+1（2），…vm（2）)sw =( v1（2），v2(2)，…，vk（2），vk+1（1），…vm（1）)組合優(yōu)化中的置換編碼遺傳算法通常采用部分映射交叉、次序交叉、循環(huán)交叉、基于位置的交叉，群交叉等操作。較高的交叉率可達到更大的解空間，但會因搜索不必要的解空間而耗費大量的計算時間，從而降低停在非最優(yōu)解上的機會。 遺傳算法執(zhí)行策略遺傳算法在執(zhí)行策略方面的下面幾方面工作值得注意:模擬退火（Simulated Annealing)是一種基于熱力學理論的優(yōu)化方法，并有著完善的全局收斂理論。而細胞模型的實施則是在一個單一種群中，通過對經(jīng)典整體性選擇與雜交機制的局部化來達到并行化目的。(5) 不考慮工件加工的優(yōu)先權，不考慮加工準備時間。 編碼選擇一種合適的染色體表現(xiàn)型是應用遺傳算法尋優(yōu)的首要和關鍵問題。 生成初始種群本文采用的十進制的編碼方式，這里采用隨機產(chǎn)生初始種群的方法。一般這樣操作很容易產(chǎn)生不合理的染色體表現(xiàn)型。這些染色體在后續(xù)迭代中不斷進化，稱為遺傳。據(jù)此，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或次優(yōu)解。提出問題最優(yōu)解編碼和生成染色體群檢測染色體的適應度選擇交叉滿足件件？變異 GA流程圖5 用Matlab實現(xiàn)模擬作業(yè)調度 程序設計思想及偽代碼文中所設計的遺傳算法是利用MATLAB語言編寫的，下面為程序的部分偽代碼：(1)遺傳算法參數(shù)(變量聲明)遺傳算法參數(shù)包括：m工件總數(shù)；n工序總數(shù)。%記錄每個工件的工序數(shù)for i=1:m pron(i)=length(find(W(i,:)~=0))。 endend counter=0。 b(i)=A(i,cp(i,2))。%交叉后的子代存入newfarm for j=1:6 oo(i,j)=length(find(newfarm(i,:)==j))。 Xp(I)= mu2。) hold on plot(counter,LC2(counter),39。%num=zeros(1,m)。 %記錄調度方案各工序的開工時間 s2=zeros(1,pn)。 s2(Xp(j))=s1(Xp(j))+W(Xp(j),num(Xp(j)))。 FITNESS(i)=Z。 LC1(counter+1)=minfitness。 ％變異概率P=6。②運行結果輸出：最佳調度方案Xp（最優(yōu)染色體）；最優(yōu)適應值收殮曲線和各代群體平均適應值曲線；基于工件的工序時間甘特圖；基于機器的工序時間甘特圖；程序運行時間。遺傳算法模擬生物進化的優(yōu)勝劣汰的規(guī)則，能在較大的范圍內搜索并逐漸逼近最優(yōu)解，圖中的曲線記錄了這個逼近過程。由圖4，很容易得知每個機床在任何時間段的加工任務。本文主要研車間作業(yè)調度問題，研究是基于遺傳算法進行的。通過MATLAB仿真驗證：較之其它調度方法，仿真調度的優(yōu)越性比較突出，能適合多條件約束的生產(chǎn)情形，能有效地提高生產(chǎn)效率。本文基于車間生產(chǎn)局部考慮，選定的適應度評價函數(shù)表明，生產(chǎn)任務越早完成越好。大學四年來老師們給了我們很多指導和幫助。在此，我對機械工程與自動化學院的所有老師表示感謝，祝你們身體健康，工作順利！同時還要感謝所有的同學們，正是因為有了你們的支持和鼓勵，此次畢業(yè)設計才能順利完成。作為企業(yè)應綜合考慮所有方面的影響，使企業(yè)綜合效益最大。本文通過簡易的編程即可實現(xiàn)生產(chǎn)車間作業(yè)的模擬調度，并且得到了最佳調度方案。在解決組合優(yōu)化問題方面的優(yōu)勢己受到各個領域專家、學者的關注，其應用領域已涉及自適應控制、組合優(yōu)化、模式識別、機器學習、信息處理和人工生命等。⑤最后輸出整個程序運行時間使用tic和toc函數(shù)，連續(xù)5次運行程序，時間如下： 程序運行時間次數(shù)12345時間/s 由表可得，每次的運行時間不同，但都是2秒多。 最優(yōu)適應值收殮曲線 ③： 基于工件的甘特圖 根據(jù)圖3可以很明了的看出各工件的各個工序的開始加工時間、加工結束時間、還有各個工件工序對應的加工機器。按照工件編碼的出現(xiàn)順序依次，可將對應的工件安排到指定的機器上加工，如第3次出現(xiàn)“2”代表工件2的第三道工序安排到機器5上加工。 2 3 5 2 1 4 。 %收斂曲線2，各代群體平均適應值的記錄% pos=find(FITNESS==minfitness)。farm1=POPU(index,:)。 s4(Q(Xp(j),n