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

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

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

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

    通過AHP層次分析法得出最大完工時(shí)間以及拖期時(shí)間的權(quán)重分別為0.68與0.32。經(jīng)計(jì)算機(jī)運(yùn)算分析可知，目標(biāo)函數(shù)為100.64；這批零件的最大完工時(shí)間至少為148，并且沒有發(fā)生零件生產(chǎn)周期延誤。通過該程序與傳統(tǒng)遺傳算法進(jìn)行比較，本文算法能夠在較短的時(shí)間內(nèi)找到比較滿意的解。
    本文在分析平行機(jī)調(diào)度問題的基礎(chǔ)上，建立了符合實(shí)際情況的調(diào)度模型。該模型加入了模具換模時(shí)間，且換模時(shí)間存在序依賴，以拖期時(shí)間最小化和生產(chǎn)時(shí)間最小化為目標(biāo)，使得該模型具有更高的實(shí)用價(jià)值。針對(duì)經(jīng)典遺傳算法進(jìn)行了分析，改進(jìn)了遺傳算法的交叉和變異概率，并通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。但對(duì)于受資源約束的調(diào)度問題，還有待進(jìn)一步研究。
參考文獻(xiàn)
[1] 何鶯，蔡鴻明. 基于需求優(yōu)先的多目標(biāo)柔性車間調(diào)度研究[J]. 微型電腦應(yīng)用，2002，7(5): 1-3.
[2] 孫志峻，喬冰，潘奎科,等. 具有柔性加工路徑作業(yè)車間批量調(diào)度優(yōu)化研究[J]. 機(jī)械科學(xué)與技術(shù),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ī)器多目標(biāo)調(diào)度問題的遺傳算法[J].系統(tǒng)工程理論與實(shí)踐, 2005,25(9):58-62.
[5] 閆楊，趙傳立. 安裝時(shí)間受資源約束的單機(jī)成組調(diào)度問題[J].電機(jī)與控制學(xué)報(bào)，2007,11(1):70-73.
[6] 李平,顧幸生.不確定條件下不同交貨期窗口的Job Shop調(diào)度[J].管理科學(xué)學(xué)報(bào)，2007,7(2)：22-26.