徐本柱 吉 靖 費曉璐

合肥工業(yè)大學，合肥，230009

?

柔性作業(yè)車間中基于工序分批的調(diào)度問題與求解

徐本柱 吉 靖 費曉璐

合肥工業(yè)大學，合肥，230009

考慮到柔性作業(yè)車間分批調(diào)度中不同工序具有各自合適批量大小，提出了基于工序分批調(diào)度的概念，建立了以關鍵路徑工序為中心的分批調(diào)度模型。該模型動態(tài)更新可加工工序子批集，同時更新可選加工機器，及時調(diào)整加工路線，為不同工序安排大小合適的批量，以達到優(yōu)化完工時間、有效降低總加工批次的目的。實驗結(jié)果表明，相比基于工件分批的調(diào)度，該模型在優(yōu)化最長完工時間、提高機器利用率的同時，大幅減少了總加工批次數(shù)量(42%)，降低了車間調(diào)度管理的復雜度。

柔性作業(yè)車間;分批調(diào)度模型;工序分批;不等量分批

0 引言

作業(yè)車間調(diào)度問題(job-shopschedulingproblem,JSP)是一類滿足任務分配和順序約束的組合優(yōu)化問題[1]，隨著實際作業(yè)車間模式的不斷改革創(chuàng)新和研究的不斷推進，分批和并行成為JSP的重點擴展方向[2-3]。并行機調(diào)度問題(PMSP)和流水作業(yè)車間調(diào)度問題(FSSP)是作業(yè)車間調(diào)度研究的典型問題，文獻[4]利用差分進化算法分別對并行機調(diào)度問題和流水作業(yè)車間調(diào)度問題進行了分批調(diào)度優(yōu)化。文獻[5]利用蟻群算法對混合流水作業(yè)車間調(diào)度問題，即并行機調(diào)度和流水作業(yè)車間調(diào)度的結(jié)合問題，進行了分批調(diào)度優(yōu)化。而柔性作業(yè)車間調(diào)度問題(flexiblejob-shopschedulingproblem,FJSP)作為JSP的擴展[6]，是目前調(diào)度領域的重要研究方向。當前柔性作業(yè)車間分批調(diào)度問題(flexiblejob-shopschedulingwithlot-splittingproblem,FJSLP)模型對同種工件所有工序采用等量分批的方法，沒有考慮不同工序的適合批量需求。由于不同工序具有加工時間、加工準備時間和約束關系不同等特點，使得不同工序具有各自的合適批量大小，甚至同一工序在不同機器上加工，其合適的批量大小也可能會發(fā)生變化。

作為并行加工問題重要的優(yōu)化方法，分批調(diào)度一直是國內(nèi)外針對柔性作業(yè)車間調(diào)度研究的熱點。文獻[7-8]通過仿真實驗證明分批處理可以有效提高機器利用率，縮短生產(chǎn)周期，但并未給出具體的分批方法。文獻[9]解決了單一工藝路線的作業(yè)車間分批調(diào)度問題，但未考慮柔性作業(yè)車間的調(diào)度環(huán)境。文獻[10]提出了一種等量分批方法，該方法使子批批次數(shù)量的確定和子批加工順序的確定同時得到優(yōu)化，但由于是等量劃分，各子批批量難以根據(jù)設備的負荷大小進行柔性調(diào)整。文獻[6]利用壓縮技術，設計了一種動態(tài)柔性分批策略，使得工件可以根據(jù)設備負荷動態(tài)調(diào)整批量大小。文獻[11]利用遺傳算法解決FJSP問題，有效地優(yōu)化了最長完工時間，但是該算法存在早熟、收斂慢的缺點。文獻[12]利用兩級遺傳算法解決可變工藝路線的JSP問題。文獻[6]利用禁忌搜索法解決柔性作業(yè)車間分批調(diào)度問題，對分批策略進行優(yōu)化，并在優(yōu)化加工順序的過程中提出對關鍵路徑進行鄰域搜索的方法，可以有效地平衡機器負荷，縮短生產(chǎn)周期。但是面對多品種小批量的生產(chǎn)需求，以上文獻沒有考慮變批量的生產(chǎn)特征。文獻[13-14]針對多品種、變批量需求的可重構(gòu)制造問題，綜合考慮工藝路線與生產(chǎn)批量約束關系，提出了兩階段求解的虛擬制造單元構(gòu)建方法。但上述方法沒有考慮到工序具有加工時間不同、準備時間不同以及工序約束關系不同等特點，本質(zhì)上都屬于基于工件分批的方法。

