基于啟發(fā)式模糊評價算法的配合加工調度問題研究

馬劍

（廣州萬寶集團冰箱有限公司研究所，廣東廣州510935）

企業(yè)管理

基于啟發(fā)式模糊評價算法的配合加工調度問題研究

馬劍

（廣州萬寶集團冰箱有限公司研究所，廣東廣州510935）

配合加工是許多離散型制造企業(yè)中常用的加工方法，它增加了生產調度的約束條件，使得車間調度的難度進一步加大。為解決這一難題，使用啟發(fā)式模糊綜合評價算法對工件工序優(yōu)先級次序和工序在不同加工設備的優(yōu)劣進行多目標的評價，使得調度問題在配合加工約束下達到多目標的優(yōu)化。通過實例計算，證明了算法的有效性和可行性，具有實際應用價值。

配合加工；啟發(fā)式模糊綜合評價；多目標調度；調度優(yōu)化

具有配合加工[1-2]工藝約束的車間作業(yè)調度問題源于實際工業(yè)生產線模型[3-5]。

配合加工工藝約束是幾個工件在某些工序需要裝配在一起進行加工的約束。由于配合加工工序的存在，使得Job-Shop調度問題中，尋找最佳的工作排序，變得更加復雜。因此，根據(jù)實際需要尋找可行的、滿足要求的近似解[6]，就更為重要。

文中，綜合考慮多目標約束[7]和配合加工車間調度的特點等，建立問題的數(shù)學模型，提出了啟發(fā)式模糊評價算法，并用實例驗證調度結果的有效性。

1 配合加工調度問題的數(shù)學模型

在Job-shop多機生產系統(tǒng)中，加工操作一次針對一批工件i的一個工序j，車間配有m臺機器設備，每臺設備Mk可實現(xiàn)若干個操作。假設：（1）工件自身的加工工序有順序約束，同時不同工件的加工工序也有約束關系（包括配合加工工件內部，基礎件與配合件之間的約束；配合加工工件之間和配合加工工件與普通件之間的約束）；（2）已知各工件的最早開始加工時間和最晚結束時間；（3）一臺設備只能完成一道工序；（4）工件工序在不同設備上的加工時長可以不相同；（5）工件的加工工序之間可以等待；（6）配合加工的工序可以在一臺設備上完成；（7）任何一道工序不可中途停止；（8）工件可由多臺設備完成加工，每臺設備上可有不同的作業(yè)順序。

為了描述方便，引入如下符號：BT（i，j）為約束條件下，工件i的第j道工序的最早開始加工時間；ET（i，j）為工件交貨期約束條件下，工件i的第j道工序的完工時間；T（i，j，k）為工件工序（i，j）在機器設備k進行加工時的正常加工時長；Mk為一批任務可選用的設備集，k∈[1，m]；jend為工件的最后一道工序；Di為工件i的交貨期；MH（（i，j）:（i’，j’））為工件工序（i，j）與（i’，j’）的配合加工屬性，若工件工序之間需要配合加工，則MH（（i，j）:（i’，j’））=1，否則MH（（i，j）:（i’，j’））=0，其中（i，j）≠（i’，j’）；RH（（i，j）:（i’，j’））為工序（i，j）與（i’，j’）的相關約束屬性，當RH（（i，j）:（i’，j’））=1時，表示工件工序（i，j）不遲于（i’，j’）完工。RH（（i，j）:（i’，j’））= 0時，表示工件工序（i，j）與（i’，j’）無相關約束。RH（（i，j）:（i’，j’））=-1時，表示工件工序（i，j）完工后，（i’，j’）才能開始加工；OC（i，j，k）為若工序j在加工設備k上，用T（i，j，k）時刻加工完畢，OC（i，j，k）=1，否則OC（i，j，k）=0；Ck為設備k上的加工費用；

根據(jù)以上描述，具有配合加工工藝約束的車間作業(yè)調度的目標函數(shù)為：

式（1）為模型的目標函數(shù)。式（2～12）為模型的約束條件：式（2）表示工件的完工時間應小于它的最長加工時長；式（3）表示可加工某道工序的設備數(shù)量應小于總設備數(shù)；式（4）表示在作業(yè)調度中存在配合加工工藝約束；式（5～6）表示工件內部工序的先后性約束；式（7）表示工件自身工序的順序性約束；式（8）表示工序完工時間應大于其加工時間；式（9）為工件的交貨期約束；式（10）為工件首道工序的開工時間約束；式（11）表示某臺設備的作業(yè)順序約束；式（12）為取值范圍。

2 基于啟發(fā)式模糊綜合評價算法

