基于多目標多約束條件下排產算法設計與應用＊

羅小峰 胡 瑩 余 翔

（①南昌大學機電工程學院，江西 南昌 330031；②中國聯合網絡通信有限公司江西省分公司，江西 南昌 330006）

隨著網絡信息化的發展，MES 系統逐步進入生產車間。生產規模擴大，對實際生產適應度要求變高。離散型的車間調度[1]問題，多品種小批量的生產需求，多目標、多約束[2]條件的實際場景，讓求解過程愈加復雜。

國內外學者對排程問題進行了深入研究與分析。目前用于解決該類問題的方法有量子遺傳算法、粒子群優化算法和人工蜂群算法等[3-5]。LI S Y 等[4]提出了一種粒子群優化算法，專注于收斂性的速度和質量；Kamal A M 等[6]總結前人研究成果，為后人的研究提供了參數指導和研究方向；針對收斂速度慢問題，Mohit A 等[7]在粒子群算法的基礎上結合遺傳算法提出了新穎的元啟發式技術；王玉芳等[8]將遺傳算法與模擬退火算法結合，提升算法尋優能力；為保留父代優良特征，張超勇等[9]提出新的POX 交叉算子，荊巍巍等[10]對于多目標調度問題提出自適應NSGA-II 算法，并通過實例證明了算法有效性。以上研究提出了許多算法模型，算法之間的結合方便了問題的求解。由于APS 本身適用性不強，目前在實際生產中的應用并不理想，因此本文基于某機加車間的實際生產情況，提出了基于傳統遺傳算法，解決多目標、多約束條件生產排程問題的改進遺傳算法，建立相關排產模型并求解，提高生產排程效率。

1 問題描述與建模

1.1 問題描述

APS(advanced scheduling)排程是一種基于有限產能的特殊排序方式，即在某一段時間將工序、設備和人員分配到對應時間節點上，最終達到高效有序生產的目的。

訂單是整個生產車間的核心，根據生產需求分析后可以得出生產任務。設備之間存在產能差異，產品可能存在多工藝路線，還存在雙工位情況，即一臺機床，可以同時加工兩道工序。

企業生產效率要提高，關鍵在于降成本、降廢品率，提高設備利用率，減少設備空閑時間。排程中所涉及的要素如表1 所示。

表1 機加排程問題信息

1.2 約束條件

（1）設備存在雙工位交替的情況，即同一設備、兩個工位，同時作業。

（2）單個零件加工時間只受設備生產節拍影響，即設備的產能一定。

（3）如設備中途出現故障，更換設備的時間忽略不計。

（4）相鄰設備優先派工，根據設備的派工優先級進行派工。

（5）同一種零件優先安排在同一臺設備上進行加工。

（6）工序委外需等該工序完成后才能開始下一道序。

（7）交期靠前的訂單優先安排生產。

約束條件的多元性，決定了算法設計的復雜度，其中雙工位需考慮交替加工情況，保證工序不發生混亂。相鄰設備在空閑時考慮優先派工，縮短物料運送時間，設備的派工優先級還需根據使用頻次動態調整，提升設備使用率。

1.3 目標函數

（1）按時交貨因子，保證在交貨期之前完成訂單。

（2）48 h 達成率因子，即相鄰兩序之間加工間隔時長不超過48 h。

（3）設備連續性影響因子，盡可能縮短設備待機時間，提高設備使用的連續性。

（4）最短完工時間影響因子，即盡早完成生產任務。

以上的生產排程目標，涉及到眾多影響因素，彼此間存在矛盾關系，往往難以兼顧所有，需均衡各方面要素。

1.4 數學模型

根據以上問題的描述與分析，本文采用加權組合優化法，建立如下目標函數模型：

其中：C(T)為工序結束時間，Ma(T)為工序結束最晚時間，Mi(T)為工序結束最早時間。C(Q)為按時交貨數量，Ma(Q)為按時交貨的最大數量，Mi(Q)為按時交貨的最小數量。C(E)為連續設備數量，Ma(E)為連續設備的最大數量，Mi(E)為連續設備的最小數量。C(R)為48 h 達成率數量，Ma(R)為48 h 達成率最大數量，Mi(R)為48 h 達成率最小數量，以上時間都按分鐘計算，F為是否完成比率，I為是否按時完成比率，A為是否達成比率。

式中：S1為最短完工時間影響因子；S2為按時交貨影響因子；S3為48 h 達成率影響因子；S4為設備連續性影響因子；W1為最短完工時間影響因子權重；W2為按時交貨影響因子權重；W3為48 h 達成率影響因子權重；W4為設備連續性影響因子權重。

2 算法設計與優化

2.1 算法設計

運用遺傳算法的思想，將實際生產與理論相結合，更好地解決實際問題。將眾多排產方案看作一個種群，一個排產方案對應一條染色體，工序對應基因，考慮到實際生產中還有設備元素和雙工位的情況，引入分子和裂變分子的概念，一臺設備對應一個分子，如果是雙工位，則存在裂變分子。

2.1.1 編碼

合適的編碼方式使得算法求解變容易。機加生產中的排程問題，首先確定加工路線，之后是設備分配，最后是人員排班。

通過分析，采用三段式排程編碼方案，第一段為工序分配，即確定工序的總時長、開始時間和結束時間，計算公式如下：

其中：Ri為第i道序的節拍，Li為加工的數量，Si為加工時長，Tie為結束時間，Tis為開始時間。T總為總時長，S為工序集合{S1,S2,···,Sn}。

第二段為設備分配，確定加工零件的設備工作時段，計算公式如下所示：

