批量生產作業車間的雙資源多目標調度問題研究

2011-10-18 14:33:46初紅艷費仁元李風光鄧穎輝

制造技術與機床 2011年9期

初紅艷費仁元李風光鄧穎輝

(北京工業大學機電學院，北京100124)

車間批量調度在先進制造系統的生產實際中具有非常高的普遍性，研究車間批量調度的優化方法，不僅可以促進調度理論的發展，而且對于企業提高生產效率和生產能力，降低生產成本有著重要的影響［1］;雙資源調度是指在調度過程中不僅考慮加工設備受到制約的情況，而且要考慮有著熟練加工能力或特殊加工能力的工人，工人和設備的合理利用明顯有利于提高產品的綜合效益;多目標調度則是指在作業車間內將各工件的工序合理安排在設備上，并確定各工序的開工時間，同時優化給定的多個性能指標。

通過對實際生產狀況的分析，針對作業車間批量生產的問題提出了分批調度策略。建立雙資源多目標優化調度模型，對分批后的工件采用遺傳算法和禁忌搜索算法相結合的混合優化算法進行調度。調度算例驗證了研究的可行性和有效性，對生產實踐具有一定的指導作用。

1 分批調度策略

分批的核心思想是:當車間只加工一類工件時，必定存在一個最優的分批方案。

先確定一定數量某種工件單獨加工時應該劃分的子批數，然后計算每個子批包含的工件數，計算每個子批的每道工序需要的新的加工時間，并將每個子批看做一個新工件。在此基礎上采用調度算法進行調度。

某工件單獨加工時，需要劃分的批次判定公式為

式中:m為工序數;n為批數;ti為該工件第i工序的加工時間;tL為最長工序的加工時間;K為子批中包含的工件數(此時判定公式并不是求得最終結果的公式，K根據計算結果能取非整數)，T為考慮分批的時間參數。

進行分批時，依次取n=1，2，…，N(N為工件的數目)，根據式(1)計算此時的時間參數T，比較找出最小的T，輸出與其對應的分批數n。

分批算法中引入了參數K，可以取為非整數，這樣就豐富了分批的情況，而不僅僅局限于完全等分批。比如，10個工件，可以分成4個子批，每個子批包含工件數為2，2，3，3。這樣會比完全等分批更有可能得到最優解。另外，該算法是確定了合理的分批數目之后再進行子批相關數據的計算，相比于計算每次分批之后的子批數據，大大減小了計算任務。

2 雙資源多目標調度算法

遺傳算法經常被用于解決車間調度問題，經典的遺傳算法雖然具有較好的全局優化求解能力，但當出現適應度很大的超常個體時，容易引起早熟收斂;而禁忌搜索算法通過引入禁忌表，避免迂回搜索，局部搜索能力強，彌補了遺傳算法的不足。

本文利用遺傳算法良好的全局搜索能力和禁忌搜索算法具有記憶能力的局部優化特性，將兩種算法進行混合［2］，用于解決雙資源多目標車間調度問題。先用遺傳算法進行全局搜索，通過遺傳操作，改善種群質量，再以該種群作為禁忌搜索算法的初始解，用禁忌搜索算法進行局部搜索，以在算法的全局收斂性能和避免早熟收斂方面有較大改善。

2．1 算法描述

算法流程如下:

Step 1:給定初始參數(包括最大迭代次數Y，群體規模s，交叉概率Pc和變異概率Pm);

Step 2:按照給定編碼方式編碼，產生初始群體，其中有s個染色體;

Step 3:按照給定的解碼方式解碼，得到每個個體的各優化指標，包括生產周期T1，T2，…，Ts，工件總延誤時間d1，d2，…，ds，設備閑置時間e1，e2，…，es和工人閑置時間w1，w2，…，ws;

Step 4:按照多目標決策理論計算群體中每個個體的適應度值f(x1)，f(x2)，…，f(xs);

Step 5:調用TS搜索過程，對群體中的每一個個體進行局部搜索，從群體中選擇r個較優解添加到禁忌表中作為禁忌對象。記各禁忌對象未被選擇的次數為Li(i=1，2，…，r)，如果Li大于禁忌長度L，將所對應個體釋放，轉Step 6;否則直接轉Step 6;

Step 6:根據交叉概率和變異概率對種群進行交叉、變異遺傳操作，得到新種群;

Step 7:如果循環次數y＜Y，令y=y+1，轉Step 3;否則轉Step 8;

Step 8:停止運算，從禁忌表中選擇確定數量的非劣解;

Step 9:使用層次分析法從非劣解集合中選擇較優解作為最終的調度方案。

2.2 遺傳編碼

采用基于工序的編碼方式。給同一工件的所有工序指定相同的符號，再根據它們在染色體中出現的順序進行解釋。例如，對于n個工件，每個工件有m道工序的問題，每個染色體由n×m個代表工序的基因組成，每個工件出現在染色體中m次。

以1個3工件，每個工件3道工序的問題為例，染色體的表達形式為211122333，其中第一個2表示工件2的第1道工序，第二個1表示工件1的第2道工序。

2．3 解碼

解碼即對編碼進行翻譯，產生具體可操作的工序安排方案。具體解碼過程是:

(1)假設所有工序的理想可被加工起始時刻:設備k可以使用的時刻Mk=0(k=1，2，…，m)，工人w可以使用的時刻Pw=0(w=1，2，…，p)，工件i的第一道工序可被加工時刻Ti1=0(i=1，2，…，n);

(2)從工序集合S中取出此刻排在第一位未被調度的工序Oij(工件i的第j道工序)，從能加工工序Oij的設備集合中挑選最先空閑的設備k，其可以使用的時刻為Mk，從能操作設備k的工人集合中挑選最先空閑的工人w，其可以工作的最早時間為Pw;

