【正文】 型結(jié)構(gòu)。（5）基于DEDS的解析模型方法現(xiàn)實中的制造系統(tǒng)往往是離散事件系統(tǒng)，因此可以用研究離散事件系統(tǒng)解析模型和方法探討車間調(diào)度問題，諸如排隊論、極大極小代數(shù)模型、Petri網(wǎng)等。（4）仿真調(diào)度方法由于制造系統(tǒng)的復雜性，很難用一個精確的解析模型來進行描述分析，而通過對仿真模型的運行收集數(shù)據(jù)，就能對實際系統(tǒng)進行性能，狀態(tài)方面的分析，從而能對系統(tǒng)采用合適的控制調(diào)度方法。這類方法因調(diào)度規(guī)則易于實現(xiàn)，計算復雜度低，能夠用于動態(tài)實時調(diào)度系統(tǒng)中，許多年來一直受到廣泛關(guān)注和研究，并不斷涌現(xiàn)許多新的調(diào)度規(guī)則。這類方法從理論上來說是能求得最優(yōu)解，但通常由于計算復雜性原因，不能獲得真正的實用。車間調(diào)度就是對一個可用的加工機床集在時間和空間上進行加工任務(wù)集分配，以達到生產(chǎn)性能指標最優(yōu)化。因此，需要在庫存成本與切換加工次數(shù)頻率之間尋求一個動態(tài)的平衡。車間調(diào)度的問題是多個工件在有限的機器上加工，每臺機器在切換不同的工件加工時又需要一定的生產(chǎn)加工準備時間。 車間作業(yè)調(diào)度問題描述一般車間調(diào)度問題可以描述為:n個工件在m臺機器上加工，每個工件分為k道工序，每道工序可在不同的機器上加工。(4)確定性調(diào)度、隨機性調(diào)度。如基于作業(yè)交貨期的目標、基于作業(yè)完成時間的目標、基于生產(chǎn)成本的目標等。(3)多約束性調(diào)度中受到很多約束條件的限制。在現(xiàn)有計算條件下，一般優(yōu)化方法對于車間調(diào)度問題是低效甚至是無能為力的。第 34 頁 共 34 頁 2 車間作業(yè)調(diào)度算法 調(diào)度問題特點與分類調(diào)度問題的主要特點有:(1)建模、計算復雜性。重點研究了遺傳算法在車間作業(yè)調(diào)度優(yōu)化中的操作過程，包括了編碼方式、種群大小、交叉方式與概率、變異方法與概率等參數(shù)的選擇。通過研究與分析車間作業(yè)調(diào)度系統(tǒng)，給出了調(diào)度的數(shù)學模型，運用Matlab遺傳算法工具箱進行了仿真調(diào)度，并分析了結(jié)果。國內(nèi)對于車間調(diào)度問題的研究起步比較晚，基本上是靠調(diào)度人員的經(jīng)驗進行車間作業(yè)分配和調(diào)度。Davis是最早把遺傳算法應(yīng)用于車間調(diào)度問題的學者之一，他在使用GA求解車間調(diào)度的問題的研究中取得了近似最優(yōu)解。由于車間調(diào)度問題的復雜性，各種不同的具體問題往往有不同的解決方法。生產(chǎn)調(diào)度對企業(yè)來說是至關(guān)重要的，在品種多、中小批量生產(chǎn)環(huán)境下的主生產(chǎn)調(diào)度問題更加復雜和重要[12]。具體就是針對一項可分析的工作（如產(chǎn)品制造），探討盡可能滿足約束條件（如交貨期、工藝路線、資源情況）的前提下，通過下達生產(chǎn)指令，安排其組成部分（操作哪些資源）、其加工時間及加工的先后順序，以達到合理利用產(chǎn)品制造資源，獲得產(chǎn)品制造時間和成本的最優(yōu)化[14] ，提高企業(yè)經(jīng)濟效益的目的。作為實施CIMS工程中的一個重要組成部分，生產(chǎn)計劃與調(diào)度系統(tǒng)是計算機集成制造系統(tǒng)功能結(jié)構(gòu)模型中不可缺少的一個層次。以前大部分企業(yè)主要依靠經(jīng)驗豐富的工人手工安排調(diào)度計劃，在調(diào)度問題比較簡單的情況下還是可行的。因此，有效的調(diào)度方法和優(yōu)化技術(shù)的研究和應(yīng)用，是實現(xiàn)產(chǎn)品高質(zhì)、低耗，進而使企業(yè)贏得市場競爭的有力武器[2]。對于中小型企業(yè)來敏捷制造就是先進的生產(chǎn)模式，生產(chǎn)調(diào)度方案的優(yōu)劣是敏捷制造的標志。制造業(yè)的經(jīng)營重心已從企業(yè)規(guī)模和產(chǎn)品成本轉(zhuǎn)移到用戶需求和上市時間、產(chǎn)品質(zhì)量、制造成本和售后服務(wù)。 we use chromosome coding, genetic operators and genetic algorithm to solve the scheduling problem. In addition, using the Matlab numerical puting power and number of library functions to write the algorithm to test the effects of algorithm by simulation examples. Examples show that The program algorithm is better, equipment of organizing production resource utilization, The algorithm has a strong guiding significance for the actual production of the workshop.Keywords: Job Scheduling, Genetic Algorithm, MATLAB目 錄1 緒論 1 課題研究背景及意義 1 問題的提出 1 課題的現(xiàn)實與理論意義 1 國內(nèi)外研究現(xiàn)狀綜述 3 本文的研究內(nèi)容 42 車間作業(yè)調(diào)度算法 5 調(diào)度問題特點與分類 5 車間作業(yè)調(diào)度問題描述 5 調(diào)度問題優(yōu)化算法 63 求解調(diào)度問題的遺傳算法 10 遺傳算法求解調(diào)度問題的優(yōu)越性 10 遺傳算法簡介 11 遺傳算法概述 11 遺傳算法基本過程 12 遺傳算法執(zhí)行策略 154 車間作業(yè)調(diào)度的建模 17 車間作業(yè)調(diào)度問題描述 17 遺傳算法設(shè)計思想 18 編碼 18 生成初始種群 19 適應(yīng)度函數(shù) 19 選擇算子 19 交叉算子 19 變異算子 19 遺傳算法流程 195 用Matlab實現(xiàn)模擬作業(yè)調(diào)度 22 程序設(shè)計思想及偽代碼 22 分析結(jié)果的可行性、運行時間以及目標函數(shù)值 26 仿真輸出結(jié)果 26 分析結(jié)果 276 結(jié)論與展望 30參考文獻 32致 謝 34第 II 頁 共 II 頁1 緒論 課題研究背景及意義 問題的提出隨著科學技術(shù)、經(jīng)濟全球化和信息技術(shù)的迅猛發(fā)展，生產(chǎn)企業(yè)面臨著多變的商業(yè)環(huán)境［1］。實例證明，該程序算法結(jié)果較好，能充分利用設(shè)備資源組織生產(chǎn)，對于車間的實際生產(chǎn)具有較強的指導意義。作業(yè)車間調(diào)度問題是一個典型的NP—hard問題，是最困難的組合優(yōu)化問題之一。有效的車間作業(yè)調(diào)度技術(shù)，可以增強車間資源優(yōu)、化配置能力、提高企業(yè)的生產(chǎn)效率、減少生產(chǎn)損耗，使企業(yè)在經(jīng)濟全球化的競爭中處于領(lǐng)先地位。中北大學2012屆畢業(yè)設(shè)計說明書摘 要在現(xiàn)今的經(jīng)濟全球化制造時代，客戶化的產(chǎn)品需求要求更短的產(chǎn)品生命周期?，F(xiàn)代制造業(yè)的生產(chǎn)特點是品種多、批量小(甚至是單件生產(chǎn))，而車間資源的有限性制約著能否有效利用車間現(xiàn)有資源完成任務(wù)，以最快的速度響應(yīng)市場需求。本文主要研究了制造車間作業(yè)調(diào)度問題。關(guān)鍵詞：作業(yè)調(diào)度，遺傳算法，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?，F(xiàn)代科學技術(shù)的快速發(fā)展和客戶對產(chǎn)品的個性化需求越來越高，這給傳統(tǒng)制造加工業(yè)帶來了巨大的挑戰(zhàn)和機遇。制造過程中的生產(chǎn)管理與調(diào)度是保證生產(chǎn)質(zhì)量和生產(chǎn)效率的關(guān)鍵，先進的生產(chǎn)管理與調(diào)度技術(shù)能夠快速響應(yīng)顧客需求變化的多樣性。在這種生產(chǎn)模式下如何進行組織管理，包括如何組織動態(tài)聯(lián)盟、如何重構(gòu)車間和單元、如何安排生產(chǎn)計劃、如何進行調(diào)度是企業(yè)面臨的主要問題。 課題的現(xiàn)實與理論意義車間作業(yè)調(diào)度問題(JobShop Scheduling Problem，JSP)的求解目標是尋求某種最優(yōu)策略，找到的調(diào)度方案能將加工作業(yè)安排到車間制造機器上，并且使加工作業(yè)能夠最高效的完成。然而，當前的產(chǎn)品的加工工藝復雜度相當高，在調(diào)度任務(wù)規(guī)模較大且動態(tài)多變的環(huán)境中，手工調(diào)度表現(xiàn)的非常低效甚至無法實現(xiàn)調(diào)度。當前在自動化程度較高的生產(chǎn)系統(tǒng)中，使生產(chǎn)過程合理、高效運行的調(diào)度問題變得非常復雜，需要建立有效的計算機調(diào)度控制策略、因此調(diào)度問題的研究具有重要的現(xiàn)實意義。制造系統(tǒng)生產(chǎn)管理的核心就是車間生產(chǎn)調(diào)度，生產(chǎn)管理任務(wù)順利實施與完成，最終要靠合理的生產(chǎn)調(diào)度來保證。 國內(nèi)外研究現(xiàn)狀綜述車間作業(yè)調(diào)度問題是一個經(jīng)典而又傳統(tǒng)的問題，對于它的研究始于20世紀50年代。大量的研究促使車間調(diào)度領(lǐng)域取得了豐碩的成果，產(chǎn)生了很多重要的調(diào)度方法。遺傳算法的優(yōu)越性主要表現(xiàn)在搜索過程中不易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù)不連續(xù)的情況下，也能以極大的概率找到最優(yōu)解[9]。隨著遺傳算法在作業(yè)調(diào)度方面的應(yīng)用，國內(nèi)也掀起了一股應(yīng)用遺傳算法研究車間作業(yè)調(diào)度問題的熱潮。本文主要分五章，具體安排如下：第一章說明了課題的提出背景和研究意義，討論了車間調(diào)度的國內(nèi)外研究現(xiàn)狀，最后給出了本文的研究內(nèi)容和文章的結(jié)構(gòu)安排。第四章將實際的車間作業(yè)問題抽象成數(shù)學模型，并且設(shè)計遺傳算法的基本算子以及操作。車間中工件、機器、操作人員和搬運系統(tǒng)之間相互影響、相互制約。(2)動態(tài)隨機性調(diào)度中存在很多隨機性和不確定性。車間的生產(chǎn)能力不僅會受到機床的制約，還會受到工人和輔助工具的制約，各道工序的先后關(guān)系不能顛倒，如緩存容量、資源數(shù)量、工件到期時間與操作順序等也是制約因素。按照不同的分類標準，可分為6種類型:(l)開環(huán)車間和閉環(huán)車間。(5)靜態(tài)調(diào)度、動態(tài)事實調(diào)度。每一臺機器在每個時間只能加工某個工件的某道工序，只能在上道工序加工完成才能開始下一道工序的加工，前者稱為占用約束，后者稱為順序約束。切換加工的次數(shù)越多越有利于減少工件的庫存，但導致生產(chǎn)率的下降。生產(chǎn)的柔性體現(xiàn)在設(shè)備的使用和設(shè)備的安排兩個方面，設(shè)備使用的柔性是指設(shè)備可用于多個零件的多道工序加工，設(shè)備安排的柔