基于混合蟻群算法的多模式下模具車間調度系統研究

2014-10-07 14:57:34 大云網　點擊量：評論 (0)

摘　要：針對多模式下模具車間調度問題，設計了一種混合蟻群算法進行求解。最后在企業信息系統的基礎上，基于該算法模塊設計了模具車間調度系統的框架。關鍵詞：多模式　調度系統　模具車間　蟻群算法模具制

摘　要：針對多模式下模具車間調度問題，設計了一種混合蟻群算法進行求解。最后在企業信息系統的基礎上，基于該算法模塊設計了模具車間調度系統的框架。

關鍵詞：多模式　調度系統　模具車間　蟻群算法

模具制造企業屬于離散制造行業，客戶訂單隨機下達，并且模具的工序復雜，返修現象隨機出現，使得模具車間調度問題越來越復雜，人工制定作業計劃變得越來越困難，亟需一套適用的模具車間調度系統來解決該類問題。模具車間是典型的柔性作業車間，而柔性作業車間調度問題是比經典作業調度問題更復雜的NP-hard 問題[1]。目前，針對該類調度問題，已經提出了很多求解算法。Pezzella等人[2]采用多種交叉方法和多種變異方法相混合的遺傳算法對該調度問題進行了求解，取得了較好的優化結果；ZHANG等人[3]設計了一種混合粒子群算法。本文為求解多模式下的模具車間調度問題，設計一種混合蟻群算法。最后，在企業應用系統的基礎上嵌入該算法模塊，設計了模具車間調度系統的框架結構和總體流程。

1　多模式下模具車間調度問題描述

　　模具車間通常是生產模具產品的某一類零件，車間由若干個加工中心組成，每個加工中心包含若干臺同等并行機。每一個模具零件需要經過多個加工工序，并且零件的加工順序是預先確定的。根據零件所屬產品類型和加工精度要求的不同，每道工序可以由若干個（一個或者多個）加工中心加工。當選擇不同的加工中心，所需要的加工時間也不相同。

　　該類車間是一類典型的柔性作業車間，在實際生產過程中，采用并行加工的思想，首先將大的模具零件分割成若干個小工件，然后并行加工，最后再組裝，以縮短零件的加工周期。當零件的某個工序選定了加工中心之后，配置不同數量的機器時，整個零件的加工時間是不同的。圖1表示某一類模具零件分割成3個工件加工，單個工件在某加工中心的加工工時為T，該加工中心包括3臺同等并行機，則該類情況下模具零件具有3種加工模式可選。當為零件分別配置1、2、3臺機器時，模具零件的加工時間分別為3T、2T和T，稱該類現象為多模式現象。為了更加準確地制定生產作業計劃，就不得不考慮此類問題。

2　混合蟻群算法設計

2.1　利用蟻群算法配置模具零件的加工中心和加工模式

2.1.1　結點構造過程

　　模具零件首先需要配置加工中心和加工模式，可以把問題描述為如圖2所示的有向結點圖。圖中的每一行對應模具零件的每道加工工序，而每一列對應加工中心。O0表示起始結點，Oij表示第i個零件的第j道工序，Oijk表示第i個零件的第j道工序選擇了加工中心Wk。圖中的橢圓表示工序可以配置的加工中心，橢圓內的圓圈表示相應工序可以配置的加工模式，都是螞蟻需要爬離的障礙物。圖中的黑圓球和黑實線表示螞蟻選擇了相應的加工中心和加工模式。

2.1.2　結點選擇規則

虛擬起始結點為所有螞蟻的出發點，當模具零件的某個工序選擇了相應的加工中心之后，需要再為該工序選擇一種加工模式，的選取按照以下規則進行：

(1)

式（1）中，表示結點在時刻的信息素濃度，表示期望程度。為隨機數，以參數確定蟻群在決策時對知識探索與利用的權重。在搜索的過程中，螞蟻以概率選擇值最大的加工模式，并且又讓螞蟻以的概率來探索其它路徑，其它路徑的選擇概率可以設置為公式（2）：