本文針對柔性作業(yè)車間中不同工序的加工工時及準備時間不同、工序間約束關系差異的情況，以及各工序合適的批量大小不盡相同的特點，提出了基于工序分批的調(diào)度概念，建立了以關鍵路徑工序為中心的分批調(diào)度模型。該模型為不同工序安排了合適的批量大小，同時優(yōu)化了最大加工完成時間，大幅減少了加工批次數(shù)量，并且使得分批更加靈活，符合實際生產(chǎn)需求。

1 問題描述

本文重點研究柔性作業(yè)車間工件工序可并行的分批調(diào)度問題，即在柔性作業(yè)車間調(diào)度的基礎上對工序進行分批，為不同的工序安排合適的批量，并讓受約束不可同時加工的工序在一定條件下并行加工，該分批調(diào)度問題描述如下：共有n種待加工工件J= {Ji|i=1,2,…,n}，在m臺加工機器M= {Mk|k=1,2，…，m}上進行加工,工件Ji包含ni道工序,工序集合為O={Oij|i=1,2,…,n；j=1,2,…,ni},每道工序可在多臺機器上進行加工，同一工序在不同的設備中加工時間相等或不等，每種工件的每道工序被分成l= {lij|i=1,2,…,n；j=1,2,…,ni}個批次。

圖1所示為工件P的加工工序，若基于工件分批，則批次數(shù)量lP1=lP2=lP3，即所有工序批次數(shù)量相同，而本文基于工序分批，則lP1、lP2、lP3根據(jù)工序特點進行確定，可相等或不等。

圖1 工件P的加工工序

針對上述問題描述，假設如下：①所有工件的工序數(shù)以及工序約束關系已知；②每道工序在可用機器上的加工時間確定；③每道工序加工準備時間已知；④加工過程中設備不因人為或非人為因素中斷。

同時，該問題需要滿足以下約束：①加工設備約束。同一機器在完成一個批次的工件后才能加工另一個批次。②加工準備時間約束。同工件相同工序的不同批次依次在同一機器上進行加工，后者無需加工準備時間，其他情況則需要加工準備時間。③工序并行性約束。在工件的加工裝配過程中，工件的某些工序可以并行加工。如圖2和圖3所示：圖2中，子工件A經(jīng)過工序OA加工成子工件A′，子工件B經(jīng)過工序OB加工成子工件B′ ，子工件A′ 和B′經(jīng)過工序OC加工成目標工件C，圖3是圖2抽象出的工序約束關系圖。工序并行性約束存在兩種情況：相同批次的工序OA和工序OB可并行加工；不同批次的工序OA和工序OC可并行加工。④工序子批批量動態(tài)加工約束。每道工序所有緊前工序已加工總批量需大于或等于該道工序的欲加工子批批量，此工序批次方可加工。

圖2 工件工序加工裝配圖

圖3 工序約束關系圖

2 基于工序的分批調(diào)度模型

根據(jù)問題的描述和實際需要，建立數(shù)學模型，目標函數(shù)如下。

(1)設Ci為工件Ji的完工時間，下式表示最長完工時間最?。?/p>

(1)

(2)設lij為工序Oij的被劃分的批次數(shù)量，下式表示總加工批次最少：

(2)

本文屬于多目標求解問題，在優(yōu)化f1的同時，盡可能減小f2，以降低車間管理復雜度。

批量加工相關的約束條件如下。

(1)設Xijz為工件Ji第j道工序第z批的批量大小，Di為工件Ji的總數(shù)量，同工序的所有批次數(shù)量總和等于工件總數(shù)。故批次數(shù)量和批量大小間的約束關系如下：

(3)

(2)同一工序內(nèi)采用等量分批的方法，當工件不可完全等分時，剩余不足一批的工件與前一批次同時加工。設lij為工件Ji第j道工序的批次數(shù)量，則子批大小為

(4)

(3)所有工序間批次數(shù)量可相等，也可不等。因此不同工序間批次數(shù)量關系約束如下：

lij=lij′‖lij≠lij′j≠j′

(5)