在配合加工工藝約束的生產調度問題中，每個工件的加工都對應著設備集合，因此在加工過程中，需要考慮機器設備能夠被均衡地利用。文中建立了啟發(fā)式模糊綜合評價算法，優(yōu)化了生產作業(yè)，使設備在最大使用率下，實現(xiàn)工件加工成本、加工時間最小。算法分為三個模塊：工序優(yōu)先級模塊，最優(yōu)設備模塊和可行解優(yōu)化模塊。工序優(yōu)先級模塊是根據(jù)生產任務對各工件的每道工序進行排序；最優(yōu)設備模塊是平衡多個目標要求，選擇最適合的加工設備；可行解優(yōu)化模塊是對調度作業(yè)中，各工序之間時間間隙的處理方法，使得在接近交貨期的條件下，盡可能的滿足評價指標的要求。

2.1 整體算法步驟

本文采用的啟發(fā)式模糊綜合評價算法，通過專家經驗對生產中的各個指標進行綜合評價，通過調整指標的權重可得到不同的可行解，增加了實際應用的可執(zhí)行性。決策者根據(jù)比較不同權重和指標下的可行解，進行選擇和動態(tài)調度。

整體算法步驟如下：

步驟1：導入生產任務（工件信息、交貨期、設備資源等）；

步驟2：剩余工序集合a初始化，將所有工序集導入a中；

步驟3：將集合a中各工件的首道待排工序導入初始化后的待排工序集合b，直至集合a為空時，結束；

步驟4：調用（2.2節(jié)中的）工序優(yōu)先級模塊，為待排工序集合b中的各工序進行優(yōu)先級排序；

步驟5：判斷集合b中最優(yōu)先的工序是否屬于配合加工工件，若是，則將相應的配合件的工序合并排序；若不是，則判斷下一級工序；

步驟6：從待排工序集b（包含合并的配合加工工序）中選取優(yōu)先級最高的工件的工序；

步驟7：調用（2.3節(jié)中的）最優(yōu)設備模塊，為工序選擇多目標條件下的最適合加工設備；

步驟8：將已排產的工序從剩余工序集a中刪除；

步驟9：判斷，若剩余工序集a不為空，則回到步驟3；若a為空且b也為空，則排序結束；若a為空且b不為空，則從待排工序集b中刪除已排工序回到步驟5；

步驟10：判斷，若ET（i，j）＜Di則調度結束；若ET（i，j）＞Di則轉入（2.4節(jié)中的）可行解優(yōu)化模塊，對調度解進行優(yōu)化。

2.2 工序優(yōu)先級模塊

配合加工工藝是為了保證工件之間裝配精度的加工方法，配合加工的車間調度問題，增加了工件在某些工序需要同時加工的工藝約束和時間約束，使得調度解的求解難度加大。

本文使用模糊綜合評價法，通過調用專家經驗和多指標評價，避免了個人因素的片面性。同時設立的多目標決策，提高了調度解的可行性。

工序優(yōu)先級處理模塊算法如下：

步驟1：計算待排工序集合b中，每個工件的交貨期松弛量slacki，配合加工的次數(shù)PHi，剩余工序的最長加工時間T~i，剩余的工序步數(shù)J~i；

其中，

步驟2：對于拖期工件，若slacki＜0，則返回調整作業(yè)任務；若slacki＞0，則進入下一步。

步驟3：運用模糊綜合評價[8]進行優(yōu)先級排序

①確定評價對象集U=（U1，U2，…，Un）和評價指標集V=（V1，V2，…，Vm）；

②根據(jù)評價指標集V在評價對象集U上的映射關系，得到評價矩陣R；

③對第②步矩陣R中的數(shù)據(jù)進行歸一化處理，公式如下：

④采用層次分析法[9]，確定各評價指標權重W；

⑤計算各工序的綜合評定向量Bij，即Bij=W○Rij；

⑥根據(jù)向量集Bij中bij值的大小確定對應的工序的優(yōu)先程度。

步驟4：將工序按優(yōu)先級順序放入集合bˉ中。2.3最優(yōu)設備模塊

根據(jù)工序優(yōu)先級模塊算法，求解出待排工序的優(yōu)先級，按優(yōu)先級順序評價工件工序在不同設備上的多個指標，從而選擇多目標條件下的最優(yōu)加工設備。

最優(yōu)設備模塊算法步驟如下：

步驟1：從待排工序集b中提取優(yōu)先順序最前的工序；若存在配合加工約束且是基礎件，則搜索待排工序集b或剩余工序集a中的配合件工序，并將該工序排產，從集合b或集合a中刪除基礎件與配合件的工序；若工序不存在配合加工約束，則進入下一步操作（注：基礎件為在車間配合加工的幾個工件中，最小交貨期松弛變量，最多配合加工次數(shù)，最長加工總時間，最多工序數(shù)的工件；配合件為在車間配合加工的幾個工件中，基礎件以外的配合加工工件）。

