模糊交貨期條件下的IPPS問題研究

馬 靜，李 言

（西安理工大學 機械與精密儀器工程學院，西安 710048）

0 引言

工藝規劃和車間調度兩個子系統在制造系統中具有重要的功能。工藝規劃通過對產品工藝路線進行不斷規劃和改善，在不同的生產狀況下，選擇不同的工藝方案，來提高產品的生產效率和制造的柔性；車間調度對工件的加工順序和資源利用進行合理分配，避免資源利用的沖突，以獲得最優的調度結果。研究表明，將工藝規劃和車間調度進行集成（Integrated Process Planning and scheduling，IPPS），可以克服二者獨立運行時存在的效率低、目標沖突及規劃與實施的過程中存在時間差等問題[1,2]。

Chrssolouris[3]首次提出將工藝與車間調度進行集成規劃。Beckendorf[4]用可選工藝路線來增加系統的柔性。Khoshnevis[5]動態反饋的思想引入到工藝規劃與車間調度集成之中，從而將動態調度和工藝規劃有機地結合在一起。Zhang[6]Larsen[7]繼承可選工藝路線和動態反饋思想的同時，采用分層規劃的思想進行生產調度研究，并首次提出了面向功能的IPPS的集成。呂盛坪、喬立紅[8]在工藝規劃和車間調度的集成過程中，提出一種結合了面向接口與面向功能集成的復合式集成模型。

目前，研究人員對IPPS問題進行了諸多研究，但大多數都是基于確定條件下進行的，而在實際的生產加工過程中，存在諸多不確定因素，如：加工時間、交貨期等，都會對調度的柔性和靈活性產生很大的影響。很多研究人員針對車間調度不確定因素進行了具體研究，引入區間數、隨機數和模糊數等來表征這些不確定[9]Ishii[10]等針對開環車間的雙機調度問題以及同型機的調度問題，首次將交貨期看作模糊數，解決了在模糊交貨期環境下基于不同目標函數的調度問題。Cheng[11]首次把交貨期窗口的概念應用到提前/拖期調度問題中。徐新黎等[12]考慮紙盆車間調度中的不確定因素，通過構建的多智能體免疫算法，找到最優調度決策。劉明周等[13]采用模糊隨機變量表示廢舊件加工時間，利用混合優化算法解決制造加工車間最優調度問題。劉曉冰等[14]提出混沌量子粒群算法解決模糊環境下柔性作業車間調度問題。王春等[15]采用混合機器分配和工序排序策略，解決工序加工時間不確定的多目標調度問題。張銘鑫等[16]基于可信性測度的模糊變量表示再制造零部件的裝配時間，建立模糊機會約束規劃調度模型，通過混合智能優化算法求解該模型。彭運芳等[16]利用改進的遺傳算法，用三角模糊數表示產品的處理時間，解決了生產調度問題，并且驗證了算法的可靠性。

綜上所述，目前對于模糊交貨期的研究，大多針對單機或多機問題，很少考慮工藝路線和設備的柔性。對于交貨期而言，一般都假設交貨期為確定值。隨著JIT（準時制）的發展，客戶對工件的提前/拖期問題的關注度日益增強[17,18]。在實際的生產過程中，隨著市場的不斷變化，以及顧客需求的多樣化，將交貨期視為一個固定值已無法滿足顧客的需求，將其考慮為一定范圍內的不確定因素更加符合實際生產情況，更有利于提高顧客的滿意程度和企業生產的效益[19,20]。因此，本文將在已有研究的基礎上，考慮IPPS問題中交貨期的不確定性，提出一種梯形模糊數表示工件的交貨期；以工件的交貨滿意度加權之和最大以及最大完工時間最小為優化目標，建立集成優化模型，并設計相應的求解算法；最后，以實例對模型和算法進行驗證。

1 IPPS問題描述