(2)

2.1.3　更新信息素濃度的規則

　　在算法更新信息素濃度的過程中，文獻[4]設計了一種只對歷史最優解進行獎勵的精英策略，文獻[5]設計了一個動態蟻群種子集。本文將采用雙向收斂策略，設定當前算法迭代中最好個解的螞蟻和最差個解的螞蟻分別構成螞蟻種子集和。在更新信息素濃度的時候，集合中的所有螞蟻都有權利強化其爬行路徑上的結點信息素濃度，而集合中的所有螞蟻將弱化其爬行路徑上的結點信息素濃度，更新規則分別為公式(3)和公式(4)：

(3) (4)

　　其中，初始化信息素濃度設定為1；為信息素揮發系數，D為常數；則通過完整的調度結果來獲得。

2.2　利用優先級配置模具零件的加工順序

　　在利用蟻群算法配置了每一道工序的加工中心和加工模式之后，下一步則需要配置模具零件在相應加工中心的加工順序。

　　在模具生產車間的相應加工中心中，決定模具零件加工順序的因素主要包括模具零件的重要系數和模具零件所屬客戶訂單的重要系數。因此，本文對模具零件的優先級將采用向量來表示，該向量的優先級決定了加工中心中模具零件的加工順序。在優先級向量中，表示模具零件的重要度系數，關鍵模具零件的重要度系數高于非關鍵模具零件的重要度系數；為模具零件的交貨緊急程度系數，零件的交貨期越靠前，該系數越高；表示模具零件所屬訂單的重要度系數，包括產品類型、客戶重要度和訂單總額，令。根據優先級向量可確定模具零件加工順序的具體步驟：第一，對按照遞減排列；第二，若相同，則對遞減排列；第三，若仍然相同，則對遞減排列；第四，如果三個優先級相等，則隨機排列。

3　系統總體框架設計

某模具企業已經運行了一套ERP系統，該ERP系統可以提供的數據為：零件數據，主要包括模具的所有零件、新零件到達信息、零件交貨期更改信息和緊急零件插入信息；車間設備數據，包括車間所有加工設備的負荷信息和設備狀態信息；工件加工數據信息，包括工件的加工狀態（正在加工、未加工）；零件工藝數據，主要包括零件的工序信息、零件清單信息。以該ERP系統所提供的這部分數據作為數據源，以混合蟻群算法模塊作為求解算法，建立了基于混合蟻群算法模塊的多模式下模具車間調度系統框架如圖3所示。該系統將充分調用ERP系統中的零件投放模塊數據、車間反饋模塊數據和工藝管理模塊數據，利用混合蟻群算法模塊進行運算，生成新的車間調度計劃。

為了使系統生成的車間作業計劃能夠順利執行并且實時滾動更新，通過對應用企業的業務流程分析，設計了模具車間調度系統的總體流程如圖4所示。該流程主要包括零件加工資源配置、調度參數調整和調度結果顯示三部分內容。

車間任務池中存放著到達的正常訂單和緊急訂單，對于任務池中的所有零件，系統將基于零件所屬產品類型，根據資源配置模板自動配置加工資源信息，包括工藝路線、可選加工中心和可選加工模式。配置完成以上信息之后，系統將利用混合蟻群算法模塊基于車間現有負荷來排產。若對排產的結果不滿意，可以調整相應系統參數，然后再重新觸發系統運行。允許調整的參數主要有零件優先級、零件的資源配置數據、部分零件作業計劃以及占用加工資源的凍結、蟻群算法涉及的參數和加工中心的計劃負荷。完成排產之后，系統以甘特圖顯示各零件的作業計劃，利用柱狀圖顯示車間各加工中心的負荷信息。對于系統排產的觸發機制，設計了人為觸發和定時觸發兩種方式。