許彥輝 高 尚

（江蘇科技大學(xué)計算機(jī)學(xué)院 鎮(zhèn)江 212000）

1 引言

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

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

摸石頭過河算法提出時日尚短，但其也已經(jīng)具有極大的優(yōu)越性，并且經(jīng)過數(shù)年的發(fā)展，也獲得了一定的改進(jìn)，對于連續(xù)優(yōu)化問題與離散優(yōu)化問題都能取得較好的優(yōu)化結(jié)果［14］；將摸石頭過河算法應(yīng)用在解決實際的多目標(biāo)車間調(diào)度多目標(biāo)優(yōu)化問題中，首先對FT06的標(biāo)準(zhǔn)問題進(jìn)行求解優(yōu)化，然后考慮到實際生產(chǎn)中存在工件在機(jī)器間的運(yùn)輸時間問題，將其考慮在內(nèi)，繼續(xù)優(yōu)化帶有運(yùn)輸時間的FT06標(biāo)準(zhǔn)問題，均優(yōu)化得到最優(yōu)解［14］。

2 摸石頭過河算法

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

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

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

3 多目標(biāo)摸石頭過河算法

3.1 算法模型

對優(yōu)化多目標(biāo)問題可表示為

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

當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時，即不存在最優(yōu)解使所有目標(biāo)函數(shù)同時最優(yōu)化。此時，把m個目標(biāo)集成在一起，構(gòu)成一個實質(zhì)偏好函數(shù)，即構(gòu)造一個妥協(xié)模型。然后在相同條件下，極大化妥協(xié)模型函數(shù)，得到的函數(shù)解成為妥協(xié)解，并作為實際意義上的原多目標(biāo)問題的Pareto有效解［14］。

采用加權(quán)求和你法構(gòu)造多目標(biāo)優(yōu)化問題的妥協(xié)模型。設(shè)目標(biāo)函數(shù)fj(x)的優(yōu)選權(quán)系數(shù)分別為λj，其中，j=1，2，…，m，則可以構(gòu)造如下綜合評價目標(biāo)函數(shù)［14］：

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

3.2 多目標(biāo)摸石頭過河算法流程

本文提出求解Pareto最優(yōu)解的多目標(biāo)的摸石頭過河優(yōu)化算法，具體流程如下：

1）隨機(jī)產(chǎn)生N個初始可行解X1，X2，…，XN以及m個權(quán)值λ1，λ2，…，λm，其中0≤λj≤1且λ1+λ2+…+λm=1，評價各獨立優(yōu)化目標(biāo)fj以及綜合目標(biāo)將p個可行方案的綜合目標(biāo)值，確定為當(dāng)前最佳方案最佳解X，令k=0。

2）由當(dāng)前解X通過鄰域函數(shù)生成p個新的可行搜索解，并對其優(yōu)化目標(biāo)和綜合目標(biāo)進(jìn)行評估。

3）對比全部的綜合性的目標(biāo)，如果存在這種

FX＜FX，那么用X'代替X成為新的當(dāng)前解。

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

上述算法過程保留了傳統(tǒng)的摸石頭過河算法的特點，并采用加權(quán)綜合目標(biāo)對多目標(biāo)優(yōu)化進(jìn)行評價。由于權(quán)重的隨機(jī)性，該算法的多次運(yùn)行或并行實現(xiàn)可以在Pareto邊界上獲得多個方向的Pareto最優(yōu)解，為決策者提供多個選擇。應(yīng)該強(qiáng)調(diào)的是：

1）步驟1）中，產(chǎn)生N個初始可行解，由于初態(tài)的隨機(jī)性，當(dāng)數(shù)量N足量多時可一定程度上體現(xiàn)了整個解空間中狀態(tài)的分布情況。

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

4 仿真實驗結(jié)果與分析

本文主要是在Matlab環(huán)境下進(jìn)行的實驗分析，通過比較算法求解多目標(biāo)優(yōu)化問題的結(jié)果，對影響尋優(yōu)結(jié)果的鄰域解搜索方法進(jìn)行了討論，確定了較好的鄰域解搜索方法。其中選擇的標(biāo)準(zhǔn)算例是車間調(diào)度問題FT06。

4.1 實際問題介紹

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

表1 標(biāo)準(zhǔn)問題FT06

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

圖2 生產(chǎn)過程示意圖

在實際生產(chǎn)現(xiàn)場，往往要考慮到工件之間的物流時間，則標(biāo)準(zhǔn)問題便會被復(fù)雜化。以某葉片車間生產(chǎn)制造現(xiàn)場為例，其加工機(jī)器布局如圖3。工件在各個機(jī)器之間的物流時間用矩陣表示為［14］

圖3 機(jī)器布局圖

其中Aij表示工件從Mi運(yùn)輸?shù)組j所需的時間。

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

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

4.2 綜合評價函數(shù)構(gòu)造中權(quán)值的影響

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

λ=0時，F(xiàn)=87，其中機(jī)器加工最大時間55，機(jī)器空閑時間87；

λ=0.25時，F(xiàn)=79，其中機(jī)器加工最大時間55，機(jī)器空閑時間87；

λ=0.5時，F(xiàn)=71，其中機(jī)器加工最大時間55，機(jī)器空閑時間87；

λ=0.75時，F(xiàn)=63，其中機(jī)器加工最大時間55，機(jī)器空閑時間87；

λ=1時，F(xiàn)=55，其中機(jī)器加工最大時間55，機(jī)器空閑時間99。

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

表2 不同權(quán)值下的綜合評價函數(shù)優(yōu)化結(jié)果

4.3 增加工件運(yùn)輸時間對尋優(yōu)的影響

在實際的車間生產(chǎn)過程中，工件在機(jī)器之間的加工轉(zhuǎn)運(yùn)往往也要花費(fèi)一定的時間，因此在實際的調(diào)度優(yōu)化中需要考慮到運(yùn)輸時間的存在，本節(jié)將運(yùn)輸時間引入到我們的優(yōu)化問題中來，機(jī)器間工件的運(yùn)輸時間可見4.1節(jié)矩陣A，機(jī)器位置布局見圖3［14］。

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

圖4 增加運(yùn)輸時間的FT06問題最優(yōu)解甘特圖

表3 增加運(yùn)輸時間的FT06問題機(jī)器加工時間表

5 結(jié)語

多目標(biāo)優(yōu)化問題被應(yīng)用于生產(chǎn)和生活的各個方面，對作業(yè)車間調(diào)度問題的深入研究具有重要的理論意義和應(yīng)用價值。尋求高效穩(wěn)定的調(diào)度算法是制造業(yè)和人工智能領(lǐng)域共同研究的重點?；贘ob-Shop調(diào)度問題具有深遠(yuǎn)的研究意義，提出了一種簡單有效的摸石頭過河算法對其進(jìn)行優(yōu)化。摸石頭過河算法本身對于連續(xù)優(yōu)化和離散優(yōu)化問題的優(yōu)化具有一定的優(yōu)勢。在多目標(biāo)優(yōu)化問題的基礎(chǔ)上，提出了一種多目標(biāo)摸石頭過河算法對其進(jìn)行優(yōu)化。優(yōu)化過程相對簡單，但效率高，可以簡單地找到最優(yōu)解，通過仿真驗證了該算法的可行性和有效性。