確定條件下的工藝規劃與車間調度集成的問題描述：n個工件在m臺設備上進行加工，每個工件有多條可選的工藝路線，每條工藝路線又有k臺設備，其中部分設備可以進行替換。根據特定的目標，在考慮車間資源、工件工序等約束條件下，通過集成調度，最終選出最優的工藝路線和作業車間調度順序。為了更好地描述IPPS問題并建立合適的數學模型，可對該問題做如下假設：

1）每個設備在同一時刻只能加工一道工序；

2）設備的初始狀態均為空閑，且在零時刻，任意任務都是可行的，并且無設備故障，加工不會出現中斷；

3）同一零件的不同工序不能同時被加工；

4）所有工件在加工過程中沒有優先級，彼此之間相互獨立；

5）任務在機器上執行的時間事先已知；

6）所有工序的準備時間均包含在工件的加工時間內，且與工序的加工順序沒有關系；

本文將在確定條件下的IPPS問題中，考慮交貨期的不確定性，用梯形模糊數來表示工件的交貨期；進而在該模糊環境下，進行問題的建模和算法設計。

2 問題建模

2.1 參數設定

為了方便建立工藝規劃與車間調度集成的數學模型，設定參數如下：

n：表示工件數目；

J：工件集合；

Ji：表示第i個工件，i =1，2，…，n；

Qi：表示工件Ji所有可能的工藝路線的數量；

Rij：表示工件Ji的第j條可行的工藝路線，j=1，2，…，Qi；

Oij：表示工藝路線Rij的所有工序數目；

Oijp：表示工件Ji的第j條工藝路線的第p道工序；

Sijpk：表示工序Oijp在設備k上的開始加工時間；

Tijpk：表示工序Oijp在設備k上的加工時間；

Cijpk：表示工序Oijp在設備k上最早完工時間；

Ci：表示工件Ji的完工時間；

Cimax：表示工件Ji的最大完工時間；

2.2 不確定交貨期的表達

準時制生產過程中，零件的提前和拖期，都會給企業和產品客戶帶來很多問題。零件的提前完工將會導致企業資金的不必要占用和庫存費用的升高等問題。零件的拖期完工，將會導致有關合同的違約懲罰和失去顧客信譽，也會在一定程度給客戶帶來巨大損失。

對于確定時間條件下的交貨期，有時不能滿足實際需求。因此將其視為不確定因素，顯得很有必要。可在滿足企業和客戶需求的同時，將固定交貨期值設置在一定范圍內，這樣有利于提高調度的靈活性，對企業和客戶而言，都比較經濟和科學。因此本文選擇用梯形模糊數來表示零件的交貨期。圖1所示為梯形模糊交貨期的線性隸屬函數圖。

圖1 梯形模糊交貨期的線性隸屬函數

如圖1所示，若工件在交貨期[d2，d3]加工完成，則其滿意度為1，不受懲罰。對于在交貨期之外加工完成，其滿意度將會小于1且呈線性變化，工件的提前和拖期懲罰根據實際情況而定。文中工件的完工滿意度用線性隸屬函數來表示，用μ（Ci）表示工件Ji的隸屬函數，如式(1)所示。

2.3 模糊交貨期條件下的IPPS問題建模

讓工件在多條柔性的工藝路線中選擇合理的工藝路線和合理的設備，并以所有工件的交貨滿意度加權之和最大而且所有工件的最大完工時間（Makespan）最小為目標，建立目標函數及相應約束條件。所有工件的交貨滿意度加權之和最大用公式表示如下：

公司所加工的工件，其面對的客戶不盡相同，其重要程度也不一樣，權重就不同。wj為工件J的權重，用來表示工件的重要程度。工件在加工過程中所要滿足的約束條件如下：

1）每個工件在加工過程中只能選擇一條工藝路線；

2）每個工件的每道工序只能選擇一臺設備進行加工；

3）同一工件的不同工序不能同時加工；

4）當工件Ji的工序Oijp1在Oijp2之前加工，要使同一機器在同一時刻只能加工一道工序，則應滿足：

5）針對工件Ji的第l條工藝路線的第一道工序；

6）針對工件i的第l條工藝路線的最后一道工序；