(3)工序Oij開始加工時刻Tb=max(Mk，Pw，Tij)，得到工序Oij的完工時刻fij=Tb+tij，其中Tij為工件i的第j道工序可被加工的時刻，tij為加工工序Oij所需的時間;

(4)如果j=Ji，則工件i的完工時間Fi=fij，否則Ti(j+1)=fij，且Mk=fij，Pw=fij，其中j=1，2，…，Ji，Ji為工件i的工序總數;

(5)檢查工序集合S中是否還有未被調度的工序，如有，轉(2)，否則，生產周期T=max(Fi)。

2．4 遺傳操作

(1)選擇本研究通過禁忌搜索算法保留相對優秀的個體，因此選擇操作將各個解的適應度值按順序排列即可。

(2)交叉采用循環交叉操作。循環交叉操作是將另一個父代個體作為參照，以對當前父代個體中的基因位置進行重組［3］。

例如，給定2個染色體p1，p2，如圖1所示。隨機選擇一個操作位置，如第2個位置，其對應的基因為6和5，則交叉過程為:首先選擇循環鏈6-5，5-7，7-1，1-3，3-8，8-6，如圖 1 所示。對應位置的基因交換后，生成新個體q1，q2，如圖2所示。

(3)變異采用逆轉變異法，即在染色體中隨機選擇兩點，然后將兩點間的基因以逆向排序插入到原位置中。如給定一個染色體p1，假設選中2號、5號位置，則變異后的染色體為q1，如圖3所示。

2．5 禁忌搜索算法參數確定

(1)禁忌對象和候選解的確定以遺傳操作后得到的種群作為禁忌搜索算法的候選解。禁忌對象是指那些被置入禁忌表中的變化元素，禁忌的目的是為了盡量避免迂回搜索。本算法將候選解中最優的40%作為禁忌對象，置入禁忌表中。

(2)禁忌長度的確定禁忌長度是禁忌對象在不考慮藐視準則的情況下允許未被選取的最大次數。禁忌長度根據不同的初始種群大小依據經驗選取不同值。本文中禁忌長度隨著種群規模的增大而增大。當某禁忌對象未被選取的次數達到禁忌長度值時，將該禁忌對象相對應的染色體釋放，參與遺傳操作，以避免產生局部最優。

3 多目標決策理論在算法中的應用

多目標決策理論的基本問題是研究如何在有多個相互沖突的決策準則(因素、目標、目的)下進行科學和有效地決策。層次分析法是20世紀70年代由美國學者薩蒂提出的一種多目標評價決策方法。其基本思路是決策者將復雜問題分解為若干層次和若干要素，在各要素間進行簡單的比較、判斷和計算，以獲得不同要素和不同待選方案的權重，從而為選擇最優方案提供決策依據。

在多目標車間調度問題中利用多目標決策理論，首先要確定各個目標的權重系數，然后對各個優化目標做無量綱化處理，確定目標函數。最后再根據層次分析法由非劣解集合求出較優解。

3．1 計算各目標權重系數

根據生產車間的具體情況，確定目標之間的相對重要性。目標比較的尺度分為5個等級:同樣重要、稍微重要、明顯重要、強烈重要與極端重要。對應的隸屬函數分別為s1、s2、s3、s4、s5，如圖 4 所示。

本研究的車間調度問題中，優化目標為生產周期、工件總延誤時間、設備閑置時間和工人閑置時間。對這些目標兩兩比較，重要性較小的數為1。

假設根據生產需要，確定各個目標重要程度如表1所示。以重要度級別的隸屬度函數作為隨機數的概率密度函數，按照概率分布產生隨機數分別代替重要度級別，得到目標比較矩陣表2。

把目標比較矩陣表2的每一元素除以其相應列所有元素的總和，得到標準兩兩比較矩陣，根據對比平均法［4-5］，再把標準兩兩比較矩陣各行元素相加并取平均值得到各目標的權重:生產周期權重ω1=0.374 3，工件總延誤時間權重ω2=0.284 1，設備閑置時間權重ω3=0.189 7，工人閑置時間權重ω4=0.151 9。

表1 目標比較矩陣

表2 用隨機數代替重要度級別得到的目標比較矩陣

3．2 計算目標函數值

在車間調度問題中，計算各指標值后，為把多個指標值集合成作為調度結果衡量標準的函數，需要對調度方案的各指標值按下列公式進行無量綱標準化處理:

標準化處理后，一個調度結果所對應的生產周期，工件總延遲時間，設備閑置時間和工人閑置時間分別表示為f1(x)、f2(x)、f3(x)、f4(x)，f(x)為衡量調度結果綜合指標的目標函數，因為各單項指標均是求極小值，則按照線性加權和方法得到目標函數為:

此目標函數即為遺傳算法的適應度函數。

3．3 獲得非劣解集合和較優解

在優化算法的計算過程中，可以獲得和保留非劣解。本文采用禁忌搜索算法實現。

獲得非劣解集合后，根據層次分析法由非劣解集合中獲得較優解。

根據目標比較矩陣表1，按照1-5標度法生成層次分析法的層次比較矩陣表3，然后把層次比較矩陣表3的每一元素除以其相應列所有元素的總和，得到標準兩兩比較矩陣，再把標準兩兩比較矩陣各行元素相加并取平均值就得到各目標的權重:生產周期權重ω1=0.449 5，工件延誤時間權重ω2=0.259 6，設備閑置時間權重 ω3=0.170 7，工人閑置時間權重 ω4=0.120 2。則各個目標權重系數矩陣為U=［0.449 5 0.259 6 0.170 7 0.120 2］T。