考慮批量分割的虛擬單元調(diào)度研究

韓文民，吳滿成，王 潔，張信兵

（江蘇科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，鎮(zhèn)江 212003）

0 引言

虛擬制造單元[1]根據(jù)生產(chǎn)任務(wù)的相似性，將制造資源視為共享資源，既能保持成組技術(shù)加工柔性特點(diǎn)，又能保持流水線的生產(chǎn)性能。通過共享設(shè)備，虛擬單元能夠提供比成組單元更少的生產(chǎn)時間，在一個虛擬單元中，設(shè)備被靈活的分配至各零件或零件族進(jìn)行加工，但由于設(shè)備物理位置并不固定，因此，設(shè)備的這種邏輯重組能夠極大的降低生產(chǎn)成本和零件的加工時間。

目前關(guān)于虛擬單元調(diào)度的研究中，從虛擬單元調(diào)度建模角度講，K.Mertins[2]以最小資源能力能力占用時間、最小成本及設(shè)備準(zhǔn)備時間為目標(biāo)構(gòu)建混合整數(shù)模型，以控制虛擬制造單元生產(chǎn)能力分配；Erhan Kesen[3]針對不同加工路徑的多任務(wù)調(diào)度問題構(gòu)建了一個能夠?yàn)楦髟O(shè)備分配任務(wù)的模型；Saadettin Erhan Kesen， Sanchoy K.Das和Zulal Gungor[4]在動態(tài)環(huán)境下構(gòu)建了多目標(biāo)混合整數(shù)規(guī)劃模型以解決多路徑的虛擬單元作業(yè)調(diào)度問題，采用代數(shù)模型系統(tǒng)求解；Luis Pinto Ferreira，Enrique Ares Gomez，Gustavo Pelaez Lourido和Benny Thahjono[5]基于虛擬單元的概念，研究汽車制造業(yè)擁有四個閉環(huán)結(jié)構(gòu)的裝配線的離散項(xiàng)目，并用Arena進(jìn)行仿真。從虛擬單元調(diào)度目標(biāo)角度講，Hamed等人[6]以設(shè)備的調(diào)整時間和產(chǎn)品完工時間為目標(biāo)解決單元的復(fù)雜調(diào)度問題；白俊杰，龔毅光，王寧生和唐敦兵[7]以完工時間最小為調(diào)度目標(biāo)，研究了柔性制造單元的兩階段調(diào)度問題；Amit[8]以合理分配產(chǎn)品和設(shè)備至已有單元，提高設(shè)備利用率為目標(biāo)，針對不同單元內(nèi)產(chǎn)品組合變化采取不同策略性方法。從虛擬單元調(diào)度算法角度講，Saravanan M.和Nooral Haq,A.[9]采取分散搜索算法求解最小化完工時間調(diào)度，實(shí)驗(yàn)發(fā)現(xiàn)該方法對求解單元內(nèi)調(diào)度問題具有可行性；M.B.Aryanezhada，Jamal Aliabadi和Reza Tavakkoli-Moghaddam[10]采用遺傳算法求解了裝配性制造單元最小化裝配周期和單元間移動距離的調(diào)度問題；王雷[11]以總加工時間最小為目標(biāo)，以魯棒性較好的粒子群算法解決了敏捷制造系統(tǒng)自組織多級協(xié)調(diào)控制結(jié)構(gòu)模型。這些研究都很好的證明，在采取虛擬單元調(diào)度方式后，企業(yè)的生產(chǎn)效率能夠得到較為明顯的改善。

但是，在傳統(tǒng)的調(diào)度問題中，都是假設(shè)每項(xiàng)作業(yè)不可分，且各項(xiàng)作業(yè)的任意加工都必須在一臺設(shè)備上加工完畢后方能進(jìn)入下一臺設(shè)備進(jìn)行加工，而在實(shí)際生產(chǎn)中，如果一項(xiàng)作業(yè)包含多個相似操作，企業(yè)可以將其操作分成多個加工子批，將其在設(shè)備上不斷重復(fù)生產(chǎn)，以降低設(shè)備重置成本，提升生產(chǎn)效率。因此，有必要考慮虛擬單元調(diào)度中的批量分割問題。