步驟2：比較排產工序在可用加工設備（工序可由多臺設備完成）上生產的成本、時間和設備當前的使用率。

步驟3：運用模糊綜合評價方法對步驟2中的指標進行評判。工序的綜合評定向量Bij中選擇最小的bijk值，k值對應的即是優(yōu)選設備。

步驟4：記錄排產工序及最優(yōu)加工設備的信息。

步驟5：待排工序集b中刪除已排產工序，并將該工件的下一道工序導入集合b，然后再次運用工序優(yōu)先級模塊判斷集合b中各工序的先后順序。

2.4 可行解優(yōu)化模塊

對于復雜工件的車間生產調度，由于調度過程中約束條件的復雜性，可能存在著較大的優(yōu)化空間。最理想的調度解形式應為在任務甘特圖中零件的各工序可緊湊地排列，而在實際調度結果中各工序之間往往存在或大或小的間隙，這種間隙是由以下3類約束[4]所致：

（1）工藝關系約束：包括前驅工序約束和具有配合加工特性的工序約束：這是生產調度時需要首先考慮的內容。

（2）設備資源約束：包括加工設備約束和設備加工能力約束，即對某工序能夠加工的設備約束和設備能夠開始加工該工序的時間約束，該約束同時是與對該設備進行操作的工人技能水平聯(lián)系在一起的。

（3）調度時間約束：包括開始時間約束和指定工時約束，由于實際生產過程受很多不確定因素的影響（如設備失效、刀具卡具損壞、外協(xié)任務的變化等），為了將這些因素反映到調度系統(tǒng)中，需動態(tài)約束加工工序的開始時間和加工工時。

本文針對配合加工工藝約束和設備約束作出了不同間隙的處理方法，調度時間約束完全由外部因素所致因此無法通過程序縮短間隙，只能通過人機交互的方式動態(tài)更改。在啟發(fā)式模糊綜合評價算法調度結果上進行的調度解優(yōu)化可以彌補本算法在對眾多復雜工件調度過程中的不足，在滿足各類約束前提下盡量壓縮工序間的間隙，使工序更加緊湊，調度解更為優(yōu)化。

基于這樣的思路，針對配合加工生產的特點可將評價指標歸結為4點：所有任務的平均拖期懲罰、所有任務的最大拖期時間、所有任務的平均加工成本以及所有設備的平均利用率。

（1）平均拖期懲罰（Gav）計算公式為：

式中ti為第i個工件的拖期時間，Zi為第i個工件的拖期懲罰因子，n為所有的工件數(shù)。平均拖期懲罰從調度任務的緊急程度上表達了不同調度方案的優(yōu)劣，該指標越大則調度方案越差。

（2）最大拖期時間（tmax）的計算公式為：

tmax=max{ET（i）–Di）}

最大拖期時間代表了車間生產能力和交貨信用度，該指標越大則調度方案越差。

（3）平均設備利用率的計算公式為：

（OEE）

該指標越大則調度方案越好。

（4）平均加工成本（C）的計算公式為：

該指標從調度任務的生產費用上表達了不同調度方案的優(yōu)劣，該指標越大則調度方案越差。

3 實例分析

車間生產任務有8個工件（1～8）需要排產，各個工件可在加工設備集M（M1～M5）中，找到滿足要求的一臺或多個設備進行生產。加工中，存在以下配合工序約束{（1，3），（2，3）}，{（3，3），（4，2）}，{（5，2），（6，3）}，{（6，5），（7，5）}。所有配合工序的工件需全部完成前一工序后，方排產配合工序。相關費用，交貨期，設備能力如表1、表2、表3所示。

表1 機床加工費用

表2 工件交貨期

表3 工序可用機器設備及加工時間

以工件的首道工序為例，步驟如下：

（1）將每個工件的全部工序導入初始化后的集合a中；

（2）若集合a為空，則結束排產；若集合a不為空，則將a中所有工件的首道工序調入待排工序集合b中；

（3）應用工序優(yōu)先級模塊排序：

①以待排工序集b中的所有工序為評價對象，

以1/slacki，T~i，J~i，PHi為評價指標；

②建立評價矩陣Rij.

③對②中矩陣R11中的數(shù)據(jù)進行歸一化處理，按公式（2～1）求得：

④構建判斷矩陣。由專家將評價指標兩兩比較，得到相對重要度的評判矩陣，如圖1.

圖1 判斷矩陣

⑤計算判斷矩陣的特征向量和最大特征根，

W=（W1，W2，W3，W4）=（0.519，0.226，0.158，0.097），λmax=4.250 8；對上述結果進行一致性檢驗，CR=CI/RI=0.083 6/0.9=0.08＜0.1，滿足要求。

⑥計算各工序的綜合評價向量Bij. b81）=（0.087，0.086，0.091，0.158，0.161，0.131，0.137，0.147），根據(jù)向量比較，工序（5，1）為最高優(yōu)先級的工序。