(4)同一臺機器，當欲加工批次的工序與緊前加工批次工序不同時，需要加工準備時間，否則無需加工準備時間。設pijk為工件Ji第j道工序在機床Mk上加工單個工件的時間，prijk表示工件Ji第j道工序在機床Mk上的加工準備時間，cijzk表示工件Ji第j道工序的第z批次在機床Mk上的全部加工時間。工件工序單批次的加工時間約束如下：

(6)

(5)設psijzk為工件Ji第j道工序第z批次在機床Mk上的加工開始時間，ei′j′z′k為第i′ 種工件第j′ 道工序的第z′ 批次在機床Mk上的加工結(jié)束時間。設備Mk在完成對正在加工批次所有工件的加工之后，才能進行下一工序批次的加工。即批次加工不可中斷約束如下：

psijzk≥ei′j′z′k

(7)

式中，z′為z的緊前批次。

3 基于工序的分批調(diào)度算法

3.1 確定調(diào)度工藝路線

3.1.1 工藝路線的表示方法

當前生產(chǎn)模式越來越趨向于加工裝配混合進行。針對實際作業(yè)車間工件加工的分解與合成，本文采用加工順序樹[15]對這種生產(chǎn)加工過程進行形象描述。

加工順序樹是產(chǎn)品的一種工藝結(jié)構(gòu)表示形式，如圖4所示，樹的節(jié)點表示工序，有向邊是工序加工的順序約束關系，所以葉子節(jié)點是最先可以被加工的工序，根節(jié)點是最后加工的工序。工件i的加工順序樹每個節(jié)點的表示形式為Oij/lij/Mj1,Mj2,…,Mjx/pj1,pj2,…,pjx。其中，Oij為工件i的第j道工序；lij為工序Oij的批次數(shù)量；Mj1,Mj2,…,Mjx為工序Oij的可選設備；x表示工序Oij在該時刻有x臺可選加工設備；pj1,pj2,…,pjx為工序Oij在不同設備上對應的加工時間。

圖4 工件A的部分工序加工順序樹

3.1.2 可加工工序子批集確定方法

本文定義可加工工序子批集σjob包含當前可加工的所有工序子批，該集合隨著工序子批加工的進行而動態(tài)變化，以工件A為例。圖4給出了工件A的部分工序加工順序樹，加工數(shù)量為100，共有4臺加工設備。假設工序OA2和OA3的所有前驅(qū)工序都加工完畢，執(zhí)行圖4框中的工序步驟。

根據(jù)圖4，當前階段工序OA2被分為5批，工序OA3被分為2批，工序OA4被分為3批。則當前可加工工序子批集σjob為{OA2-1,OA2-2,OA2-3,OA2-4,OA2-5,OA3-1,OA3-2}，可加工工序子批集的動態(tài)更新過程如下。

(1)隨機選擇加工工序OA2-1，數(shù)量為20。

(2)OA2-1加工完成，判斷OA2-1緊后工序OA4-1可否被加工。加工OA4-1需要滿足條件1({33個OA2加工完成的半成品})和條件2({33個OA3加工完成的半成品})，條件1和條件2均不滿足。

(3)加工OA2-2，數(shù)量為20，總加工數(shù)量為40。

(4)OA2-2加工完成，判斷OA2-1緊后工序OA4-1可否被加工，條件1滿足，條件2不滿足。

(5)加工OA3-1，數(shù)量為50。

(6)判斷OA3-1緊后工序OA4-1可否被加工，條件1和2均滿足，觸發(fā)OA4-1進行加工，更新可加工工序子批集為{OA2-3,OA2-4,OA2-5,OA3-2，OA4-1}。

根據(jù)上面描述的某階段加工工序子批集動態(tài)變化過程，給出確定加工工序子批集的方法。

(8)

化簡上式可得不可加工子批工序變?yōu)榭杉庸すば虻呐卸ü剑?/p>

(9)

3.1.3 機器以及加工順序確定方法

在加工開始階段，所有機器都是空閑的，可加工工序子批集σjob中的所有工序在對應可選設備中均可以加工。如果在某個機器空閑時刻只有一道工序可在該機器上加工，那么該道工序選擇在該空閑機器上加工；如果某時刻沒有工序可以在該機器上加工，則機器處于空閑狀態(tài)，直到某可加工工序加工完成后，不可加工工序轉(zhuǎn)化為可加工工序，更新可加工工序子批集，再對機器進行選擇；如果在某一時刻存在多個工序?qū)σ慌_空閑機器M1進行爭奪，分下面三種情況進行討論。