目前在關(guān)于批量分割的研究中，Rahime[12]以啟發(fā)式規(guī)則解決了作業(yè)車間中多產(chǎn)品并行時的批量分割問題；Saricicek[13]研究了并行機(jī)批量分割問題，并用禁忌搜索算法予以求解；Taofeng Ye[14]將問題分為三類，研究了作業(yè)車間中轉(zhuǎn)移方式對最有批量的確定問題；Defersha[15]研究了單元生產(chǎn)中考慮批量分割的設(shè)計問題；Ahkioon[16]通過構(gòu)建非線性整數(shù)規(guī)劃模型，研究了考慮批量分割后單元生產(chǎn)系統(tǒng)的重構(gòu)問題。在當(dāng)前在車間調(diào)度、并行機(jī)調(diào)度與單元調(diào)度的研究中發(fā)現(xiàn)，采用批量分割能改善企業(yè)運(yùn)營效率。

本文將結(jié)合虛擬單元生產(chǎn)方式特點(diǎn)，構(gòu)建允許批量分割與不允許批量分割的多目標(biāo)混合整數(shù)規(guī)劃模型，通過結(jié)合批量分割的遺傳算法求解，以證明在虛擬單元調(diào)度中考慮批量分割能幫助企業(yè)生產(chǎn)取得更好的效果。本文的構(gòu)建思路如下：第一節(jié)將介紹批量分割，以及在虛擬單元調(diào)度中，采取批量分割時應(yīng)當(dāng)考慮的影響因素；第二節(jié)將介紹不考慮批量分割的虛擬單元調(diào)度模型與相關(guān)假設(shè)；第三節(jié)將介紹考慮批量分割的虛擬單元調(diào)度模型與相關(guān)假設(shè)；第四節(jié)將介紹考慮批量分割的遺傳算法及在虛擬單元調(diào)度中的求解過程；第五節(jié)將根據(jù)算例驗(yàn)證在虛擬單元調(diào)度中實(shí)施批量分割后，能否得到生產(chǎn)效果的改善；第六節(jié)是本文小結(jié)。

1 虛擬單元調(diào)度中的生產(chǎn)批量分割

1.1 批量分割

生產(chǎn)批量確定能夠決定系統(tǒng)表現(xiàn)[17]，因此批量大小的確定對生產(chǎn)計劃十分重要。批量分割指將生產(chǎn)中的大批量分割為子批量，從而使同一作業(yè)的各工序在具有相同加工能力的設(shè)備上重疊以重復(fù)生產(chǎn)。在批量分割的加工方式中，前一設(shè)備完成子批量的生產(chǎn)后，該子批無需等待其他子批生產(chǎn)結(jié)束即可進(jìn)入下一設(shè)備繼續(xù)生產(chǎn)，從而能有效降低系統(tǒng)在制品庫存與最早完工時間，也能夠降低設(shè)備布置成本。雖然采取這樣的生產(chǎn)方式會增加作業(yè)的加工流程時間，但由于該方式允許工序重疊，所以能夠更快速的滿足生產(chǎn)交貨期。批量分割有橫向分割與縱向分割的分割方式。橫向分割指同一作業(yè)的不同子批在連續(xù)加工的設(shè)備中同時加工，產(chǎn)生工序重疊的加工現(xiàn)象，縱向分割指同一作業(yè)各工序在具有相同加工能力的相似設(shè)備或同一類設(shè)備中的加工現(xiàn)象。雖然子批的生產(chǎn)重疊能夠滿足交貨期，但子批數(shù)量的增加會影響的增加系統(tǒng)運(yùn)輸成本，并影響到相關(guān)設(shè)備的分配。因此，批量分割生產(chǎn)方式需要解決設(shè)備的分配問題，合理確定子批大小并確定設(shè)備的加工順序與子批種類，以使虛擬制造單元內(nèi)設(shè)備的負(fù)荷均衡，獲得虛擬單元生產(chǎn)方式的最大利潤。以A(B)（AN*，B N*）表示設(shè)備類型為A的第B臺設(shè)備，圖1所示為批量分割示意圖，圖2所示為縱向分割批量分割方式工藝路線圖，其中，圖1設(shè)備1(1)，1(2)與1(3)屬于同一設(shè)備，設(shè)備2與設(shè)備3,4屬于具有某種相同加工能力的相似設(shè)備，子批1與子批2和3屬于由同種類型設(shè)備存在多臺設(shè)備引起的批量分割，子批1與子批4，子批2與子批5和子批3與子批6屬于同一產(chǎn)品各工序在連續(xù)生產(chǎn)中出現(xiàn)重疊，同時進(jìn)行，圖2中SD表示開始加工設(shè)備，TD表示結(jié)束加工設(shè)備，虛線表示有多少子批在該設(shè)備上加工。

圖1 批量分割示意圖

圖2 縱向分割示意圖

1.2 虛擬單元調(diào)度中的批量分割

