基于改進(jìn)粒子群的作業(yè)車間調(diào)度多目標(biāo)優(yōu)化方法

魏宏靜，魏宏鈺，黃 彪

（1.貴州理工學(xué)院機(jī)械工程學(xué)院，貴州 貴陽 550003；2.銅仁職業(yè)技術(shù)學(xué)院經(jīng)濟(jì)與管理學(xué)院，貴州 銅仁 554300）

0 引言

當(dāng)前，制造技術(shù)和科學(xué)技術(shù)的快速發(fā)展，制造規(guī)模和復(fù)雜度都在迅速提高，在市場上的競爭也越來越激烈。為了使企業(yè)在市場上取得更大的成功，就需要對整個企業(yè)、各車間、各生產(chǎn)環(huán)節(jié)做出更加有效的計劃安排。在最近的幾十年里，由于制造技術(shù)、信息技術(shù)、自動化技術(shù)等得到了全面的綜合應(yīng)用，許多先進(jìn)的制造模式相繼出現(xiàn)[1]。盡管現(xiàn)有制造模式在原理上和實現(xiàn)技術(shù)上都存在較大差異，但每一種制造方式都需要實現(xiàn)對內(nèi)外資源的優(yōu)化配置，以此才能夠?qū)崿F(xiàn)對制造周期的縮短和對生產(chǎn)成本的控制，從而要解決當(dāng)前大部分企業(yè)所面臨的共同問題，從而提高企業(yè)在市場上的競爭力。作業(yè)車間調(diào)度作為整個先進(jìn)制造結(jié)構(gòu)體系實現(xiàn)和核心，其實質(zhì)是在一定時間內(nèi)，將可利用的共享資源、生產(chǎn)任務(wù)等進(jìn)行合理的分配和排序，并使其達(dá)到期望的特定的性能指標(biāo)。以最優(yōu)的工作車間計劃為目標(biāo)，能夠幫助企業(yè)在經(jīng)濟(jì)效益和資源利用向著更積極的方向發(fā)展[2]。同時，有效的作業(yè)車間調(diào)度優(yōu)化也是實現(xiàn)提升生產(chǎn)效率和先進(jìn)制造的基礎(chǔ)與關(guān)鍵。基于此，為促進(jìn)企業(yè)競爭實力提升，本文結(jié)合改進(jìn)粒子群算法，開展對作業(yè)車間調(diào)度多目標(biāo)優(yōu)化方法的設(shè)計研究。

1 構(gòu)建多目標(biāo)作業(yè)車間調(diào)度目標(biāo)優(yōu)化模型

從作業(yè)車間的生產(chǎn)實際角度出發(fā)，以生產(chǎn)周期，交貨滿意度，生產(chǎn)成本，加工設(shè)備利用率為指標(biāo)，制定最優(yōu)的生產(chǎn)計劃[3]。針對不同調(diào)度優(yōu)化目標(biāo)，確定對應(yīng)的量化指標(biāo)，如表1 所述。

表1 作業(yè)車間調(diào)度優(yōu)化目標(biāo)與量化指標(biāo)對照

針對表1 中記錄的各項量化指標(biāo)，明確其具體的求取公式，并完成對各項指標(biāo)目標(biāo)函數(shù)的構(gòu)建。產(chǎn)品制造周期內(nèi)的最長完工時間指標(biāo)y1的計算公式為：

式中，N為待加工工件類型總數(shù)；n為待加工工件種類；Tn為某一類工件n的完成時間。拖延懲罰系數(shù)y2的計算公式為：

式中，ETn為某一類待生產(chǎn)工件n在作業(yè)車間中生產(chǎn)產(chǎn)生的延誤時間。公式中，ETn可通過下述公式計算得出：

式中，DTn為某一類待生產(chǎn)工件n的交貨日期。加工成本y3的計算公式為：

式中，vm為單位時間內(nèi)某一機(jī)床作業(yè)時所消耗的費用；sm為單位時間內(nèi)某一機(jī)床閑置時所消耗的費用；t0為某一待加工工件在某一工序上所消耗的時間；x0為決策變量；M為調(diào)度方案中規(guī)定的最大完成時間。機(jī)床最大負(fù)荷y4的計算公式為：

在公式（4）和公式（5）中，當(dāng)x0的取值為1 時，此時某一類待加工工件第某工序在機(jī)床上進(jìn)行加工；當(dāng)x0的取值為0 時，此時為未選中狀態(tài)。根據(jù)上述公式，確定多目標(biāo)作業(yè)車間調(diào)度目標(biāo)優(yōu)化模型Y的表達(dá)式為：

進(jìn)一步確定各項量化指標(biāo)與目標(biāo)Y之間的關(guān)系為：y1、y2、y3與Y為負(fù)向相關(guān)；y4與Y為正向相關(guān)，即y1、y2、y3越小，y4越大，作業(yè)車間調(diào)度優(yōu)化效果越理想。

2 基于改進(jìn)粒子群的調(diào)度問題編碼