(1)存在2道或以上的工序爭奪機器M1，且其可選設備只有M1。假設某時刻T空閑機器為M1，有兩道工序O1(M1)、O2(M1)，即O1、O2同時爭奪空閑機器M1，利用機器短用時策略[15]為M1選擇可加工工序，即選擇加工時間較短的工序進行加工。

(2)爭奪機器M1的所有工序均存在多個可選設備(包括M1在內(nèi))。假設某時刻T空閑機器為M1，有兩道工序O1(M1,Mi, …,Mx)和O2(M1,Mj, …,My)同時爭奪M1，工序O1在M1上的加工時間為p11，O2在M1上的加工時間為p21，同樣選擇加工時間較短的工序進行加工。

(3)爭奪機器M1的多個工序中，有且僅有一道工序，其可選設備唯一，即M1。假設某時刻T空閑機器為M1，有兩道工序O1(M1,Mi, …,Mx)和O2(M1)，工序O1加工時間為p11，O2加工時間為p21，(Mi, …,Mx)結(jié)束當前加工工序時間為(ei, …,ex)，那么判斷max(ei, …,ex)與T+p21:若max(ei, …,ex)>T+p21，如圖5所示，那么當前空閑機器加工工序O2；若max(ei, …,ex)p21，加工O2，否則加工O1，如圖6所示。圖5、圖6中，陰影部分表示加工設備唯一的工序在M1上的加工時間。

圖5 max(ei,…,ex)>T+p21甘特圖

圖6 max(ei, …, ex)

針對以上三種情況，如果爭奪機器工序加工時間相同，則使用長路徑策略[16]選擇加工工序。

長路徑策略即選擇比工序父節(jié)點的最短加工路徑長度更長的工序進行加工。最短路徑長度為根節(jié)點到可加工節(jié)點之間的最短加工路徑長度。計算過程中，因為每道工序的加工機器不唯一，加工時間不同，所以選擇最短的加工時間作為最短路徑時間。假設有兩道工序Ox和Oy在一臺空閑機器上的加工時間相同，工序Ox、Oy的最短加工路徑長度分別為Lx和Ly，根據(jù)長路徑策略，若Lx>Ly，那么加工Ox，反之則加工Oy。文獻[17]指出，優(yōu)先加工路徑長度更長的工序，可以使兩個可調(diào)度工序及其后續(xù)工序的總加工時間減少，實現(xiàn)工序加工的最大并行性。

3.2 關鍵路徑工序的分批算法

根據(jù)上述方法確定加工工藝路線，在工藝路線中，加工時間最長的路徑為關鍵路徑[6]，由于對關鍵路徑有效的調(diào)整對產(chǎn)品的加工時間有很大程度的影響[18]，所以本文對批量的調(diào)度研究也應用了關鍵路徑。

首先確定工件加工任務中的關鍵路徑，從最后完工的某一工序開始搜索首尾相連的工序(同時遇到其緊前工序和同一機器前鄰工序時取其機器前鄰工序)得到一條關鍵路徑[19]，關鍵路徑工序子批集σkey由關鍵路徑上所有工序子批組成。給出關鍵路徑工序分批算法步驟如下。

(1)根據(jù)調(diào)度策略及方法生成整批調(diào)度路線Rfull。

(2)整批調(diào)度路線作為當前最新調(diào)度路線和最優(yōu)調(diào)度路線：Ropt=Rnew=Rfull。

(3)確定Rnew的關鍵路徑以及關鍵路徑工序子批集σkey。

(4)σkey中的工序批次數(shù)量：lσ←lσ+1，非關鍵路徑工序子批數(shù)不變。

(5)判斷σkey中最大的分批數(shù)與給定的分批最大值llimit的大小:若maxlσ>llimit，則分批結(jié)束并返回最優(yōu)調(diào)度路線Ropt；否則,繼續(xù)步驟(6)。

(6)對所有工序子批進行調(diào)度，生成新的調(diào)度路線Rnew。

(7)Cnew表示新調(diào)度路線的最長完工時間，Copt表示最優(yōu)調(diào)度路線的最長完工時間,判斷Cnew≤Copt,若成立，則令Ropt=Rnew，轉(zhuǎn)步驟(3)；否則，最優(yōu)路線不變，直接轉(zhuǎn)步驟(3)。