一般調(diào)度中的批量問題包括流水車間與作業(yè)車間的批量分割問題，采用批量分割解決車間批量分割問題已被廣泛使用，但是關(guān)于單元批量分割的研究較少，尤其是關(guān)于采用批量分割對虛擬單元生產(chǎn)方式的企業(yè)績效的論證的研究很少。批量分割問題主要解決轉(zhuǎn)移批量與加工批量問題，其中，企業(yè)的生產(chǎn)提前期受轉(zhuǎn)移批量的影響，資源的利用水平受加工批量決定，所以，在虛擬單元調(diào)度中，需要同時考慮加工轉(zhuǎn)移批量與加工批量。因此，為了構(gòu)建全局優(yōu)化的的批量分割模型，需要首先分析影響批量分割的因素。

傳統(tǒng)單元生產(chǎn)中考慮批量時，會從工件相似性、加工工藝相似性、加工作業(yè)轉(zhuǎn)移方式、設(shè)備運(yùn)輸能力與費(fèi)用、在制品庫存、在制品緩沖、降低設(shè)備的調(diào)整時間等方面考慮?？紤]到虛擬制造單元存在共享資源設(shè)備，以及各設(shè)備是邏輯成組的生產(chǎn)組織特點(diǎn)，在確定批量分割策略時，需要考慮生產(chǎn)計劃期、交貨期、設(shè)備特性及加工作業(yè)在產(chǎn)品結(jié)構(gòu)中的位置。

單元構(gòu)建與調(diào)度必須要考慮生產(chǎn)計劃期，它代表單元調(diào)整頻率與單元重構(gòu)節(jié)點(diǎn)，不同計劃期可能帶來不同的單元內(nèi)任務(wù)提前期，且單元內(nèi)任務(wù)和時間范圍也不同，因此，在虛擬單元生產(chǎn)方式中，生產(chǎn)提前期是影響系統(tǒng)提前期的重要因素。

由于多項(xiàng)目并行的生產(chǎn)系統(tǒng)中，同一生產(chǎn)批次中可能存在不同交貨期的加工零件，批量策略不能僅考慮生產(chǎn)加工的相似性，需要考慮交貨期的影響，以滿足不同產(chǎn)品的交貨期要求。

由于虛擬單元生產(chǎn)方式的設(shè)備具有邏輯重組的組織特點(diǎn)，因此可以調(diào)用閑置的設(shè)備加工，當(dāng)單元出現(xiàn)負(fù)荷不均衡狀態(tài)時，可以將部分任務(wù)分配至其他單元，也可利用本單元內(nèi)具有相似加工功能的其他設(shè)備，因此，設(shè)備特性應(yīng)當(dāng)也成為批量分割的考慮因素。

由于虛擬制造單元根據(jù)任務(wù)相似性，通過物流系統(tǒng)連接合適資源組織生產(chǎn)，因此，生產(chǎn)批量的確定不僅需要考慮作業(yè)的生產(chǎn)加工時間與設(shè)備的裝備時間，也需要考慮各作業(yè)在加工中的位置，上層作業(yè)數(shù)量決定下層作業(yè)數(shù)量，作業(yè)的加工位置影響其批量，因此，也需要考慮作業(yè)在產(chǎn)品結(jié)構(gòu)中的位置。

2 未考慮批量分割的虛擬單元調(diào)度模型構(gòu)建與假設(shè)

2.1 問題描述

假設(shè)未考慮批量分割的虛擬單元調(diào)度中存在m種類型與n項(xiàng)作業(yè)，每種類型設(shè)備包含多臺設(shè)備。以s(i)表示屬于設(shè)備類型i的某臺設(shè)備，假設(shè)s(i)在車間中被分散布局，每臺設(shè)備能力相同，且不存在平行加工。以O(shè)j,h表示作業(yè)j的第h項(xiàng)操作，以hj表示加工作業(yè)數(shù)，這里，每項(xiàng)作業(yè)的加工作業(yè)數(shù)不一定相等且每項(xiàng)作業(yè)各有其加工路徑與生產(chǎn)設(shè)備。在生產(chǎn)過程中，如果Oj,h在需要設(shè)備類型為i的設(shè)備加工，那么該類型設(shè)備中的所有需要加工的設(shè)備可能出現(xiàn)生產(chǎn)沖突。所以，調(diào)度中需要考慮設(shè)備分配和工序調(diào)度，且這里假設(shè)每臺設(shè)備一次最多只能加工一項(xiàng)作業(yè)，且已知作業(yè)在各設(shè)備間的移動距離、加工作業(yè)的生產(chǎn)批量、所需加工時間與加工優(yōu)先級。模型不考慮批量分割情況，即當(dāng)s(i)加工Oj,h時，作業(yè)j的所有零部件必須全部在設(shè)備s(i)上加工至完畢，不允許加工中斷。模型不考慮提前加工、設(shè)備故障及生產(chǎn)延遲，并假設(shè)當(dāng)t=0時，所有作業(yè)等待加工。

