兩車間可調(diào)度工序均衡處理的綜合調(diào)度算法

謝志強(qiáng)，鄭付萍，朱天浩，周含笑

(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080)

1 概述

產(chǎn)品制造調(diào)度問題是NP難問題[1]，目標(biāo)是在滿足約束條件的前提下，使產(chǎn)品的加工時(shí)間盡可能少。以往對大批量相同產(chǎn)品采用流水線方式生產(chǎn)制造的調(diào)度方法主要是純加工調(diào)度[2-3]和純裝配調(diào)度[4-5]，但隨著社會對產(chǎn)品多樣化的需求，多產(chǎn)品小批量的生產(chǎn)計(jì)劃越來越多。對多品種小批量產(chǎn)品，特別是單件復(fù)雜產(chǎn)品，如果按以往先加工后裝配的方式制造，必然要割裂產(chǎn)品內(nèi)在的加工與裝配的并行關(guān)系，文獻(xiàn)[6]提出產(chǎn)品制造的第3種調(diào)度方式：加工和裝配一同處理的綜合調(diào)度。隨著綜合調(diào)度研究的深入，目前有關(guān)綜合調(diào)度的研究已解決了一般綜合調(diào)度問題[7]、工序間存在特殊約束關(guān)系[8]、柔性產(chǎn)品[9]、存在相同設(shè)備[10]和存在批處理設(shè)備[11]等的綜合調(diào)度問題，但所解決的綜合調(diào)度問題僅限于設(shè)備資源在單車間的情況，目前還無人考慮單件復(fù)雜產(chǎn)品在相同設(shè)備資源兩車間制造的分布式綜合調(diào)度的實(shí)際問題。

對于單件復(fù)雜產(chǎn)品在兩車間分布式制造的調(diào)度問題，主要的研究目標(biāo)是設(shè)計(jì)使產(chǎn)品盡早完成的調(diào)度方案。為了使產(chǎn)品盡早完成，需要解決以下問題：(1)兩車間充分并行處理，即讓兩車間工序加工的時(shí)間差盡量??；(2)工序在兩車間移動的次數(shù)盡量少。

對于問題(1)，考慮到葉節(jié)點(diǎn)工序?yàn)榭赏瑫r(shí)加工工序[12]，即葉節(jié)點(diǎn)工序可充分并行處理，本文首先將原始葉節(jié)點(diǎn)工序成批調(diào)度處理，再將每次動態(tài)生成的葉節(jié)點(diǎn)工序分批處理，即可調(diào)度工序分批處理?？紤]到兩車間充分并行處理，即減少在兩車間形成的工序加工時(shí)間差，將每批工序按加工時(shí)間盡量均衡地分為 2組。借鑒單車間綜合調(diào)度中的設(shè)備均衡策略[13]，在相同設(shè)備的兩車間上，提出使得分配工序時(shí)間之和盡量相等的可調(diào)度工序車間均衡策略。對于問題(2)，采取將已分組的工序分配到其緊前工序個(gè)數(shù)較多車間的方法，以降低工序的位移次數(shù)，為此提出分組工序車間確定策略。

2 問題描述

