摘 要： 在工廠實際生產中，模具的換模時間在生產調度中不可忽略。為了更合理地研究平行機車間調度問題，本文將存在序依賴的換模時間考慮進調度模型之中，同時以最小完工時間和最小拖期時間為目標，在經典遺傳算法的基礎上，對算法選擇算子以及交叉變異概率進行改進，避免早熟現象的發生。通過計算結果的比較，證明本文中調度模型更符合實際生產情況，改進后的算法能夠得出更高質量的解，且求解效率更高。
關鍵詞： 換模時間； 平行機調度； 改進的遺傳算法

    對生產過程進行作業計劃時，生產調度作為一個關鍵模塊，是整個先進生產制造系統實現管理技術、運籌技術、優化技術、自動化與計算機技術發展的核心。調度的任務是根據生產目標和約束，為每個加工對象確定具體的加工路徑、時間、機器。一般調度以最小完成時間和最少拖期懲罰等為目標。目前生產調度問題的研究很多，何鶯等[1]提出了以工件提前/拖期懲罰代價最小、生產周期最小為目標的多目標優化調度算法，可得到滿意的較優解；孫志峻等[2]提出了針對批量生產的柔性作業車間調度方案；Runwei等[3] 研究了遺傳算法在作業車間調度問題中的應用;參考文獻[4]討論了雙目標下，帶一種資源約束的工件成型類別的并行機調度問題。參考文獻[5]討論了安裝時間受資源約束的單機成組調度問題。參考文獻[6]則討論了不確定條件下不同交貨期窗口的Job Shop調度。
    本文所針對的是帶有模具換模時間的平行機調度問題。單機調度指的是所有工件均需在指定的單臺機器上加工完成，即單機排序問題；平行機調度指的是能夠完成某種功能的機器不止一臺，即平行機排序問題。模具是用來成型物品的工具,它主要通過所成型材料物理狀態的改變來實現物品外形的加工。使用不同種類模具的工件之間需更換模具，在此之間需要消耗換模時間，換模時間存在序依賴。每個工件有交貨期和加工時間，其加工時間預先確定,其生產時間為前一個工件的結束時間。這類問題的一個典型應用是模注加工，如注塑車間,塑料件由注塑機加工而成,每個塑料件的加工都必須有一種模具裝設在注塑機臺上,經過一段成型周期加工而成，不同元件的加工中間需更換模具,并需一定的工時。
1 平行機調度問題建模
    調度問題的實質是安排最優的作業加工順序，讓機器的空閑度最低，換模時間最省，實現機器使用最大化，并且使各產品的拖期時間最少，工件最大完工時間最短。該平行機問題可描述為:給定m臺相同的機器，待加工工件為n個，每一個工件只需要加工一道工序，每一個工件在加工均要使用模具，按照工件使用模具的種類不同可分為g類。
    問題假設如下：(1)每臺設備同一時刻只能加工一個工件；(2)每個工件只有一道工序； (3)加工時間預先確定，且工件的安裝、卸載時間忽略不計或者認為被包含在所給加工時間內;(4)模具的安裝需要安裝時間，模具更換需要換模時間(安裝時間包括在內),時間預先確定；(5)所有機器在t=0時刻都可用;(6)所有工件在t=0時刻都可被加工。(7)模具使用時間能滿足生產需求。
 

2.2 初始種群的產生
    初始種群的大小和優劣對算法的執行效果有明顯的影響?？紤]到搜索效率和質量，為防止產生非法解,在初始化種群時,采取如下的初始化方法：先隨機產生?漬個(種群尺寸)n維向量(ji)分別作為初始種群?漬個個體的第一行，其中ji為互不相同的自然數；依照此辦法隨機生成每個個體的第二行向量。
2.3 目標函數評價
    目標函數即適應度的計算，由于上述問題是一個多目標問題，目標為完工時間最小化和拖期時間最小化，在不同的生產環境要求的目標不一樣。因此，本文通過權重、線性組合的方式將多目標轉化成單目標問題。
    Z=βz1+γz2 　　　　　　　　　　　　　　 (5)