2.2 參數(shù)設(shè)置與模型構(gòu)建

在相應(yīng)的模型構(gòu)建中，以Cmax表示最早完工時間，以j（j=1,…,n）表示作業(yè)數(shù)，i與k（i,k=1,…,m）表示設(shè)備類型，h（h=1,…h(huán)j）表示加工工序數(shù)，l表示每臺設(shè)備的加工順序，Nj表示作業(yè)j的加工批量，Pj,h表示作業(yè)j加工第h道工序的單位生產(chǎn)時間，Ds(i),s(k)表示每項(xiàng)作業(yè)從s(i)至s(k)的單位運(yùn)輸距離，M表示足夠大的數(shù)，W1表示最早完工時間權(quán)重，W2表示總運(yùn)輸距離。

模型以最早完工時間和總運(yùn)輸距離加權(quán)和最小為目標(biāo)，構(gòu)建如下混合多目標(biāo)整數(shù)規(guī)劃模型：

約束條件如下：

在約束條件中，以tj,h表示oj,h開始加工時間，Tms(i),1表加工第l道工序的設(shè)備s(i)的開始加工時間。約束(2)表示最早完工時間必須超過所有工序的完成時間；約束(3)表示所有工序必須在上一道工序結(jié)束后方能加工；約束(4)表示工序約束，即每道工序不可提前加工；約束(5)、(6)屬于二選一約束，表示當(dāng)Xs(i),j,h,1=1時，s(i)對應(yīng)的加工工序l必須與作業(yè)j第h項(xiàng)操作同時加工；約束(7)表示每臺設(shè)備最多只能加工一道工序；約束(8)表示每項(xiàng)作業(yè)的操作只能由i類型設(shè)備中的一臺設(shè)備加工；約束(9)表示如果選擇某臺設(shè)備加工一項(xiàng)作業(yè)的某道工序，則該道工序不受該設(shè)備加工順序的約束；約束(10)和約束(11)為二進(jìn)制約束，約束(10)表示如果Oj,h在s(i)上加工，那么Ys(i),j,h=1，否則，Ys(i),j,h=0，約束(11)表示如果Oj,h在s(i)上加工第l道工序，那么Xs(i),j,h,1=1，否則，Xs(i),j,h,1=1=0；約束(12)和約束(13)表示非負(fù)約束。

3 考慮批量分割的虛擬單元調(diào)度模型構(gòu)建與假設(shè)

3.1 問題描述

假設(shè)有n項(xiàng)作業(yè)和m種設(shè)備，每種類型設(shè)備包含多臺設(shè)備。每項(xiàng)作業(yè)需要不同類型設(shè)備加工，每種類型設(shè)備包含多種加工工能相似的設(shè)備，因此，有多臺設(shè)備可供任意作業(yè)的加工選擇。結(jié)合虛擬單元設(shè)備共享和邏輯重組的特點(diǎn)，本文以最早完工時間和總運(yùn)輸距離加權(quán)和最小為目標(biāo)，構(gòu)建多目標(biāo)混合整數(shù)規(guī)劃模型。在考慮批量分割的虛擬單元調(diào)度中，由于每種類型的設(shè)備包含多個加工路徑，所以，每項(xiàng)作業(yè)的加工子批都盡可能會選擇能提供最短路徑或最小成本的加工路徑，而這種選擇會加大最小完工時間，因此，在考慮批量分割的虛擬單元調(diào)度中，最小完工時間和總運(yùn)輸距離相互矛盾。此外，在虛擬單元中考慮批量分割時，由于任意一項(xiàng)作業(yè)的加工批量被分割為多個子批，這會導(dǎo)致加工操作數(shù)的增加。所以，在考慮批量分割的模型構(gòu)建中，應(yīng)當(dāng)考慮需要選取某種類型設(shè)備中的哪臺設(shè)備，以及該臺設(shè)備需要加工任意作業(yè)的子批量和這些加工何時開始操作。

3.2 模型假設(shè)與構(gòu)建