對于樹狀結(jié)構(gòu)的單件復(fù)雜產(chǎn)品，葉節(jié)點(diǎn)工序?yàn)槌跏紩r(shí)可加工的工序，根節(jié)點(diǎn)工序?yàn)樽詈蠹庸さ墓ば?。由于產(chǎn)品加工過程中形成的緊前工序集為空的動態(tài)葉節(jié)點(diǎn)工序?yàn)榭烧{(diào)度工序，于是設(shè)動態(tài)葉節(jié)點(diǎn)工序集為可調(diào)度工序集。為了減少產(chǎn)品完成時(shí)間，計(jì)劃將每批可調(diào)度工序進(jìn)行適當(dāng)合理的分組并分配到兩車間，為此定義可調(diào)度工序分組的相關(guān)概念：工序設(shè)備分組，車間均衡和設(shè)備均衡組。

定義 1(工序設(shè)備分組) 對于動態(tài)形成的一批可調(diào)度工序，按設(shè)備種類進(jìn)行分組稱為工序設(shè)備分組。

定義 2(車間均衡) 將按設(shè)備形成的分組再按車間均衡分配，使分配到兩車間的工序占用設(shè)備的時(shí)長差△T相對較小。

定義 3(設(shè)備均衡組) 通過車間均衡處理產(chǎn)生的車間分組稱為設(shè)備均衡組。

根據(jù)定義 2與可調(diào)度工序集的特征，通過對可調(diào)度工序集均衡處理可使產(chǎn)品在兩車間分布式加工充分并行，達(dá)到減少產(chǎn)品加工時(shí)間的目的，于是提出了兩車間可調(diào)度工序分組均衡處理的綜合調(diào)度算法，并建立相關(guān)的數(shù)學(xué)模型。

由于綜合調(diào)度是將產(chǎn)品加工工序和裝配工序統(tǒng)一為加工工序，加工設(shè)備和裝配設(shè)備統(tǒng)一為設(shè)備一同處理的調(diào)度方式，于是一個(gè)有n道工序的產(chǎn)品在m臺設(shè)備上進(jìn)行分批綜合調(diào)度的約束條件如下：

(1)一臺設(shè)備在某一時(shí)刻只能加工一道工序，且一旦加工某道工序，必須滿足該工序加工完畢后，這臺設(shè)備才可以加工其他工序。

(2)某道工序在某一時(shí)刻只可以占用兩車間中相同設(shè)備中的一臺設(shè)備進(jìn)行加工。

(3)可調(diào)度工序集加工完畢才可以開始下批可調(diào)度工序加工。

(4)允許工序之間等待，允許設(shè)備在工序到達(dá)之前閑置。

由于本文討論的綜合調(diào)度算法是在滿足上述約束條件下，按動態(tài)形成的可調(diào)度工序集分批調(diào)度，每批可調(diào)度工序加工開始的時(shí)間為上一批可調(diào)度工序加工完畢的時(shí)間，每批可調(diào)度工序加工完畢的時(shí)間為按工序設(shè)備分組后在兩車間中設(shè)備完工的最大時(shí)間值，于是本問題的數(shù)學(xué)描述為：

其中，w代表a、b兩車間，可調(diào)度工序批次為j=1,2,…,k；Ewj是每批的完成時(shí)間；Ewk為產(chǎn)品完成時(shí)間；Sj為每批可調(diào)度工序的開始加工時(shí)間，即上批可調(diào)度工序的完成時(shí)間，第1批可調(diào)度工序的開始加工時(shí)間為S1=0；Cwjf為第j批可調(diào)度工序在 w車間的設(shè)備 f上組合工序的加工時(shí)間和；tjf是設(shè)備均衡組工序加工時(shí)間差；式(5)表示第 j批可調(diào)度工序在w車間各設(shè)備完工的最大值。

3 分配方案設(shè)計(jì)與分析

為減少產(chǎn)品兩車間分布式綜合制造的時(shí)間，可從 2個(gè)方面考慮：(1)使產(chǎn)品在兩車間充分并行制造；(2)減少兩車間工序移動占用的時(shí)間。于是研究使產(chǎn)品工序在兩車間加工時(shí)間差相對小和工序在兩車間移動次數(shù)少的調(diào)度方案。

由于每批可調(diào)度工序可并行處理，為了減少兩車間加工時(shí)間差和工序移動次數(shù)，設(shè)計(jì)了可調(diào)度工序車間均衡策略和分組工序車間確定策略。

為方便按批調(diào)度工序，本文設(shè)置工序的屬性：qi|Mwi|ti|Fi|ei|Li，其中，qi為工序名；Mwi為工序 qi所在車間 w(a或b)的加工設(shè)備；ti為工序qi的加工時(shí)間；Fi為工序qi的緊前工序集；ei為集合 Fi中工序的個(gè)數(shù)；Li為工序 qi的緊后工序，i∈{1,2,…,n}。一般情況下，工序?qū)傩灾恍枨?項(xiàng)就可以實(shí)現(xiàn)產(chǎn)品加工的策略和方案，本文添加了緊前工序集、緊前工序個(gè)數(shù)和緊后工序，可根據(jù)緊前工序個(gè)數(shù)為空動態(tài)生成可調(diào)度工序。

