[發明專利]一種求解多工藝路線作業車間調度的分層優化算法

在審

• 申請號: 201610079090.7
• 申請日: 2016-02-04
• 公開（公告）號: CN106611232A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 黃超杰;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/04
• 代理公司: 暫無信息
• 代理人: 暫無信息

所屬領域

本發明涉及計算機執行制造系統領域，具體地涉及多工藝路線作業車間調度領域。

背景技術

隨著目前市場的急劇變化，制造業逐漸轉變為多品種、小批量的生產模式。作為降低生產成本并提高資源利用率的重要手段，生產調度變得尤為重要。多工藝路線作業車間調度問題考慮了生產計劃和調度過程中各個工件的多工藝路線，提高了生產過程的靈活性，優化了作業車間調度。不同于傳統的柔性作業車間調度問題主要采用單一整體模型和算法來優化，多工藝路線作業車間調度問題具有選擇工藝路線和調度優化的雙重任務，所以迫切需要一個新的優化方法來解決這個問題。目前，研究者大多采用單層算法，如整數規劃、基于規則的啟發式搜索算法和遺傳算法等，但隨著問題規模的不斷增加,建模和求解的難度不斷增大，求解的時間已不能滿足生產調度實時性的要求，效率很低。

發明內容

針對現有技術中存在的上述不足之處，根據多工藝路線作業車間調度的特征，本發明提出了一種基于目標級聯法(Analytical Target Cascading，ATC)的分層優化模型及其相應算法。通過多層協調優化和制造單元聚類，結合改進的遺傳算法搜索全局最優解，該方法可以實現在大型車間多單元協同調度，具有靈活的工藝路線、復雜度低和效率高等特點。

本發明的目的則是克服現有技術中存在的：選擇工藝路線復雜度高；隨著問題規模的擴大，建模和求解的難度不斷增大，且搜索時間顯著提高；搜索空間容易陷入局部最優的問題。

本發明為實現上述目的所采用的技術方案是：一種求解多工藝路線作業車間

調度的分層優化算法，該方法的實施步驟如下：

步驟1：初始化算法參數集，包括各層的允許誤差值：ε₀、ε₁、ε₂，反饋給上層的響應值：迭代次數CN及進化代數VN；

步驟2：在工藝規劃層，根據工件的多工藝設置路線選擇變量x₀₁；

步驟3：在單元規劃層，應用因子分析法構造虛擬制造單元及工件到制造單元的初始分布，組成動態工件族，通過基因譜描述其過程；

步驟4：在工件調度層，在各制造單元和工件族上，隨機生成N個個體作為初始種群，應用擇優選擇、POX交叉、交換變異，以盡早加工為準則對各基因進行解碼，計算其適應值，最終獲得每個制造單元的最優調度方案；

步驟5：反饋各制造單元的完工時間給單元規劃層，并計算反應偏差和全局目標值。如果偏差小于允許誤差，發送單元規劃層的響應值給工藝規劃層，使其判斷迭代次數是否超過CN，如果是則轉步驟6，否則更新所有工藝路線，進行下一次優化；如果偏差超過允許誤差，在制造單元對基因譜執行標準交叉算子然后轉步驟4；

步驟6：輸出保留最小總目標值的最優結果，優化結束。

本發明的有益效果是：

1、分層優化，模型簡單。隨著問題規模的擴大，求解的難度增加不大；

2、結合遺傳算法的交叉、變異算子，增加了基因的多樣性，提高了尋找最優解的概率；

3、工件到制造單元的聚類分布越合理，收斂速度越快，調度方案越優。

4、快速收斂，顯著減少了搜索與求解時間。

附圖說明

圖1表示該分層優化算法流程圖

圖2表示ATC模型中元素P_ij的優化示例圖。

圖3表示分層優化模型示例圖。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，以下，結合附圖對本發明進行詳細說明。

多工藝路線作業車間調度是一個考慮每個工件多條工藝路線的生產組織形式，包括工藝規劃和作業車間調度的雙重優化任務，旨在一些約束條件下確定每個工件的工藝路線和安排每臺機器上的工序順序，使調度結果最優。多工藝路線作業車間調度描述如下：n個工件J_i(i＝1，2，...，n)組成的工件集J；m臺機器M_j(j＝1，2，...，m)組成的機器集M；工件J_i有p_i條可選工藝路線；路線k上有s_ik個工序；每個工序O_ikl可以在若干機器上加工(i＝1，2，...，n；k＝1，2，...，p_i；l＝ 1，2，...，s_ik)。存在以下假設：

(1)一個工序在一臺確定的機器上開始加工就不能中斷直至完成；

(2)一臺機器在同一時刻只能加工一個工序；