7）所有工序的加工時間均大于等于0；

3 算法求解

本文求解IPPS問題的關鍵就是：在共同約束條件、目標函數和優化環境下，如何將工藝規劃和車間調度集成在一起，并將模糊交貨期考慮在內，最后求解出近似最優解。針對交貨期不確定條件下的IPPS問題，本文采用一種多層編碼結構的遺傳算法。下面將對該算法的編碼、選擇、交叉和變異操作進行具體說明，并給出算法的具體流程圖。

1）編碼

本文采用一種四層編碼結構的遺傳算法。其各層分別為：工件層、機器層、加工時間層和工藝路線層。

工件層：各工件的編碼；

機器層：各個機器的編碼；

加工時間層：各個工件的不同工序在機器上的加工時間；

工藝路線層：不同工件所選的工藝路線。

本文采用多層編碼結構將工件、機器、加工時間和工藝路線聯系在一起。這里以3個工件、6條工藝路線、4臺機器為例對算法進行進一步的說明。

表1 編碼示例

表1中的編碼，對于工件層而言，如第一個位置的3可解釋為：第三個工件的第一道工序，第四個位置的3可解釋為：第三個件的第二道工序。對于第一列編碼，可表示為第3個工件選擇第5條工藝路線，其第1道工序在機器2上加工，加工時間為5。

2）適應度函數

遺傳算法通常用適應度函數來評估一個染色體相對整個群體優劣的相對值的大小。用適應度值的高低來決定其選擇概率的大小，適應度值越高，則被選中的概率越大[15]。本文中染色體的適應度函數參考目標函數。

3）選擇操作

選擇聯賽選擇法和精英選擇相結合的遺傳算法選擇機制。假設該遺傳算法的種群規模為N，聯賽個體選擇總數目為L（L＜N）。首先從當前種群中隨機性地選擇一定數量的個體，然后根據適應度函數，從中選出個體適應度值大的個體進行交叉、變異等操作。最后，比較下一代個體的適應度值和當代個體的適應度值大小，將最佳個體復制到下一代種群中，隨機替代下一代種群中相應數量的個體。

4）交叉操作

交叉就是指染色體基因之間的一種互換過程，種群中每一代個體之間按一定的交叉概率進行基因的交換，從而產生新個體。本文采用一種優先交叉策略，對個體進行交叉，以避免其產生非法解。以工件層的工件3為例進行說明，其它層隨著工件層同時發生交叉，其交叉示例如下所示：

父代1：（3 2 2 3 1 3 1）

父代2：（2 3 2 1 3 1）

子代1：（3 2 2 3 1 1）

子代2：（2 3 2 1 3 1 3）

在不同的父代染色體中，由于工件所選擇的工藝路線不同，而每條工藝路線所對應的工件工序數目也不盡相同，則導致染色體進行交叉操作后，其子代染色體的長度發生變化，基因個數也就不同。

5）變異操作

變異操作就是從種群中隨機選擇個進行變異操作，本文選擇基于鄰域搜索的變異操作。本文以染色體工件層為例進行具體說明，其交叉步驟如下：

步驟一：從父代染色體中選擇n個基因，其中每個基因必須選擇不同的值。文中n取3，并選擇基因位置1、位置2、位置5。

步驟二：采用適應度函數評價所有的鄰域染色體，從中選擇最優的個體作為其子代染色體。

父代個體：（3 2 2 3 1 3 1）

鄰域染色體：（1 2 2 3 3 3 1）

（1 3 2 3 2 3 1）

（2 1 2 3 3 3 1）

（2 3 2 3 1 3 1）

（3 1 2 3 2 3 1）

個體通過變異后，其所對應的工藝路線、加工時間和機器都會發生變化，從而產生不合理解。這時可將產生不合理解的工件重新取出來，并將其匹配合理的工藝路線、機器和時間。以第一條鄰域染色體為例進行具體說明。

其工件3的加工順序發生變化，產生了不合理解。這時可將父代染色體工件3所在的列提取出來，將其復制到鄰域染色體中工件3所在的位置上。