3.1 可調(diào)度工序車間均衡策略

一般產(chǎn)品充分并行制造要求設(shè)備均衡加工，根據(jù)文獻(xiàn)[13]，設(shè)備均衡是指工序的加工設(shè)備不唯一時(shí)，選擇已加工時(shí)間和最小的設(shè)備作為該工序的加工設(shè)備。對于相同設(shè)備兩車間的產(chǎn)品制造，當(dāng)要求兩車間所有相同設(shè)備對每批可調(diào)度工序都均衡加工時(shí)為車間均衡，因此，車間均衡是基于設(shè)備均衡提出的。由定義2，車間均衡與設(shè)備均衡區(qū)別如下：

(1)相同點(diǎn)：2個(gè)均衡都是針對設(shè)備的。

(2)不同點(diǎn)：設(shè)備均衡是針對一種設(shè)備且考慮以往工序加工情況，車間均衡是針對兩車間中所有的相同設(shè)備且只考慮同批可調(diào)度工序。

對每批可調(diào)度工序進(jìn)行分配時(shí)，根據(jù)定義 1對設(shè)備進(jìn)行分組，針對每個(gè)工序設(shè)備分組采用本文設(shè)計(jì)的車間均衡策略達(dá)到車間均衡。下面詳細(xì)說明車間均衡策略：

(1)當(dāng)某工序設(shè)備分組中工序唯一，此時(shí)該設(shè)備無需考慮均衡；

(2)當(dāng)某工序設(shè)備分組中僅有 2個(gè)可調(diào)度工序，將這2個(gè)工序分別分配到兩車間；

(3)當(dāng)某工序設(shè)備分組中可調(diào)度工序數(shù)大于等于3時(shí)，有以下2種方案。

方案1 工序動態(tài)調(diào)整。

因?yàn)閮绍囬g工序設(shè)備分組中設(shè)備m上工序均衡分組的重要指標(biāo)是該工序設(shè)備分組中所有工序的加工時(shí)間和除以車間數(shù)2的值Pm，即在本文中為該工序設(shè)備分組中所有工序的加工時(shí)間和的一半，所以該均衡方案的目標(biāo)是讓設(shè)備均衡組的2個(gè)組合工序加工時(shí)間值與Pm的差值盡量小。具體實(shí)現(xiàn)步驟如下：

步驟1 分組時(shí)考慮有序序列比無序序列針對工序調(diào)整的確定性強(qiáng)、對后續(xù)的工序調(diào)整的操作便捷以及時(shí)間復(fù)雜度小，于是先將工序設(shè)備分組中的工序按加工時(shí)間ti升序排序得序列H。

步驟2 按序?qū)中的值累加到D中，直到首次滿足均衡差△T=D–Pm≥0，記錄累加的工序序列為 G，將其他工序存放到升序序列B中。

步驟3 對均衡差△T進(jìn)行處理。若△T=0或△T值小于H中的第1個(gè)工序的加工時(shí)間，已達(dá)到最優(yōu)均衡，記錄設(shè)備均衡組；否則將△T與 G中的其他項(xiàng)進(jìn)行比較，若△T等于G中某項(xiàng)，則將此項(xiàng)調(diào)整到序列B；若△T介于G中某相鄰兩項(xiàng)值之間，則將G中與△T接近的工序調(diào)整到B中。

方案1可調(diào)度工序車間均衡策略實(shí)現(xiàn)流程如圖1所示。

圖1 可調(diào)度工序車間均衡策略實(shí)現(xiàn)流程

方案2 根據(jù)冪集值確定。

具體方法是：首先確定設(shè)備m的最優(yōu)均衡時(shí)間Pm；然后求該工序設(shè)備分組的冪集；其次計(jì)算每個(gè)冪集中的工序按屬性ti累加和D并計(jì)算均衡差△T=D–Pm，記錄△T最小的值；最后將△T值最小的冪集作為設(shè)備均衡組的一部分。