式中，β、γ分別為總完工時間和最大拖期時間的權重系數。通過AHP層次分析法來確定這些指標項的權重系數的大小，將多目標問題轉化成單目標問題。
2.4 遺傳算子

    遺傳算子主要由選擇、交叉、變異三種構成，針對文中問題具體設計主要內容如下：
    (1)選擇
    傳統的選擇操作容易造成在進化初期,有可能適應度很高的個體被選擇的概率很大, 從而復制出很多后代,因個體單一而無法繼續進化使搜索陷入局部最優；并且在進化后期,當各個個體的適應度差距不大時,該方法已經不再具有選擇能力,體現不出個體的優劣。本文選用如下方法，將群體中的所有個體按照適應度從大到小進行排列,排在最前面1/4的個體復制兩份,中間的2/4復制一份,最后面的1/4拋棄。用此方法來進行選擇,可以將適應度比較低的個體直接淘汰掉,并且增加了適應度較好的個體的數目,從而在一定程度上解決了上述問題。
    (2)交叉
    交叉操作用于組合出新的個體，在解空間中進行有效搜索，同時降低對有效模式的破壞概率。在此將兩個父代個體中的一個個體作為參照，對另一個個體中的位置進行重組，然后與其實現一個循環鏈，并將對應位置的基因填入相應的位置，循環組成后再將另一個個體各位置的基因填入相同的位置。
 
3 計算實例與結果
    根據上述建模思想和算法進行算例分析。例：該生產任務包括50個工件，工件按照使用模具種類的不同分為8組，有6臺機器可用于加工，工件的加工時間如表1所示，工件交貨期以及模具的安裝時間和換模時間已知。為了驗證算法的有效性,本文算法通過Visual C++編程實現。算法主要參數假設如下：種群個數20，變異率和交叉概率由程序中自適應得出，循環迭代次數為50。

    通過AHP層次分析法得出最大完工時間以及拖期時間的權重分別為0.68與0.32。經計算機運算分析可知，目標函數為100.64；這批零件的最大完工時間至少為148，并且沒有發生零件生產周期延誤。通過該程序與傳統遺傳算法進行比較，本文算法能夠在較短的時間內找到比較滿意的解。
    本文在分析平行機調度問題的基礎上，建立了符合實際情況的調度模型。該模型加入了模具換模時間，且換模時間存在序依賴，以拖期時間最小化和生產時間最小化為目標，使得該模型具有更高的實用價值。針對經典遺傳算法進行了分析，改進了遺傳算法的交叉和變異概率，并通過仿真實驗驗證了算法的有效性。但對于受資源約束的調度問題，還有待進一步研究。
參考文獻
[1] 何鶯，蔡鴻明. 基于需求優先的多目標柔性車間調度研究[J]. 微型電腦應用，2002，7(5): 1-3.
[2] 孫志峻，喬冰，潘奎科,等. 具有柔性加工路徑作業車間批量調度優化研究[J]. 機械科學與技術,2002，3(4):348-350.
[3] Cheng Runwei, GEN M, TSUJIMURA Y. A tutorial survey of Job-Shop scheduling problems using genetic algorithms partⅡ: hybrid genetic search strategies[J]. Computers and Industrial Engineering, 1999,36(2):343-364.
[4] 曾相戈,韓伯棠. 一種求解帶資源約束的并行機器多目標調度問題的遺傳算法[J].系統工程理論與實踐, 2005,25(9):58-62.
[5] 閆楊，趙傳立. 安裝時間受資源約束的單機成組調度問題[J].電機與控制學報，2007,11(1):70-73.
[6] 李平,顧幸生.不確定條件下不同交貨期窗口的Job Shop調度[J].管理科學學報，2007,7(2)：22-26.