為了解決調(diào)度問題，在調(diào)度問題編碼中，首先將染色體的位置向量與排程規(guī)劃相對應(yīng)。優(yōu)化調(diào)度問題求解的滿意程度和算法的復(fù)雜性都與編碼質(zhì)量密切相關(guān)[4]。在編碼的過程中需要考慮到編碼的可行性以及有效性。把調(diào)度編碼過程的順序，每一個基因都表示代工生產(chǎn)的過程[5]。在此基礎(chǔ)上，根據(jù)每個工藝點在已知染色體顆粒上的排列順序，確定每個工藝點的個數(shù)。假定Job Shop 排序問題有n個工件數(shù)，那么改進(jìn)粒子群中的每一條染色體都包含n×m個完整的基因，每一條工件數(shù)都是m次，這里的基因是對工件數(shù)進(jìn)行排序的，并不是對工件數(shù)進(jìn)行詳細(xì)描述[6]。以包含3 個機(jī)器，3 個工件的Job Shop 調(diào)度為例，見表2。

表2 包含3 個機(jī)器3 個工件的Job Shop 調(diào)度案例

針對表2 中的3 個機(jī)器3 個工件的Job Shop 調(diào)度案例，其改進(jìn)粒子群編碼如圖1 所示。

圖1 改進(jìn)粒子群編碼

在對調(diào)度問題編碼時，隨機(jī)生成9 維（3×3）染色體顆粒。1，2，3 分別代表相應(yīng)的工件j1、j2、j3的工序號。因為每一個產(chǎn)品都包括3 個步驟，所以每一個整數(shù)表示產(chǎn)品在一個染色體上的三次發(fā)生。在譯碼過程中，首先利用修正的質(zhì)點向量來判斷各工藝的加工機(jī)理，并將相應(yīng)的質(zhì)點向量轉(zhuǎn)化為順序操作表。兩種的順序決定著工序調(diào)度的優(yōu)先順序，再依據(jù)表2 中的內(nèi)容，按照工序的先后次序，按照工序的最短容許時間，對所分配的機(jī)床進(jìn)行加工，進(jìn)而得到調(diào)度方案。

3 粒子位置更新策略與最優(yōu)解搜索

在完成對調(diào)度問題的編碼后，結(jié)合改進(jìn)粒子群算法，確定粒子位置更新策略，并搜索調(diào)度最優(yōu)解。通過對微粒群算法進(jìn)行優(yōu)化，得到微粒在微粒演化過程中，微粒在當(dāng)前狀態(tài)下、個體最佳狀態(tài)與種群最佳狀態(tài)相互影響的變化規(guī)律。通過模仿構(gòu)建上述三個部分，基于改進(jìn)粒子群算法的優(yōu)化機(jī)制，定義離散粒子群粒子位置更新公式：

式中，Xki+1為離散粒子群粒子位置更新結(jié)果；c1為認(rèn)知系數(shù)；c2為社會系數(shù)；ω為慣性權(quán)重因子。利用對染色體粒子進(jìn)行的編輯運算，對其搜索空間進(jìn)行拓展，從而指導(dǎo)粒子進(jìn)行進(jìn)化。最終確定最優(yōu)解。主要變異方式包括：交換變異、插入變異和反序變異。在改進(jìn)粒子群中，通過在p 位、q 位兩個位點，在不改變其他位點的情況下，將兩位點上的基因進(jìn)行互換。本文中的互換運算使兩個位點上的基因不完全一樣，從而避免兩個位點上的基因完全一樣的可能[7]。在該方法中，通過對染色體顆粒中的p、q 個基因進(jìn)行隨機(jī)選取，并將其插入到相應(yīng)的位置。逆序突變是指在兩個不同的位點上，在兩個位點上進(jìn)行一次突變，然后將兩個位點上的基因重新插入到兩個位點上[8]。在此基礎(chǔ)上，提出了一種基于微粒群的離散微粒群優(yōu)化方法，該方法具有微粒群優(yōu)化方法收斂快、易于實現(xiàn)等特點。然而，在具有有限的搜索迭代次數(shù)和粒子數(shù)的條件下，調(diào)度問題的規(guī)模越大，可供求解的空間也就越大，算法不可避免地會陷入局部最優(yōu)，而不能完全絕對地保證每次都能搜索到全局最優(yōu)。利用改進(jìn)粒子群算法中的局部搜索策略，對作業(yè)車間調(diào)度多目標(biāo)優(yōu)化問題進(jìn)行最優(yōu)解搜索。在執(zhí)行完成一次粒子位置的更新操作后，針對中群眾的適應(yīng)度數(shù)值在前10%的個體以及其他任意20%的個體進(jìn)行最優(yōu)解搜索。在相應(yīng)點上，采用了一種基于交變鄰居結(jié)構(gòu)的最佳搜索策略，實現(xiàn)了對相應(yīng)點的局部搜索。在具體對作業(yè)車間調(diào)度多目標(biāo)優(yōu)化求解時，設(shè)定初始參數(shù)。通過對PSO 的恒定慣性權(quán)數(shù)、認(rèn)知因子、社會因子進(jìn)行初值，并對最大迭代數(shù)和群體大小進(jìn)行計算。采用基于步驟表示的編碼方式，對群體和染色體進(jìn)行隨機(jī)初始化，生成群體和染色體顆粒。通過對每一個微粒進(jìn)行譯碼，得到微粒在譯碼過程中的適合度，并將該適合度作為優(yōu)化問題的一個目標(biāo)函數(shù)，記錄下微粒在初始狀態(tài)下的局部最優(yōu)和整體最優(yōu)。更新粒子位置，并同時更新各個粒子的局部最優(yōu)值和全局最優(yōu)值。在該算法中，對個體的適應(yīng)度最高的10%和其他20%的個體進(jìn)行局部尋優(yōu)。在此基礎(chǔ)上，對每個粒子進(jìn)行局部最優(yōu)和整體最優(yōu)。判斷是否達(dá)到進(jìn)化停止條件，若是，則輸出求得的最優(yōu)值結(jié)果，并退出循環(huán)，否則重復(fù)上述操作步驟，直到確定最優(yōu)解為止。對離散微粒群算法的改進(jìn)，是以基本微粒群算法的演化優(yōu)化機(jī)理為基礎(chǔ)的，與遺傳算法的優(yōu)勝劣汰的演化機(jī)理完全不同。根據(jù)上述操作，完成對作業(yè)車間調(diào)度多目標(biāo)的最優(yōu)解搜索，將最優(yōu)解作為最終的作業(yè)車間調(diào)度方案。