（4）最高優(yōu)先級工序，若是基礎件則查找集合a中是否存在它的配合件的配合加工工序，若存在，則將兩工序合并排序，并調用最優(yōu)設備模塊；若不存在，就直接進入最優(yōu)設備模塊。

（5）調用最優(yōu)設備模塊選擇最適合的加工設備

按照（3）中①～⑥步驟，以設備集M中可加工該工序的各個設備為評價對象，以加工時間v1，加工成本v2，設備使用率為評價指標。建立評價矩陣R，由層次分析法得到權重W=（0.123，0.557，0.320），應用模糊理論的綜合評價規(guī)則，計算工件每一道工序的綜合評定向量Bijk，例如：

B31k=W●Rij=（b511，b512，b513，b514）=（0.277，0.274，0.275，0.175），根據(jù)最大隸屬原則，M4為工序（5，1）的最優(yōu)加工設備。

按最大隸屬原則，向量組中最大向量對應的設備即為最優(yōu)的加工設備。

（6）將已排產工序（5，1）從集合a中刪除。判斷，集合a若不為空，返回步驟（2）；若集合a為空，判斷集合b為空，則結束排產；若集合b不為空，則將已排產工序從集合b中刪除，返回步驟（4）；

（7）判斷，若ET（i）＜Di則調度結束；若ET（i）＜Di則轉入可行解優(yōu)化模塊進行優(yōu)化。

通過上述算法，得到實例的調度甘特圖，如圖2所示。

圖2 調度甘特圖

4 結束語

本文所述的啟發(fā)式模糊綜合評價算法，將車間調度作業(yè)問題，分為三個模塊進行處理，有效的發(fā)揮了模糊綜合評判規(guī)則和優(yōu)先分配啟發(fā)式調度算法的優(yōu)點，較好地解決了配合加工約束下的車間調度問題，具有可行性和實用性。對于模糊綜合評判的參數(shù)選取、權重的設定，啟發(fā)式算法中的規(guī)則選取，以及相互之間的結合，還將作進一步的研究。

[1]馬劍.考慮配合加工的車間制造資源配置與作業(yè)調度的算法研究[D].廣州：廣東工業(yè)大學，2008.

[2]趙寧，吳超，寧汝新，等．面向配做的柔性生產線調度[J].機械工程學報，2005，41（7）：180-185.

[3]趙詩奎，王林瑞，石飛.作業(yè)車間調度問題綜述[J].濟南大學學報（自然科學版），2016，30（1）：74-80.

[4]雷建平，袁剛，袁細發(fā).單親遺傳算法與流水作業(yè)優(yōu)化[J].武漢理工大學學報（交通科學與工程版），2004，28（4）：593 -596.

[5]Ma，J.，Wu，Y.M.，Jiang，L.L.，&Liu，Y.（2008）.Research on Allocation of Resources based on reconfigurable manufac turing system[C].Frontiers in Enterprise Integration Xian Inter national Symposium，IFISF and IFIP TC 8.9 International Con ference on Research and Practical Issues of Enterprise Informa tion Systems，CONFENIS 2007，2008，（161-169）.

[6]王柏琳，李鐵克.啟發(fā)式算法求解等待時間受限的兩階段流水車間調度問題[J].管理工程學報，2014（2）：182-190.

[7]馬劍.基于訂單的多任務廠多目標決策的生產作業(yè)算法研究[J].裝備制造技術，2010（7）：115-119.

[8]付微，孟波.一種模糊多目標群決策方法[J].系統(tǒng)工程與電子，1996（12）：8-13.

[9]Yurdakul M.AHP as a strategic decision-making tool to justify machine tool selection[J].Mat.Proc.Tech.，2004，146：365-376.

Heuristic Fuzzy Evaluation Algorithm of Job-Shop Scheduling in Consideration of Matching Machining Process

MA Jian
（The R&D Center of Guangzhou Wanbao Group Refrigerator Co.，Ltd.，Guangzhou Guangdong 510935，China）

Matching production is a machining method used in many discrete manufacturing enterprises.scheduling restriction is added by this method and scheduling is made more difficult.In order to resolve this problem，a heuristic scheduling algorithm combing the fuzzy decision-making method is presented，which is used to realize the optimal equilibrium between the multiple objectives of matching machining process.An example is illustrated to verify the effectiveness and feasibility of the model proposed in this paper.

matching machining process；heuristic fuzzy comprehensive evaluation；multi-objective scheduling；scheduling optimization

TH162

A < class="emphasis_bold">文章編號：1

1672-545X（2017）05-0255-05

2017-02-09

馬劍（1980-）男，河南鄭州人，機械工程師，工學碩士，研究方向：先進制造技術。