馬劍

（廣州萬(wàn)寶集團(tuán)冰箱有限公司研究所，廣東廣州510935）

企業(yè)管理

基于啟發(fā)式模糊評(píng)價(jià)算法的配合加工調(diào)度問(wèn)題研究

馬劍

（廣州萬(wàn)寶集團(tuán)冰箱有限公司研究所，廣東廣州510935）

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

配合加工；啟發(fā)式模糊綜合評(píng)價(jià)；多目標(biāo)調(diào)度；調(diào)度優(yōu)化

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

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

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

1 配合加工調(diào)度問(wèn)題的數(shù)學(xué)模型

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

為了描述方便，引入如下符號(hào)：BT（i，j）為約束條件下，工件i的第j道工序的最早開(kāi)始加工時(shí)間；ET（i，j）為工件交貨期約束條件下，工件i的第j道工序的完工時(shí)間；T（i，j，k）為工件工序（i，j）在機(jī)器設(shè)備k進(jìn)行加工時(shí)的正常加工時(shí)長(zhǎng)；Mk為一批任務(wù)可選用的設(shè)備集，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’）的相關(guān)約束屬性，當(dāng)RH（（i，j）:（i’，j’））=1時(shí)，表示工件工序（i，j）不遲于（i’，j’）完工。RH（（i，j）:（i’，j’））= 0時(shí)，表示工件工序（i，j）與（i’，j’）無(wú)相關(guān)約束。RH（（i，j）:（i’，j’））=-1時(shí)，表示工件工序（i，j）完工后，（i’，j’）才能開(kāi)始加工；OC（i，j，k）為若工序j在加工設(shè)備k上，用T（i，j，k）時(shí)刻加工完畢，OC（i，j，k）=1，否則OC（i，j，k）=0；Ck為設(shè)備k上的加工費(fèi)用；

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

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

2 基于啟發(fā)式模糊綜合評(píng)價(jià)算法

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

2.1 整體算法步驟

本文采用的啟發(fā)式模糊綜合評(píng)價(jià)算法，通過(guò)專家經(jīng)驗(yàn)對(duì)生產(chǎn)中的各個(gè)指標(biāo)進(jìn)行綜合評(píng)價(jià)，通過(guò)調(diào)整指標(biāo)的權(quán)重可得到不同的可行解，增加了實(shí)際應(yīng)用的可執(zhí)行性。決策者根據(jù)比較不同權(quán)重和指標(biāo)下的可行解，進(jìn)行選擇和動(dòng)態(tài)調(diào)度。

整體算法步驟如下：

步驟1：導(dǎo)入生產(chǎn)任務(wù)（工件信息、交貨期、設(shè)備資源等）；

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

步驟3：將集合a中各工件的首道待排工序?qū)氤跏蓟蟮拇殴ば蚣蟗，直至集合a為空時(shí)，結(jié)束；

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

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

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

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

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

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

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

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

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

本文使用模糊綜合評(píng)價(jià)法，通過(guò)調(diào)用專家經(jīng)驗(yàn)和多指標(biāo)評(píng)價(jià)，避免了個(gè)人因素的片面性。同時(shí)設(shè)立的多目標(biāo)決策，提高了調(diào)度解的可行性。

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

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

其中，

步驟2：對(duì)于拖期工件，若slacki＜0，則返回調(diào)整作業(yè)任務(wù)；若slacki＞0，則進(jìn)入下一步。

步驟3：運(yùn)用模糊綜合評(píng)價(jià)[8]進(jìn)行優(yōu)先級(jí)排序

①確定評(píng)價(jià)對(duì)象集U=（U1，U2，…，Un）和評(píng)價(jià)指標(biāo)集V=（V1，V2，…，Vm）；

②根據(jù)評(píng)價(jià)指標(biāo)集V在評(píng)價(jià)對(duì)象集U上的映射關(guān)系，得到評(píng)價(jià)矩陣R；

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

④采用層次分析法[9]，確定各評(píng)價(jià)指標(biāo)權(quán)重W；

⑤計(jì)算各工序的綜合評(píng)定向量Bij，即Bij=W○Rij；

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

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

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

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

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

