摘要：針對模具生產典型的離散生產過程，對模具生產的工藝過程和工件的特徵進行了研究。結合企業的生產特點，從通用類模具生產例項入手，建立了生產單元分配方法，利用遺傳演算法的強魯棒性，提出了一種實用的生產排程演算法，並進行了詳細的演算法設計與計算。
關鍵詞：遺傳演算法；模具；車間作業排程
the design of mould enterprise』s job-shop scheduling algorithm based on genetic algorithms
abstract：mold processing is a typical discrete manufacturing process, the ***** analyzes the technological process of mold processing and the characteristics of workpiece. in addition, consider the production characteristics of enterprise, the ***** take the general kind of mold』s processing for example，established the production unit allocation method，utilizes the robustness of genetic algorithms，proposed the idea of job-shop scheduling algorithm，give the detailed design and calculation.
key words: genetic algorithms；mould；job-shop scheduling algorithm
1 引言
模具製造具有單件生產、面向訂單、離散型、多衝突和動態多變等製造特性[1]，其設計製造過程依賴較強的經驗性，生產任務存在時間上的不均衡性，生產過程經常受到訂單和返工返修的干擾，具有較強的被動性和滯後性。因此，相對於一般的離散型機械加工，模具企業車間作業排程問題更加複雜，意義更加重要，作業排程的效果直接影響模具的生產質量和交貨期,從而影響模具企業的信譽和經濟效益。
目前，在車間作業排程問題的研究方面，尚未形成一套系統理論能夠有效地解決各種作業排程。許多學者根據特定的生產製造系統提出了不同的排程演算法：kudva等（1994）在考慮訂單優先順序和減少切換成本的情況下，採用啟發式方法對具有有限中間儲存的多產品批處理和半連續企業產生排程方案[2]。
harjunkoski和grossmann（2001）提出了使用數學規劃方法的分解策略解決大型排程問題[3]。kim等提出了一種改進的遺傳演算法來得到批處理排程的生產順序和生產路徑[4,5]。
遺傳演算法是借鑑生物界自然選擇和自然遺傳機制的隨機搜尋演算法，其全域性搜尋能力強，適合在較大規模的解空間中尋求全域性最優解。另一方面，利用遺傳演算法的隱式並行性和強魯棒性等優點，可充分減少問題的求解時間，求解效率高，非常適合應用於車間作業排程這類典型的組合優化問題。
2 模具企業車間作業排程問題
2.1 車間作業排程問題描述
車間作業排程問題（job-shop scheduling problem，jsp）是一類滿足任務配置和順序約束要求的資源分配問題，資源和任務分別是一些機器和作業。作業可由若干稱為工序的子任務組成，每個任務中的各工序在機器上加工的優先順序和所需時間是已知的。排程就是把工序分配給機器上某個時間段，問題的目標是使得加工所有工件的完成時間最短。
一般需要考慮以下幾方面：①加工機器總數；②加工工件總數以及工件需要加工的工序數；③工件的工藝路線（工序）及每道工序的加工時間；④工件加工的優先權和交付期。
由於標準件可以購買，模具加工通常只加工型腔，電極，模板三類零件。在操作上，這些零件的每道工序分成3個部分：準備、加工和運輸，且工具機準備時間和運輸時間之和遠大於零件的加工時間，零件的加工時間通常只佔總生產週期的6%左右。
jsp問題已被證明是屬於np（non-polynomial complete problems）難題，被公認為是最困難的組合優化問題之一。此外，由於模具自身的複雜多樣性，對模具加工製造過程的排程相對於一般的jsp問題難度更大。文章在研究中加入了如下假設：
（1）所有機器均同時開工，且工件從機器i到機器j的運輸及準備過程的時間併入加工時間；
（2）數量多於1個的工件直到加工完畢才進行轉移且同一機器上同種工件切換時間
不計；（3）操作允許等待，即前一操作未完成，則後面的操作需要等待，可用資源有限；
（4）假設所有資源和工序在生產過程中一切正常，不考慮偶然事故發生。
（5）不考慮並行機和多功能工具機的柔性作業車間排程。
2.2 模具企業車間作業排程數學模型
根據以上對排程問題的描述及假設，模具企業車間作業排程數學模型建立如下：
（1）工件集，為第i個工件（i=1,2,…,n）。
（2）機器集，為第j個工件（j=1,2,…,m）。
（3）工序序列集，為工件的工序序列。
（4）表示第i個工件的第k個工序在第q臺機器上加工的工序，其開始加工時間和需要加工的時數分別記為和。
而且問題滿足下列條件：
（1）各工件必須按工藝路線以指定的次序在機器上加工多次；
（2）任何工件沒有搶先加工的優先權，服從任何生產順序；
（3）每件產品必須按規定工序加工，不得顛倒；
（4）每台機器在同一時間只能擔任一項任務（每件產品的每個工序為乙個任務）；
（5）工件加工過程中沒有新工件的加入，也不臨時取消工件的加工。
採用整數線性規劃模型描述為：1）
（2）其中，式1表示工序順序約束，同一工件的不同工序不能同時加工；式2表示資源約束，每台機器同一時刻只能加工乙個工件。優化目標為：尋找最優排程方案，使全部工件的最大完工時間最短，即
其中，表示最後乙個工件i的完工時間。
3 遺傳演算法求解job-shop排程問題
3.1 生產例項
以某模具企業作業車間為例，該車間擁有車床、鑽床、刨床、鏜床、銑床、剪床、滾床7臺機器。在一次生產任務中，需要為轎車尾燈的一套注塑模具加工不同型別的9種工件，各工件數量不同，並且具有不同的加工工藝過程。各工件的加工數量和工藝資訊如表1所示，其中，工件各工序所用時間用括號中資料表明，單位為分鐘（min）。
表1 工件加工工藝資訊與生產數量
根據車間加工工具機的位置安放情況，確定工具機之間的運輸時間如表2所示，單位為分鐘（min）。
表2 工具機之間的運輸時間
根據經驗積累，總結出各工具機換刀，對刀等平均調整時間如表3所示，其中，各工具機後數字表示裝置編號，調整時間單位為分鐘（min）。
表3 工具機的平均調整時間
3.2 技術約束條件確定
這是乙個9工件7機器的離散車間生產排程問題。將不同數量的同一工件確定為乙個生產單元，對生產單元進行排程。該生產單元的加工工序與單個工件的工序一致，各工序的加工時間=工件數量*單個工件加工工序時間+機器運輸時間+工具機準備時間。
確定問題的機器順序陣mm和時間加工陣tm如下 ：
mm = tm =
機器順序陣中每一行表示對應工件的加工工序機器資訊，時間加工陣中每一行表示對應工件的加工工序時間資訊。如工件1的3工序分別在機器1、2、5上加工，各工序加工時間分別為128、161、47。
對問題編碼時，染色體的長度就是根據加工工序的總數確定的。根據以上資料資訊，確定工件的淨加工時間及工序數量如表4所示，時間單位為分鐘（min）。
表4 工件加工單元時間及工序數量
可以得出染色體長度為24，全部加工完工時間不超過3456分鐘。
3.3 編碼方案與適應度函式設計
（1）編碼方法
採用基於工序的編碼方法[6]，將排程編碼為工序的序列，每個基因代表一道工序。給所有同一工件的工序指定相同的符號，然後根據它們在染色體**現的順序加以解釋。
設染色體k=[454834691481257824138454]，每個基因不表明乙個具體的工序，而是指有上下依賴關係的工序，其中1表示工件1，2表示工件2，以此類推。在染色體k中，出現7個4表示工件4的7道工序，第乙個4表示工件4的第一道工序應該在車床上進行操作，第二個4表示工件4的第二道工序應該在鏜床上操作。每個工件在染色體**現的次數等於其對應的工序數。
可以確定染色體的任意排列總能夠產生可行排程。
基於遺傳演算法的高速列車執行多目標優化
摘要 隨著我國高速鐵路的迅速發展，人們不僅要求列車安全 正點 執行過程舒適的同時，能耗和執行時間達到鐵路運營部門和旅客都可以接受的程度。同時也對列車的低能耗和舒適性提出了更高的要求。針對這一情況，本文將遺傳演算法運用於列控系統中對高速列車的執行過程進行優化。通過研究列車的運動方程和約束條件，對列車的...
用C 實現遺傳演算法
本程式試用遺傳演算法來解決rosenbrock函式的全域性最大值計算問題 max f x1,x2 100 x1 2 x2 2 1 x1 2 2.048 xi 2.048i 1,2 include include include include using namespace std const in...
遺傳演算法原理及應用
07計本張雷 070701010116 遺傳演算法是由美國的j.holland教授於1975年在他的專著 自然界和人工系統的適應性 中首先提出的，它是一類借鑑生物界自然選擇和自然遺傳機制的隨機化搜尋演算法 遺傳演算法模擬自然選擇和自然遺傳過程中發生的繁殖 交叉和基因突變現象，在每次迭代中都保留一組候...