由于方案2在確定均衡差△T時(shí)比方案1考慮的情況多，因此方案2的結(jié)果可能優(yōu)于方案1。但由于方案2的時(shí)間復(fù)雜度是指數(shù)級的，而方案 1的時(shí)間復(fù)雜度在二次多項(xiàng)式內(nèi)，考慮調(diào)度方法的實(shí)用性和時(shí)效性，針對工序設(shè)備分組中可調(diào)度工序大于等于3的情況時(shí)，選擇方案1進(jìn)行車間均衡。

3.2 工序車間確定策略

產(chǎn)品在兩車間分布式加工制造，存在工序在兩車間移動的情況，關(guān)于工序的移動提出以下相關(guān)概念：

定義 4(工序移動) 產(chǎn)品加工時(shí)，當(dāng)工序 qi的緊前工序Fi與其不在同一車間，需將Fi的加工結(jié)果移動到qi所在的車間，稱其為工序移動。

定義5(位移數(shù)) 由工序移動產(chǎn)生的次數(shù)稱為位移數(shù)。

由于工序移動會增加產(chǎn)品完工的時(shí)間，當(dāng)確定設(shè)備均衡組后，需確定設(shè)備均衡組 2個(gè)組合的加工車間，以減少位移數(shù)，于是根據(jù)工序相關(guān)性[14]提出分組工序車間確定策略。工序車間策略實(shí)現(xiàn)流程如圖2所示。

圖2 工序車間策略實(shí)現(xiàn)流程

工序車間確定策略描述如下：

設(shè)第j批可調(diào)度工序中設(shè)備f均衡組的2個(gè)組合為C1jf和C2jf，對C1jf和C2jf中工序的緊前工序所在車間進(jìn)行統(tǒng)計(jì)。設(shè)組合C1jf中工序的緊前工序在a、b車間的總數(shù)分別為x、y，組合C2jf中工序的緊前工序在a、b車間的總數(shù)分別為p、q。若C1jf組合中的工序在a車間加工，C2jf組合中的工序在b車間加工，則產(chǎn)生的位移數(shù)為y+p，反之產(chǎn)生的位移數(shù)為x+q。于是工序車間確定策略是選擇產(chǎn)生位移數(shù)較少的將兩組合分配到兩車間的方式。即通過min{x + q, y + p}確定C1jf和C2jf所在車間；若x+q和y+p相等，即工序的緊前工序在兩車間分布數(shù)相同，則任意分配兩組合到兩車間。

4 可調(diào)度工序分組處理的實(shí)現(xiàn)與分析

4.1 算法實(shí)現(xiàn)

為了實(shí)現(xiàn)產(chǎn)品在兩車間分布式加工縮短產(chǎn)品完成時(shí)間和減少工序移動次數(shù)的目標(biāo)，提出兩車間可調(diào)度工序分組均衡處理的綜合調(diào)度算法。該算法的主要思想是將原始葉節(jié)點(diǎn)工序和每次動態(tài)生成的葉節(jié)點(diǎn)工序分批處理，再將每批工序按設(shè)備加工時(shí)間盡量均衡地分為 2組，再將已分組的工序分配到其緊前工序個(gè)數(shù)較多的車間，對分組中的工序依次按序調(diào)度并在相應(yīng)設(shè)備上確定盡早開始加工時(shí)間，最后修改當(dāng)前已調(diào)度工序的緊后工序、緊前工序個(gè)數(shù)屬性。

對可調(diào)度工序按批進(jìn)行分配調(diào)度時(shí)，既考慮了可調(diào)度工序車間均衡又考慮了減少位移數(shù)，因此該算法可使產(chǎn)品盡早完成且控制工序位移次數(shù)。算法的描述如下：

(1)輸入設(shè)備數(shù)和產(chǎn)品信息。

(2)根據(jù)工序 qi緊前工序個(gè)數(shù)屬性 ei為 0確定可調(diào)度工序。

(3)根據(jù)上一批可調(diào)度工序在a、b車間中各設(shè)備完成時(shí)間 Ea(j–1)、Eb(j–1)的最大值，即 Sj=(Ea(j–1)≤Eb(j–1)?Eb(j–1)：Ea(j–1))，確定每批可調(diào)度工序的開始加工時(shí)間Sj。

