基于協(xié)同多目標優(yōu)化方法的流水車間組調(diào)度

肖秀梅，王欣蕊

（云南師范大學數(shù)學學院，昆明 650500）

0 引言

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

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

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

（1）精確算法。提出了一種基于分支界定法的基于總流量時間準則的FSDGSP 下界法。由于搜索效率相當?shù)停瑢τ谛〉膯栴}，可以得到理論最優(yōu)解。然而，對于中等大小的問題，在合理的時間內(nèi)獲得大規(guī)模問題的最優(yōu)解是非常困難的。

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

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

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

圖1 多目標優(yōu)化相關文獻主題分布

1 問題描述

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

圖2 調(diào)度方案1

圖3 調(diào)度方案2

2 算法設計

2.1 問題編碼

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

圖4 甘特圖編碼

2.2 算法流程圖

設計的多目標優(yōu)化算法流程如圖5所示。

圖5 CMOEA算法流程

3 實驗分析

3.1 實驗條件

該算法用MATLAB 編程語言實現(xiàn)。機器配置參數(shù)如下：CPU 型號為i7，內(nèi)存為16 GB，操作系統(tǒng)為Win10。

3.2 實驗算例

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

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

3.3 算法對比

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

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

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

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

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

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

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

圖6 算法求得的帕累托解集（續(xù)）

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

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

4 結語

本文的主要工作：

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

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

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