摸石頭過河算法解決車間調度問題的研究*

許彥輝 高 尚

（江蘇科技大學計算機學院 鎮江 212000）

1 引言

作業車間調度即Job-Shop調度問題，是典型的多目標問題，很多研究學者都會將其作為生產調度問題［1～4］，對于企業復雜的生產調度環境，作業生產調度是一種簡化模型。對該調度模型的研究具有實際的理論意義和研究價值。作業車間生產調度是指每個生產作業需要在多臺加工機器上進行加工。每個生產作業包含多個生產過程。工件一經加工，不得中斷。每個生產作業都有自己的處理順序，不限制作業處理的機器，一個生產作業可以有不同的處理路徑，一臺機器一次只能處理一個作業。在這種生產車間中，機器的布局是任意的，工件的加工機器也是任意的，每個工件的數量和加工順序也是任意的，每個產品都有其不確定的加工路徑。由于作業加工的多重約束和加工環境的隨機不確定性，它已成為一個極其困難的NP完全問題。傳統多目標優化算法有加權法求和法［5～6］、約束法［7］、目標規劃法［8～9］和目標滿意法［10］等。近些年研究比較熱門的多目標遺傳算法［11］、蟻群算法［12］、粒子群算法［13］等也是用來解決最優化問題。

“摸石頭過河算法”在2015年被高尚、邱玲、曹存根等率先提出。2015年3月，高尚、邱玲、曹存根在《南京師范大學報》自然科學版發表《解連續性優化問題的摸石頭過河算法》的學術研究文章，受到摸石頭過河思想的啟發，提出了摸石頭過河算法［14］，同時通過仿真實驗，驗證了其具有搜索速度快、精度高和不易陷入局部極值點的特點，進而說明該算法具有較好的全局搜索能力，應用前景非常廣泛，具有一定潛力［15］。

摸石頭過河算法提出時日尚短，但其也已經具有極大的優越性，并且經過數年的發展，也獲得了一定的改進，對于連續優化問題與離散優化問題都能取得較好的優化結果［14］；將摸石頭過河算法應用在解決實際的多目標車間調度多目標優化問題中，首先對FT06的標準問題進行求解優化，然后考慮到實際生產中存在工件在機器間的運輸時間問題，將其考慮在內，繼續優化帶有運輸時間的FT06標準問題，均優化得到最優解［14］。

2 摸石頭過河算法

摸石頭過河算法的思想來源于“摸石頭過河”的思想［16］：摸到一個“石頭”后，向該“石頭”周圍摸索其它石頭，當再摸到一個“石頭”后，再向該“石頭”周圍摸索其它石頭，以此類推進行搜索。摸石頭過河算法以一個解為起點，向該起點附近鄰域隨機搜索若干個解，找出這些解中的最好的一個解，以此解作為第2次迭代的結果。然后以此點為起點，再向附近鄰域隨機搜索若干個解，找出這些解中的最好的一個解，以此解作為第3次迭代的結果。后面的步驟以此類推，直到達到最大迭代次數或其它停止條件為止。其迭代過程如圖1所示。

圖1 摸石頭過河算法迭代過程

摸石頭過河算法是一個尋解與迭代的過程。由于算法每一次尋解都只保留最好解，所以在迭代的正反饋作用下，函數目標函數值將趨向于該函數的最小值。具體算法流程為［14］

3 多目標摸石頭過河算法

3.1 算法模型

對優化多目標問題可表示為

其中，x=(x1，x2，…，xn)∈X∈Rn，n為變量的維數，X為決策空間；y=(y1，y2，…，ym)∈Y∪Rn，m為目標函數個數，Y為目標空間；gi(x)≥0(i=1，2，…，p)為p個不等式約束；hj(x)=0(j=1，2，…，q)為q個等式約束。

當目標函數處于沖突狀態時，即不存在最優解使所有目標函數同時最優化。此時，把m個目標集成在一起，構成一個實質偏好函數，即構造一個妥協模型。然后在相同條件下，極大化妥協模型函數，得到的函數解成為妥協解，并作為實際意義上的原多目標問題的Pareto有效解［14］。

采用加權求和你法構造多目標優化問題的妥協模型。設目標函數fj(x)的優選權系數分別為λj，其中，j=1，2，…，m，則可以構造如下綜合評價目標函數［14］：

其中，0≤λj≤1，且λ1+λ2+…+λm=1。然后利用摸石頭算法進行求解。

3.2 多目標摸石頭過河算法流程

本文提出求解Pareto最優解的多目標的摸石頭過河優化算法，具體流程如下：

1）隨機產生N個初始可行解X1，X2，…，XN以及m個權值λ1，λ2，…，λm，其中0≤λj≤1且λ1+λ2+…+λm=1，評價各獨立優化目標fj以及綜合目標將p個可行方案的綜合目標值，確定為當前最佳方案最佳解X，令k=0。

2）由當前解X通過鄰域函數生成p個新的可行搜索解，并對其優化目標和綜合目標進行評估。

3）對比全部的綜合性的目標，如果存在這種

FX＜FX，那么用X'代替X成為新的當前解。

4）判斷是否滿足終止條件，否則令k=k+1，返回步驟2）。

上述算法過程保留了傳統的摸石頭過河算法的特點，并采用加權綜合目標對多目標優化進行評價。由于權重的隨機性，該算法的多次運行或并行實現可以在Pareto邊界上獲得多個方向的Pareto最優解，為決策者提供多個選擇。應該強調的是：

1）步驟1）中，產生N個初始可行解，由于初態的隨機性，當數量N足量多時可一定程度上體現了整個解空間中狀態的分布情況。