模型需要考慮以下情況：1）不存在返工情況，即每項(xiàng)作業(yè)只能被同一臺設(shè)備加工一次；2）在加工初始時刻t=0時，每一項(xiàng)作業(yè)都等待被加工；3）調(diào)度開始前，已知每項(xiàng)作業(yè)的加工時間、批量大小以及加工優(yōu)先級；4）已知每種類型設(shè)備之間的運(yùn)輸距離；5）每臺設(shè)備在一個時間點(diǎn)只能加工一項(xiàng)作業(yè)；6）當(dāng)一項(xiàng)作業(yè)開始加工某一工序時，其他工序不允許被加工。

在相應(yīng)的模型構(gòu)建中，以j和u表示作業(yè)數(shù)，i、k和o表示設(shè)備種類，以s(i)表示第i類設(shè)備中的單一設(shè)備s，Nj表示作業(yè)j的批量大小，Pi,j表示第i類設(shè)備生產(chǎn)作業(yè)j的加工時間，Ds(i),s(k)表示從每項(xiàng)作業(yè)從設(shè)備s(i)到s(j)的運(yùn)輸距離，Vj,s(i),s(k)表示作業(yè)j從設(shè)備s(i)到設(shè)備s(k)的轉(zhuǎn)移批量，B表示子批（b=1,2,…,B），F(xiàn)j,b表示作業(yè)j的加工子批，W1表示最小完工時間Cmax的權(quán)重，W2表示最小運(yùn)輸距離的權(quán)重。同時，以(j,i)表示作業(yè)j在設(shè)備i上加工，以(j,i)→(j,k)表示j在i上的加工優(yōu)先于j在k上的加工?；谏鲜黾僭O(shè)與參數(shù)設(shè)置，考慮最小化最早加工時間和最小運(yùn)輸距離的多目標(biāo)整數(shù)規(guī)劃模型構(gòu)建如下：

在約束條件的構(gòu)建中，以tj,s(i),s(k)表示作業(yè)j從設(shè)備s(i)到設(shè)備s(k)后的開始加工時間，Q表示足夠大的數(shù)。設(shè)置約束條件如下：

其中，式(14)表示目標(biāo)函數(shù)為最早完工時間與運(yùn)輸距離最小化；式(15)表示每項(xiàng)作業(yè)加工約束關(guān)系，即后項(xiàng)作業(yè)必須在前向作業(yè)完成后方開始加工；式(16)表示最早完工時間必須在系統(tǒng)完工時間內(nèi)；式(17)表示批量等于前一臺設(shè)備加工的作業(yè)數(shù)；式(18)表示每臺設(shè)備加工的作業(yè)數(shù)需等于該設(shè)備產(chǎn)出的作業(yè)數(shù)；式(19)表示作業(yè)j的加工子批數(shù)等于其加工批量；式(20)前一臺設(shè)備加工的作業(yè)需在后一臺設(shè)備的空閑段加工；式(21)表示需在不同時間段加工不同作業(yè)；式(22)表示如果s(i)作業(yè)j優(yōu)先于s'(t)的作業(yè)在s(k)上加工即為1，否則為0；式(23)表示設(shè)備s(k)上加工的作業(yè)j先于作業(yè)u抵達(dá)，即為1，否則為0；式(24)表示非負(fù)約束。

4 基于遺傳算法的考慮批量分割的虛擬單元調(diào)度模型求解

4.1 遺傳算法介紹

遺傳算法（GA）是一種被廣泛應(yīng)用于解決組合優(yōu)化問題的元啟發(fā)式算法。該算法通過產(chǎn)生隨機(jī)初始種群開始計算，這些初始種群中包含的所有個體被稱為染色體或可行解。遺傳算法通過前期確定的迭代次數(shù)，以交叉、變異等模仿生物界進(jìn)化論的思想增強(qiáng)可行解的質(zhì)量。遺傳算法的目的是在每一代的最后都保持最優(yōu)解。

4.2 染色體編碼

虛擬單元調(diào)度實(shí)際上是一個關(guān)于設(shè)備分配、作業(yè)調(diào)度以及子批量決策的組合調(diào)度問題。這樣，可以通過設(shè)備機(jī)器的分配、設(shè)備加工順序以及加工的子批量大小確定可行解。因此，一條染色體編碼可以由4部分構(gòu)成，分別以v1表示設(shè)備分配矢量，以v2表示作業(yè)加工順序矢量，以v3表示所加工序列的子批量數(shù)，以v4表示子批量大小。假設(shè)有2個子批量，有4種設(shè)備類型A、B、C與D，每種設(shè)備類型包含多臺設(shè)備，如表1所示，表2所示為各加工作業(yè)加工順序與批量大小。

表1 設(shè)備類型與加工設(shè)備

表2 作業(yè)順序及加工批量