圖7描述的是工件B的加工順序樹，其加工數(shù)量設定為10。

圖7 工件B加工順序樹

圖8為工件B的整批調(diào)度甘特圖，最后一道工序OB6為關鍵路徑工序，工序OB6開始加工時間為200min，記為psB6，然后向前查找關鍵工序，由于工序OB4的加工完成時間為200min，與psB6相等，所以工序OB4為關鍵路徑工序，以此類推，從調(diào)度方案最后向前查找得到的關鍵路徑為OB2→OB4→OB6，因此關鍵路徑工序子批集σkey為{OB2,OB4,OB6}。使σkey內(nèi)所有工序的批次數(shù)加1，調(diào)整加工順序樹,如圖9所示，其中工序OB2、OB4、OB6的批次數(shù)量為2。對已調(diào)整的加工順序樹中所有工序批次進行重新調(diào)度，得到工藝路線如圖10所示。

圖8 工件B整批調(diào)度甘特圖

圖9 第一次調(diào)整后順序加工樹

圖10 新調(diào)度甘特圖

更新關鍵路徑工序子批集σkey為{OB2-1,OB4-1,OB5,OB6-2}，對新的關鍵路徑工序進行再分批，直到分批量達到給定最小值，分批結(jié)束，得到加工時間相對最短的工序分批方案和加工工藝路線。

3.3 基于關鍵路徑工序分批調(diào)度算法

綜上所述，算法流程步驟如下。

(1)輸入產(chǎn)品的工藝信息，即工件工序集σfull以及各個工序之間的順序約束關系，工序加工設備集σM等。

(2)將工件工序輸入到調(diào)度模塊，利用機器短用時策略調(diào)度所有工序。①由于工件工序間有順序約束，首先要確定可加工工序子批集σjob，開始時刻所有機器為空閑。②利用短用時策略和長路徑策略確定當前空閑機器加工工序。③更新可加工工序子批數(shù)量，將已加工的工序子批數(shù)量減1。機器選擇可加工工序加工，更新可加工工序子批集σjob，如果工序子批批次數(shù)量大于1，根據(jù)可加工工序子批集確定算法動態(tài)更新可加工工序子批集σjob。④判斷σjob=?是否成立，若成立，本次調(diào)度結(jié)束，返回調(diào)度路線Ropt，轉(zhuǎn)到步驟(3);否則轉(zhuǎn)到步驟②。

(3)判斷是否所有工序批次均為1，若是，則判定當前調(diào)度為整批調(diào)度,Rnew=Ropt=Rcur，轉(zhuǎn)到步驟(5);否則Rnew=Rcur,轉(zhuǎn)到步驟(4)。

(4)判斷Tnew≤Topt若成立，則Ropt=Rnew，轉(zhuǎn)到步驟(5);否則,直接轉(zhuǎn)到步驟(5)。

(5)確定Rnew的關鍵路徑以及關鍵路徑工序子批集σkey。

(6)使子批集σkey里的工序批次數(shù)加1，即lσ←lσ+1，非關鍵路徑工序子批數(shù)量不變。

(7)判斷關鍵路徑工序子批集中最大的分批數(shù)與給定的最大分批批次的大小:若maxlσ≤llimit，則轉(zhuǎn)到步驟(2)；否則，轉(zhuǎn)到步驟(8)。

(8)返回最優(yōu)調(diào)度路線Ropt。

(9)輸出加工工藝路線和分批方案。

4 實例分析

本節(jié)通過實際加工案例進行實驗分析，驗證本文算法的可行性和有效性。算法運行環(huán)境配置為Inteli7CPU，3.4GHz主頻，8G內(nèi)存，Windows7操作系統(tǒng)，其中基于遺傳算法的調(diào)度排序交叉概率設定為0.85，變異概率為0.2，進行多次仿真實驗。

線束工藝產(chǎn)品車間，擬加工A和B兩個線束零部件(以下簡稱工件A、工件B)，加工圖紙見圖11，加工數(shù)量均為100，共有4臺加工設備。加工工序順序如圖12所示，加工工件工序加工時間見表1，抽象出虛擬加工順序樹如圖13所示。設定分批加工的最小批量為20，加工準備時間設定為單工件工序在各機器上的加工時間，通過以上算法對工件工序加工順序進行調(diào)度安排。