(4)可調(diào)度工序按設(shè)備進(jìn)行分組。

(5)如果工序設(shè)備分組中工序數(shù)小于等于 2，將工序依次存入兩組合，此時(shí)組合可以為空集；若分組中工序數(shù)大于2，依據(jù)車間均衡策略進(jìn)行均衡分組。

(6)判斷所有的工序設(shè)備分組是否達(dá)到車間均衡，不均衡則執(zhí)行步驟(5)。

(7)判斷可調(diào)度工序的批次j是否為1，若為1則轉(zhuǎn)到步驟(9)。

(8)根據(jù)分組工序車間確定策略確定設(shè)備均衡組的加工車間，方法是對設(shè)備均衡組中的工序，根據(jù)已加工工序緊后工序?qū)傩?Li，依次尋找緊前工序并確定緊前工序所在車間 w，同時(shí)累加對應(yīng)車間工序數(shù)，并根據(jù)工序數(shù)的多少確定設(shè)備均衡組的加工車間。

(9)各設(shè)備均衡組中的工序按序調(diào)度，且開始加工時(shí)間為Sj。

(10)判斷此批可調(diào)度工序的緊后工序Li是否為空，為空轉(zhuǎn)到步驟(14)。

(11)計(jì)算此批工序在兩車間的結(jié)束時(shí)間Eaj和Ebj。方法是由問題描述中的式(3)有：Eaj=Sj–1+Taj或 Ebj=Sj–1+Tbj；根據(jù)式(6)有：Taj=max{Caj1,Caj2,…,Cajf,…,Cajm}或 Tbj=max{Cbj1,Cbj2,…,Cbjf,…,Cbjm}。

(12)修改此批可調(diào)度工序的緊后工序、緊前工序個(gè)數(shù)屬性，配合完成下批可調(diào)度工序的確定。方法是對當(dāng)前批次可調(diào)度工序的緊后工序、緊前工序個(gè)數(shù)依次進(jìn)行減1操作。

(13)刪除此批可調(diào)度工序，并將可調(diào)度工序的批次j值加1且轉(zhuǎn)到步驟(2)。

(14)輸出甘特圖。

(15)結(jié)束。

算法流程如圖3所示。

圖3 本文算法流程

4.2 算法復(fù)雜度分析

本文算法特點(diǎn)是動態(tài)生成可調(diào)度工序，并按批進(jìn)行調(diào)度處理，所以，下面針對一批可調(diào)度工序調(diào)度處理的復(fù)雜度進(jìn)行分析。

(1)可調(diào)度工序確定。根據(jù)工序qi緊前工序個(gè)數(shù)的屬性ei確定可調(diào)度工序，方法是當(dāng)ei=0，qi為可調(diào)度工序。對n個(gè)工序需進(jìn)行n次判斷處理，所以，可調(diào)度工序確定的復(fù)雜度為O(n)。

(2)工序設(shè)備分組及排序。根據(jù)工序qi加工設(shè)備屬性Mwi先進(jìn)行工序設(shè)備分組，此時(shí)需判斷 n次；然后進(jìn)行工序設(shè)備分組中工序排序，設(shè)工序設(shè)備分組中每個(gè)設(shè)備工序數(shù)平均為 n/m，于是每個(gè)設(shè)備上工序升序排序的操作次數(shù)是，所有工序設(shè)備分組并排序的操作次數(shù)是 n+，由于1 ≤ m＜＜n，因此工序設(shè)備分組并排序的復(fù)雜度為O(n2)。

(3)車間均衡。工序設(shè)備分組中工序要達(dá)到車間均衡，對每個(gè)工序設(shè)備分組工序加工時(shí)間求和，再除以 2求得平均時(shí)間Pm，需運(yùn)算n/m次；工序設(shè)備分組中的工序依次累加到D且與Pm比較，最多需計(jì)算和判斷2n/m次；均衡差△T與G中工序，最多進(jìn)行比較和調(diào)整次數(shù)為n/m+1。每個(gè)工序設(shè)備分組達(dá)到車間均衡的操作次數(shù)是4n/m+1。所有工序設(shè)備分組處理的次數(shù)為m(4n/m+1)，因此，車間均衡的復(fù)雜度為O(n)。