4 優(yōu)化前后對比

在上述論述基礎(chǔ)上，為驗證引入改進(jìn)粒子群算法的目標(biāo)優(yōu)化方法是否能夠?qū)崿F(xiàn)對作業(yè)車間調(diào)度的多目標(biāo)優(yōu)化，選擇以某生產(chǎn)制造企業(yè)的作業(yè)車間為研究對象，針對其日常作業(yè)任務(wù)進(jìn)行調(diào)度。通過對比優(yōu)化前后作業(yè)車間的生產(chǎn)周期用工件最大完成時間、生產(chǎn)成本、機(jī)床利用率等指標(biāo)，對是否實現(xiàn)優(yōu)化進(jìn)行判定。該生產(chǎn)制造企業(yè)的作業(yè)車間生產(chǎn)規(guī)模是多品種、小批量的，屬于流程式作業(yè)車間。在生產(chǎn)過程中集合了人、設(shè)備、材料以及能源等多種因素，生產(chǎn)過程中生產(chǎn)物料的連續(xù)性、生產(chǎn)工藝等約束的復(fù)雜性使得該作業(yè)車間的調(diào)度極為復(fù)雜。根據(jù)該生產(chǎn)制造企業(yè)對該作業(yè)車間的生產(chǎn)要求，確定生產(chǎn)周期最大完成時間應(yīng)控制在18～20 天范圍內(nèi)；生產(chǎn)成本控制在15 元/m ～17 元/m范圍內(nèi)；機(jī)床作業(yè)率應(yīng)控制在85%以上。根據(jù)上述標(biāo)準(zhǔn)，將應(yīng)用本文設(shè)計的優(yōu)化方法前后優(yōu)化效果對比，得到結(jié)果見表3。

表3 優(yōu)化前后作業(yè)車間調(diào)度結(jié)果相關(guān)參數(shù)記錄

對表3 中記錄的結(jié)果進(jìn)行分析得出，優(yōu)化后生產(chǎn)周期最大完成時間、生產(chǎn)成本明顯降低，機(jī)床作業(yè)率明顯提升，且三項指標(biāo)均在該生產(chǎn)制造企業(yè)對該作業(yè)車間生產(chǎn)要求規(guī)定范圍內(nèi)。生產(chǎn)周期最大完成時間越短，生產(chǎn)成本越低，機(jī)床作業(yè)率越高，調(diào)度效果越理想。因此，通過上述得出的結(jié)果可以證明，本文提出的基于改進(jìn)粒子群算法的優(yōu)化方法能夠?qū)崿F(xiàn)對作業(yè)車間調(diào)度多目標(biāo)優(yōu)化，具備極高的應(yīng)用可行性。

5 結(jié)語

針對作業(yè)車間調(diào)度問題，本文提出了一種基于改進(jìn)粒子群算法的多目標(biāo)優(yōu)化方法。將該方法應(yīng)用于實際可以使作業(yè)車間生產(chǎn)周期最大完成時間縮短，降低生產(chǎn)成本，并促進(jìn)機(jī)床作業(yè)率的提升。通過研究得出，將改進(jìn)粒子群算法應(yīng)用到作業(yè)車間調(diào)度優(yōu)化中可以縮小算法的搜索空間，使算法效率得到提升。同時，該算法還可以將求解的優(yōu)化問題聚焦于決策所關(guān)注的范圍內(nèi)，從而有效地降低了非劣解個數(shù)，從而有效地解決了從一堆非劣解中搜索出最優(yōu)解的難題。