(a)工件A

(b)工件B圖11 線束零部件圖紙

(a)工件A

(b)工件B圖12 工序約束圖

在加工開始時刻，可加工工序為葉子節(jié)點工序，根據(jù)圖12加工順序樹，開始時刻可加工工序子批集σjob為{OA1,OA2,OB1,OB2}。開始時刻每個設備均為空閑狀態(tài)，所以根據(jù)機器選擇策略選擇合適的工序加工。如工序OB1和OB2在M1上的

表1 工件工序加工時間表

(a)工件A

(b)工件B圖13 虛擬加工順序樹

需求時間相等，所以根據(jù)長路徑策略，OB1和OB2的最短路徑長度分別為25和10，所以機器M1選擇工序OB1加工。當工序OB1加工完畢，觸發(fā)工序OB3變成可加工工序，那么當前可加工工序子批集σjob為{OB2,OB3}，由于工序OB2在機器M1上加工時間少于OB3在機器M1上加工時間，所以選擇工序OB2。根據(jù)上述步驟更新可加工工序子批集并確定加工機器，直至可加工工序子批集為空，生成調(diào)度方案如圖14所示。

圖14 整批加工調(diào)度甘特圖

由圖14可以看出，整批加工的最長完工時間長達3015min，并且機器利用率極低。整批加工后的關鍵路徑工序為OA1→OB3→OB4，對該路徑所有工序批次數(shù)量加1。圖14中黑色區(qū)域表示加工準備時間。

工件工序分批加工后，最小批量不能小于20，即最大批次不能大于5。每次分批后，對關鍵路徑和調(diào)度方案進行審查，若批量小于給定最小值，則分批結(jié)束。表2給出了基于關鍵路徑工序每次分批的結(jié)果，其中分批方案為各道工序的批

表2 基于工序分批結(jié)果

次數(shù)，用{lA1，lA2，lA3，lB1，lB2，lB3，lB4}表示。通過分析多目標值最長完工時間和總批次數(shù)可知，第五次分批為最優(yōu)分批，分批方案為{3,2,2,2,1,4,4}，總批次數(shù)量為18，最長完工時間為1870min，機器利用率達到95.79%，圖15為該次分批后調(diào)度甘特圖。而繼續(xù)分批得到的第6次、第7次調(diào)度結(jié)果的總批次數(shù)和最長完工時間相對第五次均有所增加，且機器利用率也降低至91.5%左右。

圖15 基于工序最優(yōu)(第五次)分批調(diào)度甘特圖

為了驗證本模型實驗結(jié)果的真實性和有效性，將本模型與傳統(tǒng)的基于工件分批調(diào)度模型[11]進行對比，這里以基于遺傳算法的分批調(diào)度模型為參照。表3為遺傳算法迭代100次的分批結(jié)果。其中，當lA/lB為1/2、1/3等分批次數(shù)時，最長完工時間與lA/lB為1/1分批的最長完工時間相同，故不再贅述，只列出最長完工時間變動的分批方案，在批量不小于20的要求下，最優(yōu)分批方案為{4,4,4,5,5,5,5}，總分批數(shù)量為32，最長完工時間為1900min，機器利用率達到92.11%，圖16為該分批方案調(diào)度甘特圖。

表3 基于遺傳算法分批結(jié)果

圖16 基于遺傳算法工件分批的最優(yōu)調(diào)度甘特圖

根據(jù)表4，基于關鍵路徑工序的分批調(diào)度算法在保證最長完成時間相對優(yōu)化的情況下，為每個工序安排其合適的批次數(shù)，使總加工批次由32降為18，減少了42%，機器利用率由92.1%提高到95.8%。

表4 調(diào)度方案對比表

5 結(jié)論

(1)根據(jù)工序間的不同特點，提出基于工序進行不等量分批概念，為每道工序安排其合適的批量大小。

(2)采用動態(tài)更新可加工工序子批集與機器選擇的方法，及時調(diào)整加工路線。

(3)以關鍵路徑工序為中心進行分批，并在調(diào)度過程中考慮加工準備時間，增加工藝柔性和實用性。本文從總加工批次和最長完工時間兩方面與基于工件分批的調(diào)度方案進行比較，用實驗結(jié)果驗證了基于工序分批調(diào)度的可行性和有效性。

