基于協同多目標優化方法的流水車間組調度

肖秀梅，王欣蕊

（云南師范大學數學學院，昆明 650500）

0 引言

近年來，隨著生產力的快速發展，人們往往追求高效的方法來使企業獲得更高的效益。其中帶序列依賴的流水車間組調度問題（flow setup de?pendency group scheduling problem,FSDGSP）中提到的評估生產效率的指標是對這一問題的突破，在工業上得到了廣泛的應用。

FSDGSP 作為單元制造系統中的一個重要調度問題，引起了學術界和實踐者的極大關注。對于它的討論也變得越來越多。如Costa 等［1］研究具有阻塞約束的流水車間序列相關組調度問題的最小完工時間等。

目前解決FSDGSP的方法主要分為以下三類。

（1）精確算法。提出了一種基于分支界定法的基于總流量時間準則的FSDGSP 下界法。由于搜索效率相當低，對于小的問題，可以得到理論最優解。然而，對于中等大小的問題，在合理的時間內獲得大規模問題的最優解是非常困難的。

（2）構造性啟發法。根據一定的調度規則，采用構造性啟發式算法快速構造求解方案。一般來說，構造性啟發式被用作初始化方法，為元啟發式算法提供高質量的初始解。Reddy 等［2］提出了在組內安排工件的啟發式方法，以提高單元內機器的利用率。Neufeld 等［3］認為每個組都是一份有時間延遲的工件。

（3）元啟發式算法。元啟發式算法的通用性很強。各種搜索框架用于解決FSDGSP。Costa 等［1］提出了一種自適應遺傳算法，以最小化具有阻塞約束的FSDGSP 的最大完工時間。Lin 等［4］介紹了一種數學方法，用于求解具有無等待約束的FSDGSP。Li 等［5］設計了一種混合和聲搜索算法來解決FSDGSP 問題，其目標是最小化總延誤和平均總流量時間。Tavakkoli?Moghadam 等［6］研究了一種基于分散搜索的元啟發式算法，用于求解多準則的FSDGSP。

隨著綠色經濟的發展，能源消耗量逐漸成為評判生產效率的一個指標。然而在現有文獻中，主要優化的是一個或兩個生產目標。Shao等［7］提出PEDA 來解決MDNWFSP?SDST 問題，研究最大完工時間和等待時間之間的關系。Zhao 等［8］提出了TS?CEA 算法，研究加工時間和能耗之間的關系。何啟巍等［9］提出了混合粒子群優化算法，來解決最大完工時間和總流經時間之間的關系。基于多目標優化方法的流水車間調度問題已經成為當前調度方向的主流趨勢［10?11］，其中一個主要研究目標是最大完工時間。通過搜索能耗與多目標相關的論文，也可以觀察到能耗是一個熱點約束，而結合多目標與能耗的相關文獻較少。多目標優化相關文獻主題分布如圖1所示。

圖1 多目標優化相關文獻主題分布

1 問題描述

FSDGSP 問題可以描述為：有n個工件需要在m臺機床上依次加工，每個工件的加工工序一致，所有工件分配到指定組內。組內工件之間沒有準備時間，組間工件之間需要準備時間。圖2 展示了5 個工件在3 臺加工機床上的調度方案，其中工件1 和3 分到第一組，工件2/4/5 分到第二組。由圖2 可見，工件1 和3 之間沒有加工準備時間，第二組內的3 個工件之間也沒有加工準備時間。圖2 給出的調度方案的完工時間是425 分鐘。如果改變組內工件的排列順序，會得到不同效果的調度方案，如圖3 所示。圖3中工件1和3交換了一下位置，最終的makespan指標降低了15分鐘。

圖2 調度方案1

圖3 調度方案2

2 算法設計

2.1 問題編碼

首先進行種群編碼，假設有三個子問題：所有組的分組序列，每一個組內的工件序列以及在所有機器上的速度序列。一個解可以表示為(μ,τ,v)。μ表示按順序排好的一個組序列，τ表示在每一個組中的工件序列，v是一個速度等級矩陣，用于確定機器上處理每個作業的每個操作的速度。由于前期速度從未改變，所以一個解也可以表示為()μ,τ。通?？梢杂脵C器甘特圖的設計來實現。在圖4 所示的例子中，解的表示為組序列（1，4，2，3），工件的順序為｛（2，1），（7，8，6），（4，3），（5）｝。

圖4 甘特圖編碼

2.2 算法流程圖

設計的多目標優化算法流程如圖5所示。

圖5 CMOEA算法流程

3 實驗分析

3.1 實驗條件

該算法用MATLAB 編程語言實現。機器配置參數如下：CPU 型號為i7，內存為16 GB，操作系統為Win10。

3.2 實驗算例

針對某紡織車間組調度流程開展算法測試分析。實例包含387個工件，6臺機床，60個分組。所提算法CMOEA 求解該類問題的Pareto 解集如表1所示。

表1 CMOEA算法求解所得Pareto解集

3.3 算法對比

將CMOEA 算法與其他三種最新算法進行了比較［12］，包括基于分解的多目標進化算法（MOEAD?SAS）［13］，基于知識的協同進化算法（KCA）［14］，基于支配關系的多目標遺傳算法（NSGA?III）的改進版本［15］。

對這些算法的簡要描述如下：

（1）多目標優化問題（MOP）由基于分解的多目標進化算法（MOEA/D）分解為多個子問題。MOEA/D?SAS 是MOEA/D 的一種變體，采用基于角度的選擇和基于分解的排序兩種策略來實現多樣性和收斂性的平衡。

（2）針對高效節能的分布式流水車間調度問題，提出了KCA 算法。其核心思想是對不同的子問題自適應地采用不同的搜索算子。

（3）NSGA?III是基于支配關系的多目標遺傳算法（NSGA?II）的改進版，它提供了一組保持種群分布的參考點。NSGA?III用于解決多目標問題。

為了比較這些算法的差異性，所有競爭算法在同一計算環境中獨立運行10 次。最大運行時間是固定的，是K×n×m×δ毫秒。結果表明，在幾乎所有的測試用例中，CMOEA 在收斂性、分布性和超容量指標方面都比其他競爭算法得到的結果更好，這說明CMOEA 明顯優于其他競爭算法。

與其它三種算法的運行結果如圖6（a）～（d）所示。

圖6 算法求得的帕累托解集（續）

圖6 算法求得的帕累托解集

通過與當前其它算法相比，CMOEA 算法的最大完工時間、總流經時間、總能耗都是相對最小的，由此可以得出該算法的有效性。

4 結語

本文的主要工作：

（1）在FSDGSP 研究一兩個目標的基礎上，加入能量消耗作為優化目標，因此目標變成了三個。采用CMOEA 算法提出求解多目標FSDGSP問題。

（2）分析FSDGSP 的問題特點，展示了問題特性。

（3）對問題進行編碼與解碼，提出協同多目標優化CMOEA 算法來尋找最優解集。與其他競爭算法相比較，得出本文提出的CMOEA 算法具有明顯優于現有競爭算法的搜索性能。