以表3表示設(shè)備分配矢量，在設(shè)備分配矢量v1中，以v1(r)表示分配給某一項(xiàng)加工的某臺設(shè)備，且該臺設(shè)備的位置以r表示。在染色體編碼中，染色體長度表示為設(shè)備需要加工操作的數(shù)目與子批量數(shù)目的乘積。例如，在本例中，加工操作數(shù)是10，子批量數(shù)是2，因此，染色體長度是20。在針對表3列示的設(shè)備分配矢量表格中，4號位置表示o2,2，v1(4)則表示o2,2加工的設(shè)備。通過表3發(fā)現(xiàn)，設(shè)備4和設(shè)備3可加工o2,2，所以，子批量為2時，分配加工o2,2的是位置在14的設(shè)備3。

通過以上置換表示方法能夠清楚的表示出作業(yè)的加工順序，但是考慮到加工優(yōu)先級，通過上述方式產(chǎn)生的初始解可能難以是可行解。Gen（1994）[18]針對車間調(diào)度問題提出一種取代置換方法的方法，即指定一項(xiàng)作業(yè)中具有相同加工特征的操作，而后根據(jù)加工優(yōu)先級給出一條染色體中各作業(yè)的加工順序。Gen的置換取代法可以(oj,h)p應(yīng)用于虛擬單元調(diào)度中，以表示第p個子批中作業(yè)j的第h項(xiàng)加工操作，例如，表3的加工可以表示為：

以Vj,p表示第p個子批中生產(chǎn)作業(yè)j所需批量。如作業(yè)3批量大小為13，那么V3.1=7就表示加工作業(yè)3的第一個子批中所需批量為7，V3.2=6表示加工作業(yè)3的第二個子批所需批量為6。通過這種染色體編碼方式，可以使每條生成染色體表示能體現(xiàn)作業(yè)加工優(yōu)先級的可行解，也減少了與置換表示方法相比所需的程序解碼時間。程序?qū)㈦S機(jī)生成代表四個部分的染色體，然后通過解碼方式將染色體與虛擬單元調(diào)度相結(jié)合，通過基因算子進(jìn)化初始解以尋求最優(yōu)解。

4.3 解碼

由于作業(yè)操作之間通常能夠被插入多余空閑時間，所以，能將一條染色體轉(zhuǎn)換為無數(shù)個調(diào)度。解碼的目的是重新排序染色體將其編入調(diào)度，為了達(dá)到這個目的，設(shè)置如下解碼規(guī)則。

在特定子批量p加工過程中，同一作業(yè)加工操作存在加工順序，加工順序之間就存在設(shè)備空閑時間，這里假設(shè)bj,h表示oj,h開始加工時間，cj,h表示oj,h加工完成時間，oj,h只能在oj,h-1加工結(jié)束后加工。假設(shè)設(shè)備i的加工開始時間分別是，如果在存在足夠的空白時間，就能在中能夠插入oj,h進(jìn)行加工，因此，定義bj,h和如下：

該解碼規(guī)則能根據(jù)加工順序矢量v2將加工分配至對應(yīng)的設(shè)備。當(dāng)oj,h在設(shè)備i上調(diào)度時，將從左到右評估已經(jīng)在設(shè)備i上完成調(diào)度的加工操作，以尋得能夠開始的最早空閑時間。如果存在這樣的空閑時間，則安排該項(xiàng)操作至這段時間，如果不存在這樣的空閑時間，則將該項(xiàng)操作安排至設(shè)備i以最后加工。染色體即按照上述規(guī)則進(jìn)行重新排序。

該項(xiàng)解碼規(guī)則和重新排序規(guī)則可使一項(xiàng)操作加工尋求最早的設(shè)備空閑時間，所以，基于上述規(guī)則，在加工順序矢量v2中，列在r前面的操作v不一定能在r前加工。在遺傳算法中，為了保證子代能夠準(zhǔn)確繼承父代的作業(yè)加工順序信息，有必要根據(jù)解碼規(guī)則生成的新加工順序?qū)θ旧w中原作業(yè)加工順序進(jìn)行重新編排。

4.4 交叉

Gen（1994）[19]認(rèn)為，加工順序矢量v2中的每個等位基因并不能代表某項(xiàng)作業(yè)的某個具體操作，只代表該作業(yè)的一項(xiàng)操作，因此，交叉很難生成保持父代加工順序信息的子代。為讓子代能夠保留父代的遺傳信息，將染色體編碼部分的Gen的置換取代法轉(zhuǎn)換成置換表示方法。Gao（2008）[17]指出，當(dāng)前有許多交叉采用置換表示方法，如順序交叉、局部映射交叉、循環(huán)交叉等。本文將對加工順序矢量v2采用順序交叉方式，該交叉步驟如下：