(4)分組工序車間確定。若工序qi已加工調(diào)度，可通過工序?qū)傩訫wi確定其加工設(shè)備和加工車間。一批可調(diào)度工序得到的某設(shè)備均衡組中的工序數(shù)平均小于n/m，已加工工序最壞情況下為n。

確定設(shè)備均衡組中一個(gè)工序的緊前工序及緊前工序所在車間，需判斷已加工的n個(gè)工序緊后工序?qū)傩詎次，再確定其所在的車間最多n次，在累加車間工序數(shù)最多n次，所以確定設(shè)備均衡組中一個(gè)工序的緊前工序及緊前工序所在車間最多需處理3n次。

確定設(shè)備均衡組的組合中 n/m個(gè)工序的緊前工序及緊前工序所在車間最多需處理3n2/m次，于是一個(gè)設(shè)備均衡組分組工序車間確定的次數(shù)為6n2/m，所有設(shè)備均衡組確定車間的次數(shù)為6n2。因此，分組工序車間確定的復(fù)雜度為O(n2)。

(5)分組中工序的依序調(diào)度。設(shè)備均衡組的一個(gè)組中工序按序調(diào)度，由于平均每個(gè)組中工序個(gè)數(shù)小于n/m，組中工序需要比較的次數(shù)為，一個(gè)設(shè)備均衡組工序按序調(diào)度需比較次數(shù)為。因此所有分組中工序依序調(diào)度的比較次數(shù)為，即復(fù)雜度為O(n2)。

(6)工序緊后工序?qū)傩缘男薷?。?dāng)前批次可調(diào)度工序個(gè)數(shù)最多為n，每個(gè)工序查找其緊后工序且緊后工序的緊前工序個(gè)數(shù)屬性進(jìn)行一次減 1操作。由于被查找的工序數(shù)最多為n，因此查找緊后工序的操作最多為n×n次，修改一批可調(diào)度工序的緊后工序緊前工序個(gè)數(shù)屬性的修改次數(shù)最多為n。因此，修改一批可調(diào)度工序的緊后工序緊前工序個(gè)數(shù)屬性的操作次數(shù)的數(shù)量級最多為O(n2)。

綜上所述，在最壞情況下，對一批可調(diào)度工序調(diào)度處理的時(shí)間復(fù)雜度為O(n2)。設(shè)產(chǎn)品分k批調(diào)度，因此，本文算法復(fù)雜度應(yīng)為O(kn2)。

5 調(diào)度實(shí)例

若有單件復(fù)雜產(chǎn)品A，其加工工藝樹如圖4所示，框內(nèi)符號分別表示：產(chǎn)品的工序名|加工設(shè)備名|工序加工時(shí)間。

圖4 產(chǎn)品A的加工工藝樹

由工序緊前工序個(gè)數(shù)屬性為0確定第1批可調(diào)度工序{A13, A14, A15, A22, A17, A18, A19, A9, A20, A21}；根據(jù)定義 1進(jìn)行工序設(shè)備分組且分組中工序 qi按加工時(shí)間屬性 ti升序排序(Mf表示工序設(shè)備分組的工序組)：M1{A18, A21},M2{A9, A19, A20}, M3{A13, A22, A15, A17}, M4{A14}。

M1組中兩工序依次分配到兩車間；M2組工序數(shù)大于2，需進(jìn)行車間均衡，A9與A19的加工時(shí)間和與平均值Pm相等，所以設(shè)備均衡組兩組合C112{A9, A19}、C212{A20}；M3組工序(A13, A22, A15)累加和D首次滿足大于Pm，即15>11時(shí)，兩組合C113{A13, A22, A15}、C213{A17}，均衡差值△T=D –Pm=4，△T與累加工序A13的加工時(shí)長相等，于是應(yīng)調(diào)整到C213中，所以C213改為{A13, A17}，C113改為{A22, A15}，M4{A14}任意分配。

