組合規則啟發式算法在模具加工作業調度中的應用研究

摘要：由于現行的優化算法在解決模具車間調度問題上存在局限性，目前大部分模具車間由人工編制車間作業計劃，導致生產效率較低、物料供應不能同步化等問題。為此，介紹了采用基于組合規則的啟發式算法，選擇加工時間最短和最小等待時間等規則，解決了現行的優化調度算法在車間調度問題中所遇到的難點。經實例驗證獲得了較為理想的結果。

關鍵詞:作業車間調度; 組合規則； 啟發式算法

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2007)11-0185-03

模具生產一般是根據客戶訂貨合同組織生產，屬于單件的訂貨生產類型。企業目前在模具生產管理中存在很多問題：由于同時制造的模具較多且要求各不相同，在生產工藝信息不完全或不準確的情況下，由人工編制車間作業計劃將是非常困難的。目前企業針對各套模具只制訂粗略的階段性計劃，以及關鍵零件的進度計劃。這樣顯然不能滿足生產需求，也無法保證物料的同步化。由于作業車間調度是制造中最基本、最重要的問題之一，對制造過程具有重要的實際意義，學者們對其進行了廣泛的研究，提出了許多種方法來解決作業車間調度問題。求解作業車間調度問題的方法主要有優先分配啟發式方法、隨機分配啟發式方法、瓶頸移動啟發式方法、分支定界法、人工神經網絡、模擬退火、禁忌搜索、遺傳算法、蟻群優化算法、效率調度算法和約束分析法等。由于作業車間調度問題是一個非常難解的組合優化問題，盡管已有幾十年的研究歷史，也提出過許多最優化求解算法，但至今尚未形成系統的理論與方法。多數算法由于計算復雜，只適用于規模較小的作業車間調度問題。為了滿足企業的正常生產需要，車間必須合理地安排各個零件的加工順序，保證各零件在最短的時間內加工完成，從而提高企業的生產效率。如何準確地安排各工序的加工就是提高車間生產效率的關鍵。本文提出了將加工時間最短和最小等待時間等規則組合應用以解決模具車間調度問題，并用Java編程實現。

1模具車間作業調度的調度模型

1．1調度問題描述

N個工件要在M臺設備上進行加工，工件的工藝路線是預先給定的，調度的目標是確定每臺設備上不同工序的加工順序，使得某項性能指標最優。該調度問題應當滿足以下幾點約束：

工件必須按其工藝路線加工，后道工序必須在前道工序完成后方可開始;

不同工件的工序之間沒有先后約束;

一臺設備不能同時加工兩個工件;

工件裝卸時間及刀具調整時間統一被考慮到等待時間內。

相比傳統的job shop調度問題，本文所研究的調度問題更接近車間實際生產。對于某道工序，存在一個設備集合，集合中的任意一臺設備都能對其進行加工。在解決此類調度問題時，不僅要考慮多道工序競爭一臺設備時的工件排序問題，同時還要考慮一道工序可在多臺設備上加工時的設備選擇問題以及工廠日歷。顯然，這增加了求解的難度。但是在放寬約束的情況下，調度的結果更能滿足車間生產的實際需要，為車間生產提供更有效的指導，要求總加工時間最小。

1．2模具車間作業問題的數學模型

1）調度問題的變量描述

4結束語

本文分析了模具車間的生產特點，提出了一種基于最短加工時間和最小等待時間等組合規則的調度算法。本文實現了當工件的每道工序可在一臺或多臺設備上進行加工時，如何挑選機器的問題；同時考慮了不同工序的加工沖突和不同設備的資源分配問題。本算法在傳統的job shop調度問題的基礎上，放寬了資源約束條件，更符合大多數企業的實際生產情況，具有實際使用價值。調度實例表明，該方法能有效滿足模具車間生產的實際需要。

參考文獻:

[1]玄光男，程潤偉 .遺傳算法與工程優化［Ｍ］. 北京：清華大學出版社，2004.

[2]張良揚.單件小批生產模式下的計劃系統與優化算法研究[D].南京：南京航空航天大學， 2004：80-100.

[3]許文硯.基于單件小批生產模式的車間調度方法研究和系統開發[D].南京：南京航空航天大學， 2005:40-100.

[4]王凌. 混合優化策略和神經網絡中若干問題的研究[D]. 北京: 清華大學， 1999:50-100.

[5]潘全科.一類解決作業車間調度問題的遺傳退火算法job－shop調度問題[J]. 自然科學報， 2005，20(5):10-20.

[6]何霆.車間生產調度問題研究[J].機械工程學報，2000，36(5):97-103.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”