第一步：隨機(jī)從父代選取兩個不同的等位基因形成子部分；

第二步：復(fù)制加工順序的字串到相同位置生成后代；

第三步：從左到右檢查第二代父代的所有加工以完成子代加工順序中未被分配的位置。如果相應(yīng)的位置在第一代父代遺傳后已經(jīng)被分配，則在第二代父代中調(diào)至下一代，否則，將第二代父代中相應(yīng)操作分配至子代對應(yīng)位置。這里，來自第二代父代的加工操作是后代所需要的。交叉過程如圖3所示。

表3 設(shè)備分配矢量表

圖3 加工順序矢量上的順序交叉

4.5 變異

變異的目的是產(chǎn)生和父代略有不同的新解。本文采用基于等位基因的變異操作。對設(shè)備分配矢量v1，基于等位基因的變異操作以隨機(jī)選取等位基因r（r[1,N]）進(jìn)行變異，然后根據(jù)所選等位基因分配設(shè)備進(jìn)行作業(yè)操作。對加工順序矢量v2，基于等位基因的變異操作隨機(jī)決定是否需要變異等位基因s（s[2,N]），如果等位基因s需要變異，則交換v2(s-1)和v2(s)。本文中，將對所有新解進(jìn)行變異操作。

4.6 選擇

在遺傳算法中，選擇操作在放大的樣本空間內(nèi)進(jìn)行，這樣無論子代還是父代就擁有相同的生存幾率。在每一代，如果子代有更好的適應(yīng)度值，則排除整個種群中適應(yīng)度值最差的染色體，剩下的部分用輪盤賭進(jìn)行選擇操作，以在每一次進(jìn)化中提升種群質(zhì)量。表4所示為遺傳算法偽代碼。

表4 遺傳算法偽代碼

5 算例分析

5.1 算例基礎(chǔ)數(shù)據(jù)

為驗(yàn)證模型的有效性，本章以算例說明VCMS調(diào)度。假設(shè)虛擬單元內(nèi)設(shè)備類型有3類，每種設(shè)備包含多臺設(shè)備，如表5所示。表6列出虛擬單元內(nèi)需要加工的作業(yè)及各作業(yè)對應(yīng)的加工工序、加工時間與生產(chǎn)批量，共有6項(xiàng)作業(yè)。各設(shè)備間移動距離矩陣如表7所示。由于模型涉及到權(quán)重設(shè)定，而權(quán)重的確定屬多目標(biāo)決策問題，為方便計算，這里假設(shè)最早完工時間權(quán)重W1為0.95，運(yùn)輸距離權(quán)重W2為0.05。

表5 設(shè)備類型與對應(yīng)設(shè)備

表6 作業(yè)加工順序、加工工時與生產(chǎn)批量

表7 設(shè)備移動距離矩陣

5.2 計算結(jié)果

用MATLAB7.12進(jìn)行計算，初始種群設(shè)為100，交叉和變異概率為0.4，最大迭代次數(shù)為100。得出圖4的調(diào)度結(jié)果。圖5為不考慮批量分割的調(diào)度結(jié)果。發(fā)現(xiàn)模型2對應(yīng)的最早完工時間Cmax和總運(yùn)輸距離分別為272和3756，模型1對應(yīng)的最早完工時間和總運(yùn)輸距離分別為360和3106，通過比較圖4和圖5可以發(fā)現(xiàn)，當(dāng)考慮批量分割時設(shè)備的利用效率得到改善，因此，討論批量分割在虛擬單元調(diào)度中顯得很有必要。

本文主要討論批量分割在虛擬單元調(diào)度中的必要性，通過構(gòu)建不允許批量分割和允許批量分割的兩個混合多目標(biāo)整數(shù)規(guī)劃模型，用遺傳算法求解，結(jié)果表明在虛擬單元調(diào)度中實(shí)行批量分割的策略能夠提高生產(chǎn)效率，而討論批量分割的思路也更符合實(shí)際生產(chǎn)實(shí)際。

圖4 考慮批量分割的虛擬單元調(diào)度

圖5 不考慮批量分割的虛擬單元調(diào)度

6 結(jié)束語