(4)本文重點討論對工序進行分批，建模過程中采用了對關鍵路徑工序進行分批的調(diào)度方法，該解決方法相對簡單易用，比較適合加工裝配型車間的生產(chǎn)，但具有陷入局部最優(yōu)的可能。為了提高算法的全局搜索能力，同時適應更加復雜的作業(yè)車間生產(chǎn)，今后將考慮采用禁忌搜索、粒子群算法以及混合算法等方法進一步對模型進行優(yōu)化和改進。

[1] 王萬良, 吳啟迪, 宋毅. 求解作業(yè)車間調(diào)度問題的自然改進自適應遺傳算法 [J]. 系統(tǒng)工程理論與實踐, 2004, 2(2):58-62.WangWanliang,WuQidi,SongYi.ModifiedAdaptiveGeneticAlgorithmsforSolvingJob-shopSchedulingProblems[J].SystemsEngineering—Theory&Practice, 2004, 24(2):58-62.

[2]HuangRH.Multi-objectiveJob-shopSchedulingwithLotSplittingProduction[J].InternationalJournalofProductionEconomics, 2010, 124(1):206-213.

[3] 劉曉平, 徐本柱, 彭軍, 等. 工件工序可并行的作業(yè)車間調(diào)度模型與求解 [J]. 計算機輔助設計與圖形學學報, 2012, 24(1):120-127.LiuXiaoping,XuBenzhu,PengJun,etal.ModelandSolutionofJob-shopSchedulingforParallelProcesses[J].JournalofComputer-AidedDesign&ComputerGraphics, 2012, 24(1):120-127.

[4] 王海燕. 基于混合差分進化算法的制造過程分批優(yōu)化調(diào)度研究[D]. 杭州:浙江工業(yè)大學, 2011.

[5] 宋代力, 張潔. 蟻群算法求解混合流水車間分批調(diào)度問題 [J]. 計算機集成制造系統(tǒng), 2013,19(7):1640-1647.SongDaili,ZhangJie.BatchSchedulingProblemofHybridFlowShopBasedonAntColonyAlgorithm[J].ComputerIntegratedManufacturingSystems, 2013,19(7):1640-1647.

[6] 陸漢東, 何衛(wèi)平, 周旭, 等. 基于禁忌搜索的柔性作業(yè)車間分批調(diào)度 [J]. 上海交通大學學報, 2012, 46(12):2003-2008.LuHandong,HeWeiping,ZhouXu,etal.AnIntegratedTabuSearchAlgorithmfortheLotStreamingProbleminFlexibleJobShops[J].JournalofShanghaiJiaotongUniversity, 2012, 46(12):2003-2008.

[7]LowCY,HsuCM,HuangKI.BenefitsofLot-splittinginJob-shopScheduling[J].InternationalJournalofAdvancedManufacturingTechnology, 2004, 24(9/10):773-780.

[8] 潘多科, 朱劍英. 多工藝路線的批量生產(chǎn)調(diào)度優(yōu)化[J]. 機械工程學報, 2004, 40(4):36-39.PanDuoke,ZhuJianying.OptimizationMethodforaJob-shopSchedulingProblemwithAlternativeMachinesintheBatchProcess[J].ChineseJournalofMechanicalEngineering, 2004, 40(4):36-39.

[9]JeongHI,ParkJW,LeachmanRC.ABatchSplittingMethodforaJobShopSchedulingProbleminanMRPEnvironment[J].InternationalJournalofProductionResearch, 1999, 37(15):3583-3598.

[10] 孫志峻, 安進, 黃衛(wèi)清. 作業(yè)車間多工藝路線批量作業(yè)計劃優(yōu)化[J].中國機械工程, 2008, 19(2):183-187.SunZhijun,AnJin,HuangWeiqing.LotSchedulingwithMultipleProcessRoutesinJobShop[J].ChinaMechanicalEngineering, 2008, 19(2):183-187.

[11]ChanLY.TheApplicationofGeneticAlgorithmstoLotStreaminginaJobSchedulingProblem[J].InternationalJournalofProductionResearch, 2009, 47(12):3387-3412.

[12] 陳偉達，達慶利. 工藝路線可變車間作業(yè)調(diào)度的兩級遺傳算發(fā)[J].系統(tǒng)工程學報，2002,17(2):161-166.ChenWeida,DaQingli.Job-shopSchedulingwithAlterableCraftBasedonBilevelGeneticAlgorithms[J].JournalofSystemsEngineering, 2002, 17(2):161-166.