最后分到 a車間加工調(diào)度的工序{A18, A9, A19, A13,A17, A14}，b車間加工調(diào)度的工序{A21, A20, A22, A15}。由于此批可調(diào)度工序無緊前工序，因此開始加工時(shí)間S1為0，對此批可調(diào)度工序進(jìn)行加工調(diào)度。根據(jù)已加工工序可知此批可調(diào)度工序在a、b車間加工結(jié)束時(shí)間均為11個(gè)單位。

修改此批可調(diào)度工序的緊后工序、緊前工序個(gè)數(shù)屬性，并刪除此批可調(diào)度工序。根據(jù)工序、緊前工序個(gè)數(shù)屬性 ei為0確定下一批可調(diào)度工序{A6, A16, A8, A10, A11, A12}，按工序設(shè)備分組，分組中工序按加工時(shí)長升序排序M2{A6,A16, A8}、M4{A10, A11, A12}。

M2組進(jìn)行車間均衡，A6和A16的加工時(shí)間和D與Pm的關(guān)系9>8，△T =D–Pm=1，△T小于累加工序中第1項(xiàng)，所以不需調(diào)整，最后組合C122{A6, A16}、C222{A8}；M4組車間均衡后均衡組的兩組合C124{A10, A11}、C224{A12}。

由于此批工序有緊前工序，因此需根據(jù)分組工序車間確定策略進(jìn)行車間選擇。首先統(tǒng)計(jì)兩組合C122、C222中緊前工序在兩車間的個(gè)數(shù)。C122、C222在a車間的個(gè)數(shù)分別為x=2、p=2，在 b車間的個(gè)數(shù)分別為 y=1、q=0；若組合 C122在a車間加工產(chǎn)生的位移數(shù)為1，C222在b車間加工產(chǎn)生的位移數(shù)為2，總位移數(shù)3；反之產(chǎn)生的總位移數(shù)2；選擇位移數(shù)少的方式進(jìn)行分配，即選擇位移數(shù)為2的方式將C122分配到b車間，C222分配到a車間；同理C124分配到a車間，C224分配到b車間。

于是，此批分到 a車間加工的工序{A8, A10, A11}，b車間加工的工序{A6, A16, A12}。此批工序的開始加工時(shí)間為上一批工序加工結(jié)束時(shí)間即11，調(diào)度此批可調(diào)度工序。由于Ta2為13、Tb2為9，因此Ea2為24、Eb2為20。

按照上面的處理方法對每批工序分配和調(diào)度直到最后一個(gè)工序處理結(jié)束，產(chǎn)品在a、b車間調(diào)度的甘特圖如圖5和圖6所示。

圖5 車間a所得甘特圖

圖6 車間b所得甘特圖

若對每批可調(diào)度工序處理時(shí)不采用上文提出的策略，即先進(jìn)行設(shè)備均衡處理，而是將工序降序排序后通過考慮設(shè)備均衡進(jìn)行工序車間分配。

對第 1批可調(diào)度工序并按路徑長度降序排序?yàn)閧A20,A21, A17, A18, A22, A19, A13, A15, A14, A9}。依次將工序按盡早加工要求分配到兩車間，分到 a車間的工序?yàn)閧A14,A17, A15, A19, A9, A21}、b車間的工序?yàn)閧A22, A13, A20,A18}。

依次類推得到該方法a和b車間產(chǎn)品調(diào)度甘特圖如圖7和圖8所示。

圖7 對比方法所得a車間甘特圖

圖8 對比方法所得b車間甘特圖

由圖5、圖6與圖7、圖8對比可以看出，采用本文的算法產(chǎn)品加工完成時(shí)間是38工時(shí)，產(chǎn)生的位移數(shù)為6，采用另外一種方案的加工時(shí)間是40工時(shí)，產(chǎn)生的位移數(shù)為8。

之所以第1個(gè)方案效果更好，是因?yàn)榈?個(gè)方案既沒有真正地實(shí)現(xiàn)設(shè)備均衡，也沒有考慮工序移動次數(shù)。例如，第1批結(jié)束時(shí)間方案1是11，而方案2是13。

6 結(jié)束語