表2 父代染色體

表3 第一條領域染色體

表4 修正后的領域染色體

對機器層進行變異：從機器層中隨機產生變異位置，假設該變異發生在位置6上，然后對其匹配正確的加工時間，則可得到新的子代。其變異結果如表5所示。

表5 器層變異后的領域染色體

其他鄰域染色體同樣根據上述過程進行變異操作，然后比較，選出最優的個體。根據上述描述，可得到該IPPS問題的遺傳算法流程圖，如圖2所示。

圖2 交貨期不確定條件下的遺傳算法流程圖

其中N為種群規模，T為迭代次數，Pc為交叉概率，Pm為變異概率。

4 實例仿真

某企業要生產一批軸類零件，該批零件共包括三種工件，圖3和表6分別為工件1的可選加工路線以及每道工序可選機器及其加工時間，圖4和表7分別為工件2的可選加工路線以及每道工序可選機器及其加工時間，圖5和表8分別為工件3的可選加工路線以及每道工序可選機器及其加工時間。

1）工件參數

圖3 工件1可選工藝路線

表6 工件1每道工序可選機器及其加工時間

圖4 工件2可選工藝路線

表7 工件2每道工序可選機器及其加工時間

圖5 工件3可選工藝路線

表8 工件3每道工序可選機器及其加工時間

2）算法求解結果及其分析

按照式(1)～式(9)，可以建立實例對應的模型。求解過程中，設置的初始參數如下：種群規模N=100，迭代次數G=200，交叉概率Pc=0.9，Pm=0.05。機器層變異概率為0.5。根據上述算法，搜索出最優的車間作業調度順序。圖6為模糊交貨期算法迭代圖，圖7顯示模糊交貨期下每個工件的調度順序。

每個工件分別用不同的形式來表示，工件1、2、3的完工時間分別為11min、12min、13.5min。所有工件的最大完工時間為13.5min，所有工件的滿意度加權之和最大為0.75。

圖6 模糊交貨期下的算法迭代圖

圖7 模糊交貨期下的調度甘特圖

如果將交貨期考慮為一固定值，假設工件1、2、3的交貨期分別為11min、10min、14min。在滿足目標條件的情況下，決策出最優的調度順序。圖8所示為確定交貨期下算法迭代圖，圖9所示為確定交貨期下的調度甘特圖。工件1、2、3的完工時間分別為12min、13min、14min。所有工件的最大完工時間為14min，所有工件的滿意度加權之和最大為0.33。

與確定交貨期條件下的IPPS相比，通過使用梯形模糊數來表示工件的交貨期，在一定程度上不僅有利于制造商合理安排生產計劃，為公司提高經濟效益，也可盡可能地滿足顧客的需求，在交貨期范圍內，使其最大程度地完成工件的加工。如果是確定交貨期條件下的IPPS問題時，其交貨期為一固定值，相比模糊交貨期而言，其最大完工時間變大，顧客滿意度值也有所降低。

圖8 確定交貨期下算法迭代圖

圖9 確定交貨期下的調度甘特圖

5 結束語

針對工藝規劃和車間調度中的交貨期不確定問題，本文引入梯形模糊數來表示工件的交貨期。以所有工件的交貨滿意度加權之和最大而且所有工件的最大完工時間（Makespan）最小為目標函數，最后，采用基于多層編碼結構的遺傳算法決策出了最優的調度順序，并驗證了算法的有效性和可行性。并與交貨期確定條件下的IPPS相比，該研究更符合實際需求，亦可提高客戶的滿意度。該基于交貨期不確定條件下的IPPS問題研究，將會對實際的生產調度有著很大的指導作用和實際參考價值。

在生產制造過程中還存在很多不確定性，在以后研究中，可將其他不確定性因素與交貨期不確定聯系起來，使其更好地為實際所用。除此之外，不確定因素的表示方法還有很多，研究人員可選擇其他方法對此進行更深入的研究。