本文意在強(qiáng)調(diào)虛擬單元調(diào)度中批量分割的重要性。虛擬單元生產(chǎn)方式能夠幫助企業(yè)實(shí)現(xiàn)設(shè)備的靈活配置，加大的降低生產(chǎn)成本和零件的加工時間，但如果一項(xiàng)作業(yè)具有多個相似操作，即可將其分成多個批量予以加工以降低設(shè)備的重置成本，因此，在虛擬單元調(diào)度中考慮批量分割的理念顯得尤為重要。本文分別構(gòu)建了考慮批量分割與不考慮批量分割的多目標(biāo)整數(shù)規(guī)劃模型，并介紹了考慮批量分割的遺傳算法，文章最后通過算例驗(yàn)證了所提方法的有效性，并在虛擬單元調(diào)度中實(shí)行批量分割的理念提供了一定的理論依據(jù)。

[1]McLean C.R., Bloom H.M.,Hopp T.H..The virtual manufacturing[A].Proceedings of the 4th IFAC/IFIP Conference on Information Control Problems in Manufacturing Technology,G aithersburg[C].1982,207-215.

[2]K.Mertins.Capacity assignment of virtual manufacturing cellsby applying lot size harmonization[J].International Journal of Production Research,2000,38(17),4383-4391.

[3]Saadettin Erhan Kesen,Sanchoy K.Das,Zulal Gungor.A genetic algorithm based heuristic for scheduling of virtual manufacturing cells(VCMS)[J].Computer&Operations Research,2010,(37):1148-1156.

[4]Saadettin Erhan Kesen,Sanchoy K.Das,ZUlal Gungor.A mixed integer programming formulation for scheduling of virtual manufacturing cells(VCMS)[J].International Journal of Advanced Manufacturing Technology,2010,(47):665-678.

[5]Luis Pinto Ferreira, Enrique Ares Gomez, Gustavo Pelaez Lourido,Benny Thahjono.Optimization of a Multiphase Multiproduct Production Line based on Vrtual Cells[A].Proceedings of the World Congress on Engineering[C].2011:1527-1533.

[6]S.Hamed Hendizadeha, Hamidreza Faramarzib, S.Afshin Mansouric, Jatinder N.D.Guptad, Tarek Y ElMekkawy.Metaheuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times[J].International Journal of Production Economics,2008(111):593-605.

[7]白俊杰,龔毅光,王寧生,唐敦兵.面向訂單制造的可重構(gòu)制造系統(tǒng)中虛擬制造單元構(gòu)建技術(shù)[J].計算機(jī)集成制造系統(tǒng),2009,15(2):313-320.

[8]Amit Bhandwale,Thenkurussi Kesavadas.A methodology to incorporate product mix variations in cellular manufacturing[J].Intell Manuf,2008(19):71–85.

[9]Saravanan M.and Nooral Haq,A.A scatter search method to minimize makespan of cell scheduling problem[J].International Journal of Agile Systems and Management,2008(3):18-36.

[10]王雷,唐敦兵,許美健,萬敏,袁偉東.基于粒子群優(yōu)化算法的制造單元聚類研究[J].計算機(jī)集成制造系統(tǒng).2009,15(2):328-332.

[11]M.B.Aryanezhada, Jamal Aliabadi, Reza Tavakkoli Moghaddam.A new approach for cell formation and scheduling with assembly operations and product structure[J].International Journal of Industrial Engineering Computations,2011(2):533-546.

[12]Rahime Sancar Edis, Arslan Ornek.Simulation analysis of lot streaming in job shops with transportation queue disciplines[J].Simulation Modelling Practice and Theory,2009(17):442-453.

[13]Inci Saricicek, Cenk Celik.Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness[J].Applied Mathematical Modelling,2011(35):4117-4126.

[14]Taofeng Ye.Analysis on multi-stage lot streaming:The effect of transfer[J].Computers & Industrial Engineering, 2012(62):1046-1054.

[15]Defersha FM, Chen M.A comprehensive mathematical model for the design of cellular manufacturing systems[J].International Journal of Production Economics 2006,103:767-83.

[16]Ahkioon S, Bulgak AA, Bektas T.Integrated cellular manufacturing systems design with production planning and dynamic system reconfiguration[J].European Journal of Operational Research,2009,192:414-428.

[17]唐立新,楊自厚,王夢光.CIMS下MRP-Ⅱ多級生產(chǎn)批量計劃問題的研究[J].控制理論與應(yīng)用,1997,14(3):376-382.

[18]Gen M, Tsujimura Y,Kubota E.Solving job-shop scheduling problem using genetic algorithms[A].Proceedings of the 16th International Conference on Computer and Industrial Enginerring[C],1994,576-579.

[19]Gao J, Sun L, Gen M.A hybrid genetic and variable neighborhood decent algorithm for flexible job shop scheduling problems[J].Comput Opns Res, 2008,35(9),2892-2907.