[13] 陶俐言, 聶倩, 王志峰, 等. 面向變批量生產(chǎn)的制造單元構(gòu)建方法[J]. 計算機集成制造系統(tǒng), 2014, 30(10):2411-2418.TaoLiyan,NieQian,WangZhifeng,etal.FormationTechnologyofManufacturingCellDesignforScalableBatchProduction[J].ComputerIntegratedManufacturingSystems, 2014, 30(10):2411-2418.

[14] 陳亞絨, 周余慶, 周宏明, 等. 兩階段求解的可重構(gòu)虛擬制造單元構(gòu)建方法[J]. 中國機械工程, 2013, 24(22):3024-3029.ChenYarong,ZhouYuqing,ZhouHongming,etal.VirtualManufacturingCellFormationMethodforReconfigurableManufacturingBasedonTwo-stageSolving[J].ChinaMechanicalEngineering, 2013, 24(22):3024-3029.

[15]XieZ,HaoS,YeG,etal.ANewAlgorithmforComplexProductFlexibleSchedulingwithConstraintbetweenJobs[J].Computers&IndustrialEngineering, 2009, 57(3):766-772.

[16] 謝志強, 楊靜, 楊光, 等. 可動態(tài)生成具有優(yōu)先級工序集的動態(tài)Job-Shop調(diào)度算法 [J]. 計算機學報, 2008, 31(3):502-507.XieZhiqiang,YangJing,YangGuang,etal.DynamicJob-shopSchedulingAlgorithmwithDynamicSetofOperationHavingPriority[J].ChineseJournalofComputers, 2008, 31(3):502-507.

[17] 謝志強, 辛宇, 楊靜. 基于設備空閑事件驅(qū)動的綜合調(diào)度算法[J]. 機械工程學報, 2011, 47(11):139-147.XieZhiqiang,XinYu,YangJing.IntegratedSchedulingAlgorithmBasedonEvent-drivenbyMachines’Idle[J].JournalofMechanicalEngineering, 2011, 47(11):139-147.

[18] 周馳, 高亮, 高海兵. 基于PSO的置換流水車間調(diào)度算法[J]. 電子學報, 2006, 34(11):2008-2011.ZhouChi,GaoLiang,GaoHaibing.ParticleSwarmOptimizationBasedAlgorithmforPermutationFlowShopScheduling[J].ActaElectronicaSinica, 2006, 34(11):2008-2011.

[19] 蘇子林. 車間調(diào)度問題及其進化算法分析[J].機械工程學報, 2008, 44(8):242-247.SuZilin.Job-shopSchedulingProblemandItsEvolutionAlgorithmAnalysis[J].ChineseJournalofMechanicalEngineering, 2008, 44(8):242-247.

(編輯 王旻玥)

ProblemsandSolutionsofFlexibleJob-shopSchedulingwithOperationLot-splitting

XuBenzhuJiJingFeiXiaolu

HefeiUniversityofTechnology，Hefei，230009

Consideringthateachoperationinflexiblejob-shopschedulingwithlot-splittinghaditsownappropriatelot-size,theconceptofschedulingwithlot-splittingwasproposedbasedonoperations,andaschedulingmodelwithlot-splittingwasestablishedbasedoncriticalpathoperations.Thismodelcoulddynamicallyupdatemachinablesub-lotset,updateavailablemachines,determineoptimalprocessingroutesandappropriateoperationlot-sizesthusmakespanmightbeoptimizedandtotallotquantitymightbereduced.Theexperimentalresultsshowthat,comparedwithlot-splittingbasedonworkpieces,usingtheestablishedschedulingmodelthemakespanmaybeoptimized,machineutilizationmaybeimproved,totalmachinedlotquantitymaybereduced(42%)andschedulingmanagementcomplexitymaybedecreased.

flexiblejobshop;schedulingmodelwithlot-splitting;operationlot-splitting;non-equalsizelot-splitting

2016-01-25

國家自然科學基金資助項目(61300118)；安徽省自然科學基金資助項目(1308085MF102)；安徽省科技攻關項目(1401B042009)；中央高?；究蒲袠I(yè)務費專項資金資助項目(2014HGCH0014)

TP391.7

10.3969/j.issn.1004-132X.2016.23.016