其中：Mie為設備結束時間，MiS為設備開始時間，M總為所有設備總加工時長，M為設備集合{M1,M2,···,Mn}。

第三段為人員分配，確定相關操作人員工作時段，計算公式如下：

其中：Gie為操作人員結束時間；GiS為操作人員開始時間；G總為所有操作人員總加工時長；G為人員的集合{G1,G2,···,Gn}。

例如F1(S1,M2,G1)為任務F1的第一道工序由G1人員在M2設備上進行加工。

2.1.2 初始染色體種群

種群規模大小的選擇關系到排程結果的好壞，一般選擇種群大小在[50,200]。

采用加權系數法生成初始種群。對于插單的情況需采用前向排程,給突發情況留更多的緩沖空間，保證交貨期之前完成任務。對于委外工序，即該工序外包生產，采用前、后混合排程，在委外工序完成之前采用后向排程,在委外工序完成之后采用前向排程，有利于前后工序的緊密銜接。而對于以按時交貨為目標的任務，采用后向排程，保證按時交貨的同時降低庫存成本。

按照一定的權重隨機生成初始種群，面對不同的排程任務，動態調整權重大小。

2.1.3 選擇、交叉和變異

個體適應度越大，排程結果越優，根據個體的好壞程度決定個體選擇的概率，極大程度避免優良個體交叉變異之后成為較差個體，一定程度上保證了算法的收斂速度，也被稱為保優策略。一般選擇概率在[5%,10%]，本文選取8%，這部分個體直接進入子代種群中。

交叉是遺傳算法中的關鍵步驟，通過染色體交叉操作，可產生優良品種，增加種群多樣性。由于工序交叉無法保證產品的正常生產，所以采用設備兩點交叉的方式，即隨機設置兩個交叉點，再進行部分基因交換的方法。一般交叉概率在[50%,90%]。本文采用動態交叉概率，在交叉過程中，不斷改變交叉因子的大小，具體計算如下：

其中：Xi為交叉因子；G為總迭代次數；g為當前迭代次數。

采用均勻變異的方式，在符合某一范圍內取隨機數，這一變異方式適合于種群的初始運算。變異因子隨迭代次數動態變化。具體計算如下：

其中：Qi為變異因子；G為總迭代次數；g為當前迭代次數。

通過非固定交叉因子和變異因子，避免陷入局部最優解的同時，加快收斂速度，一定程度上提升了計算效率。

2.2 算法優化

基于遺傳算法的思想，在以下幾方面優化排產結果：

（1）基于產能失衡，或工序阻塞問題，在初始化種群時，根據派工級別按動態概率選擇設備。首先隨機產生索引數組（一個個數小于最大數的索引數組），索引數字大的概率高。

比如：index=4 產生的概率分布輸入：1-1/10,2-2/10,3-3/10,4-4/10。計算平均最優時間，將生產任務分派到設備上，保證設備分派的優先性和均衡性，計算公式如下：

其中：P總為計劃生產總數；T為平均時間；R為節拍；H為已占用時間。

（2）針對雙工位的設備，提出裂變分子的概念，算法設計偽代碼如下：

在排程結果涉及雙工位設備時進行染色體偏移，調整工序之間的空隙，提高排程的緊湊性，算法設計偽代碼如下：

（3）針對排程任務多造成速度慢，效率低問題，采用工序合并降低訂單數量，算法設計偽代碼如下：

3 結果分析

3.1 實例描述

本文以某機械制造公司的實際生產排程為例，利用所設計的算法求解，算例中涉及8 種零件，共1 255 個產品，50 臺相關設備，其中2 臺雙工位設備，9 條加工路線，1 個零件是雙工藝路線，表2為各工序可選設備，表3 為每臺設備單位生產節拍。

表2 工序可選設備

表3 設備單位生產節拍

3.2 排程展示

本文算法基于.NET 平臺，采用B/S 架構實現客戶端開發。排產過程運行在Window10 專業版64 位操作系統的PC 端，12.0 GB 運行內存，i7-5500U 雙核四線程處理器，最后經過6.3 s 得出結果。各參數詳細說明如下：

最短完工時間權重W1=0.3，按時交貨權重W2=0.4，48 h 達成率權W3=0.2，設備連續性權重W4=0.1，初始種群大小200，最大迭代次數150，選擇概率0.08，初始交叉概率0.8，變異概率0.05。

排程結果如圖1 所示。

對比之下，改進后的遺傳算法效率大大提高，產能充分利用，穩定性有保證，排程結果更加緊湊，設備使用率變高，加工時間縮短，人員安排更加靈活。

以傳統遺傳算法排程為1，兩種排程方式性能對比結果如表4 所示。

表4 結果對比

從表4 中數據可看出，改進排程在排產速度方面大大提高，經過多次排程性能均相差無幾，穩定性好，在處理多目標、訂單種類多和動態排程的情況，改進后的排程系統優勢更加顯著。

4 結語

本文基于多約束，多目標條件下的機加生產排程問題，設計多目標優化模型，利用加權系數組合優化法均衡各目標，采用三段式排程編碼方案進行編碼，在傳統遺傳算法的基礎上進行改進，設計了分子和裂變分子模型，針對裂變分子提出染色體偏移求解方法，保證了初始解質量。通過動態調整交叉和變異因子大小，彌補傳統算法收斂速度慢的缺陷，相較于傳統遺傳算法排程優勢明顯，為多約束多目標條件下的離散型機加生產制造提供理論指導。由于本文在算法設計上不夠簡潔，且未將成本因素考慮在內，這將作為今后進一步研究的方向。