2）摸石頭過河算法區別于傳統規劃算法的關鍵之一在于鄰域函數的設計。一般地，可以簡單采用附加Gaussian分布擾動方式，即x'=x+ηξ，ξ∈N(0，1)，η為步長。最優解的保留則能夠避免優良解的遺失。

4 仿真實驗結果與分析

本文主要是在Matlab環境下進行的實驗分析，通過比較算法求解多目標優化問題的結果，對影響尋優結果的鄰域解搜索方法進行了討論，確定了較好的鄰域解搜索方法。其中選擇的標準算例是車間調度問題FT06。

4.1 實際問題介紹

為了判斷算法的優缺點，需要用同樣的問題去測試，這些測試問題逐漸形成了標準問題。最著名的標準問題是Fisher等［17］提出的FT問題，包括FT06（6×6，即為6個工件，每個工件有6道不同的加工工序）、FT10（10×10）和FT20（20×5）。本文中采用FT06標準問題對多目標摸石頭過河算法的可行性進行分析研究。FT06問題描述見表1，其中的序列對（M，T）表示（機器，加工時間）［14］。

表1 標準問題FT06

FT06問題的描述可見圖2。工件P1在機器M3上加工，生成節點11，1個單位時間后，節點11消亡，工件P1在機器M1上加工3個單位時間。6個工件的加工過程形成了生產現場的6個線程［14］。

圖2 生產過程示意圖

在實際生產現場，往往要考慮到工件之間的物流時間，則標準問題便會被復雜化。以某葉片車間生產制造現場為例，其加工機器布局如圖3。工件在各個機器之間的物流時間用矩陣表示為［14］

圖3 機器布局圖

其中Aij表示工件從Mi運輸到Mj所需的時間。

設置迭代尋優次數為100，通過加權求和法構造綜合評價函數，共有兩個優化目標，為機器工作時間為Cmax和機器工作空閑時間Wmax，機器工作時間權值設為λ，分目標的權值之和為的原則即則機器工作空閑時間權值為1-λ，得到構造的綜合評價函數為F=λ*Cmax+(1-λ)*Wmax［14］。

為了分析多目標摸石頭過河算法的性能，我們通過針對性的幾點討論來分析所提出算法的性能，主要是通過加權求和法構造的綜合評價函數中權值對算法優化的影響，以及多目標摸石頭過河算法在增加運輸時間的標準問題FT06上的優化性能［14］。

4.2 綜合評價函數構造中權值的影響

在多目標摸石頭過河算法優化過程中，綜合評價函數對優化的結果至關重要，這里我們討論了多目標中各分目標的不同權值對優化結果的影響，車間調度算法中主要優化的兩個目標：機器加工的最大時間Cmax以及機器工作空閑時間Wmax，通過加權求和法得到綜合評價函數F=λ*Cmax+(1-λ)*Wmax，為了公平比較，對每個權值求和得到的評價函數優化時各做了500次實驗［14］，從中得到的最優結果為

λ=0時，F=87，其中機器加工最大時間55，機器空閑時間87；

λ=0.25時，F=79，其中機器加工最大時間55，機器空閑時間87；

λ=0.5時，F=71，其中機器加工最大時間55，機器空閑時間87；

λ=0.75時，F=63，其中機器加工最大時間55，機器空閑時間87；

λ=1時，F=55，其中機器加工最大時間55，機器空閑時間99。

具體優化結果可見表2。從最優結果中，可以看出除了λ=1時，其余權值情況下優化得到的機器加工最大時間與機器空閑時間是相同，然而由甘特圖也可以看出，最終優化得到的加工順序確實不同，優化的綜合評價函數值相同，這也說明該問題具有很多個最優解，而不同權值的優化方式都是可以優化到最優值的，多目標摸石頭過河算法是可以優化FT06問題得到最優解的［14］。

表2 不同權值下的綜合評價函數優化結果

4.3 增加工件運輸時間對尋優的影響

在實際的車間生產過程中，工件在機器之間的加工轉運往往也要花費一定的時間，因此在實際的調度優化中需要考慮到運輸時間的存在，本節將運輸時間引入到我們的優化問題中來，機器間工件的運輸時間可見4.1節矩陣A，機器位置布局見圖3［14］。

同樣地，經過以上幾節的實驗研究，在加入工件運輸時間后，設置參數為取權值λ=0.5構造綜合評價函數F=0.5*Cmax+0.5*Wmax，初始解的搜索個數為10000，鄰域解的搜索方法采用三種方法隨機選擇混合的方式，每次迭代的鄰域解搜索個數為100，迭代總次數為100，共進行500組實驗。500次實驗中，優化得到的最優值為89，最劣值為102.5，500次實驗結果的平均值為92.161，該問題的最優值也為89，根據實驗結果可以看出加入工件運輸時間以后，優化問題變得更復雜，多目標摸石頭過河算法依然能夠優化得到最優值。由一組最優值編碼201520310255342514013341041235442503，表3列出了該方案的機器加工時間，表中數字含義與表1相同，圖4同時也展示了該加工甘特圖［14］。

圖4 增加運輸時間的FT06問題最優解甘特圖

表3 增加運輸時間的FT06問題機器加工時間表

5 結語

多目標優化問題被應用于生產和生活的各個方面，對作業車間調度問題的深入研究具有重要的理論意義和應用價值。尋求高效穩定的調度算法是制造業和人工智能領域共同研究的重點。基于Job-Shop調度問題具有深遠的研究意義，提出了一種簡單有效的摸石頭過河算法對其進行優化。摸石頭過河算法本身對于連續優化和離散優化問題的優化具有一定的優勢。在多目標優化問題的基礎上，提出了一種多目標摸石頭過河算法對其進行優化。優化過程相對簡單，但效率高，可以簡單地找到最優解，通過仿真驗證了該算法的可行性和有效性。