針對單件復(fù)雜產(chǎn)品在兩車間分布式制造問題，本文根據(jù)動態(tài)生成可并行處理的可調(diào)度工序和兩車間的資源屬性提出了 2個(gè)方案：設(shè)備均衡策略和工序確定車間策略，通過 2個(gè)策略的結(jié)合應(yīng)用，實(shí)現(xiàn)了兩車間分布式制造調(diào)度的綜合調(diào)度。主要結(jié)論如下：

(1)按可調(diào)度工序分批處理，再按工序設(shè)備分組和車間均衡處理，算法簡單，效果較好，且算法復(fù)雜度不超過二次多項(xiàng)式。

(2)按分組工序車間確定策略確定工序所在車間，減少了工序在兩車間的移動次數(shù)，縮短了產(chǎn)品加工時(shí)間。

本文為解決具有相同資源的兩車間分布式調(diào)度提供了解決方案，對研究多車間分布式綜合調(diào)度問題有一定的借鑒作用。

[1]黃啟春, 陳 奇, 俞瑞釗.一種面向作業(yè)的快速調(diào)度算法[J].軟件學(xué)報(bào), 1999, 10(10): 1073-1077.

[2]Brucker P, Sotskov Y N, Werner F.Complexity of Shop-scheduling Problems with Fixed Number of Jobs: A Survey[J].Mathematical Methods of Operations Research,2007, 65(3): 461-481.

[3]張維存, 鄭丕諤, 吳曉丹.蟻群遺傳算法求解能力約束的柔性作業(yè)車間調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng), 2007, 13(2):127-131, 156.

[4]羌 磊, 肖田元.應(yīng)用擴(kuò)展貝葉斯進(jìn)化算法求解混流裝配調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng), 2007, 13(2): 111-116.

[5]李 原, 張開富, 王 挺, 等.基于遺傳算法的飛機(jī)裝配序列規(guī)劃優(yōu)化方法[J].計(jì)算機(jī)集成制造系統(tǒng), 2006, 12(2): 30-33.

[6]謝志強(qiáng).工件間有約束的復(fù)雜產(chǎn)品工序調(diào)度研究[D].哈爾濱:哈爾濱理工大學(xué), 2009.

[7]謝志強(qiáng), 辛 宇, 楊 靜.基于設(shè)備空閑事件驅(qū)動的綜合調(diào)度算法[J].機(jī)械工程學(xué)報(bào), 2011, 47(11): 139-147.

[8]謝志強(qiáng), 李志敏, 郝淑珍, 等.工序間存在零等待約束的復(fù)雜產(chǎn)品調(diào)度研究[J].自動化學(xué)報(bào), 2009, 35(7): 983-989.

[9]Xie Zhiqiang, Hao Shuzhen, Ye Guangjie, et al.A New Algorithm for Complex Product Flexible Scheduling with Constraint Between Jobs[J].Computers & Industrial Engineering, 2009, 57(3): 766-772.

[10]Xie Zhiqiang, Ye Guangjie, Zhang Dali, et al.New Nonstandard Job Shop Scheduling Algorithm[J].Chinese Journal of Mechanical Engineering, 2008, 21(4): 97-100.

[11]謝志強(qiáng), 王 悅, 楊 靜.存在批量為2的批處理設(shè)備的綜合調(diào)度算法[J].北京工業(yè)大學(xué)學(xué)報(bào), 2011, 37(10): 1470- 1476, 1481.

[12]謝志強(qiáng), 楊 靜, 楊 光, 等.可動態(tài)生成具有優(yōu)先級工序集的動態(tài)Job-Shop調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào), 2008, 31(3): 502-508.

[13]謝志強(qiáng), 邵 俠, 楊 靜.存在設(shè)備無關(guān)延遲約束的綜合柔性調(diào)度算法[J].機(jī)械工程學(xué)報(bào), 2011, 47(4): 177-185.

[14]熊禾根, 李建軍, 孔建益, 等.考慮工序相關(guān)性的動態(tài)Job Shop調(diào)度問題啟發(fā)式算法[J].機(jī)械工程學(xué)報(bào), 2006, 42(8): 51-55.