步驟2：比較排產(chǎn)工序在可用加工設(shè)備（工序可由多臺(tái)設(shè)備完成）上生產(chǎn)的成本、時(shí)間和設(shè)備當(dāng)前的使用率。

步驟3：運(yùn)用模糊綜合評(píng)價(jià)方法對(duì)步驟2中的指標(biāo)進(jìn)行評(píng)判。工序的綜合評(píng)定向量Bij中選擇最小的bijk值，k值對(duì)應(yīng)的即是優(yōu)選設(shè)備。

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

步驟5：待排工序集b中刪除已排產(chǎn)工序，并將該工件的下一道工序?qū)爰蟗，然后再次運(yùn)用工序優(yōu)先級(jí)模塊判斷集合b中各工序的先后順序。

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

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

（1）工藝關(guān)系約束：包括前驅(qū)工序約束和具有配合加工特性的工序約束：這是生產(chǎn)調(diào)度時(shí)需要首先考慮的內(nèi)容。

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

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

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

基于這樣的思路，針對(duì)配合加工生產(chǎn)的特點(diǎn)可將評(píng)價(jià)指標(biāo)歸結(jié)為4點(diǎn)：所有任務(wù)的平均拖期懲罰、所有任務(wù)的最大拖期時(shí)間、所有任務(wù)的平均加工成本以及所有設(shè)備的平均利用率。

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

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

（2）最大拖期時(shí)間（tmax）的計(jì)算公式為：

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

最大拖期時(shí)間代表了車間生產(chǎn)能力和交貨信用度，該指標(biāo)越大則調(diào)度方案越差。

（3）平均設(shè)備利用率的計(jì)算公式為：

（OEE）

該指標(biāo)越大則調(diào)度方案越好。

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

該指標(biāo)從調(diào)度任務(wù)的生產(chǎn)費(fèi)用上表達(dá)了不同調(diào)度方案的優(yōu)劣，該指標(biāo)越大則調(diào)度方案越差。

3 實(shí)例分析

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

表1 機(jī)床加工費(fèi)用

表2 工件交貨期

表3 工序可用機(jī)器設(shè)備及加工時(shí)間

以工件的首道工序?yàn)槔?，步驟如下：

（1）將每個(gè)工件的全部工序?qū)氤跏蓟蟮募蟖中；

（2）若集合a為空，則結(jié)束排產(chǎn)；若集合a不為空，則將a中所有工件的首道工序調(diào)入待排工序集合b中；

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

①以待排工序集b中的所有工序?yàn)樵u(píng)價(jià)對(duì)象，

以1/slacki，T~i，J~i，PHi為評(píng)價(jià)指標(biāo)；

②建立評(píng)價(jià)矩陣Rij.

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

④構(gòu)建判斷矩陣。由專家將評(píng)價(jià)指標(biāo)兩兩比較，得到相對(duì)重要度的評(píng)判矩陣，如圖1.

圖1 判斷矩陣

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

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

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

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

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

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

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

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

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

（7）判斷，若ET（i）＜Di則調(diào)度結(jié)束；若ET（i）＜Di則轉(zhuǎn)入可行解優(yōu)化模塊進(jìn)行優(yōu)化。

通過(guò)上述算法，得到實(shí)例的調(diào)度甘特圖，如圖2所示。

圖2 調(diào)度甘特圖

4 結(jié)束語(yǔ)

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

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

[2]趙寧，吳超，寧汝新，等．面向配做的柔性生產(chǎn)線調(diào)度[J].機(jī)械工程學(xué)報(bào)，2005，41（7）：180-185.

[3]趙詩(shī)奎，王林瑞，石飛.作業(yè)車間調(diào)度問(wèn)題綜述[J].濟(jì)南大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，30（1）：74-80.

[4]雷建平，袁剛，袁細(xì)發(fā).單親遺傳算法與流水作業(yè)優(yōu)化[J].武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），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ā)式算法求解等待時(shí)間受限的兩階段流水車間調(diào)度問(wèn)題[J].管理工程學(xué)報(bào)，2014（2）：182-190.

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

[8]付微，孟波.一種模糊多目標(biāo)群決策方法[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">文章編號(hào)：1

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

2017-02-09

馬劍（1980-）男，河南鄭州人，機(jī)械工程師，工學(xué)碩士，研究方向：先進(jìn)制造技術(shù)。