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

徐本柱 吉 靖 費(fèi)曉璐

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

?

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

徐本柱 吉 靖 費(fèi)曉璐

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

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

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

0 引言

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

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

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

1 問(wèn)題描述

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

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

圖1 工件P的加工工序

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

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

圖2 工件工序加工裝配圖

圖3 工序約束關(guān)系圖

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

根據(jù)問(wèn)題的描述和實(shí)際需要，建立數(shù)學(xué)模型，目標(biāo)函數(shù)如下。

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

(1)

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

(2)

本文屬于多目標(biāo)求解問(wèn)題，在優(yōu)化f1的同時(shí)，盡可能減小f2，以降低車(chē)間管理復(fù)雜度。

批量加工相關(guān)的約束條件如下。

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

(3)

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

(4)

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

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

(5)

(4)同一臺(tái)機(jī)器，當(dāng)欲加工批次的工序與緊前加工批次工序不同時(shí)，需要加工準(zhǔn)備時(shí)間，否則無(wú)需加工準(zhǔn)備時(shí)間。設(shè)pijk為工件Ji第j道工序在機(jī)床Mk上加工單個(gè)工件的時(shí)間，prijk表示工件Ji第j道工序在機(jī)床Mk上的加工準(zhǔn)備時(shí)間，cijzk表示工件Ji第j道工序的第z批次在機(jī)床Mk上的全部加工時(shí)間。工件工序單批次的加工時(shí)間約束如下：

(6)

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

psijzk≥ei′j′z′k

(7)

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

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

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

3.1.1 工藝路線(xiàn)的表示方法

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

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

圖4 工件A的部分工序加工順序樹(shù)

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

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

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

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

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

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

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

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

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

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

(8)

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

(9)

3.1.3 機(jī)器以及加工順序確定方法

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

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

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

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

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

圖6 max(ei, …, ex)

針對(duì)以上三種情況，如果爭(zhēng)奪機(jī)器工序加工時(shí)間相同，則使用長(zhǎng)路徑策略[16]選擇加工工序。

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

3.2 關(guān)鍵路徑工序的分批算法

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

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

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

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

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

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

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

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

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

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

圖7 工件B加工順序樹(shù)

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

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

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

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

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

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

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

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

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

(3)判斷是否所有工序批次均為1，若是，則判定當(dāng)前調(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的關(guān)鍵路徑以及關(guān)鍵路徑工序子批集σkey。

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

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

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

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

4 實(shí)例分析

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

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

(a)工件A

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

(a)工件A

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

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

表1 工件工序加工時(shí)間表

(a)工件A

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

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

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

由圖14可以看出，整批加工的最長(zhǎng)完工時(shí)間長(zhǎng)達(dá)3015min，并且機(jī)器利用率極低。整批加工后的關(guān)鍵路徑工序?yàn)镺A1→OB3→OB4，對(duì)該路徑所有工序批次數(shù)量加1。圖14中黑色區(qū)域表示加工準(zhǔn)備時(shí)間。

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

(3)以關(guān)鍵路徑工序?yàn)橹行倪M(jìn)行分批，并在調(diào)度過(guò)程中考慮加工準(zhǔn)備時(shí)間，增加工藝柔性和實(shí)用性。本文從總加工批次和最長(zhǎng)完工時(shí)間兩方面與基于工件分批的調(diào)度方案進(jìn)行比較，用實(shí)驗(yàn)結(jié)果驗(yàn)證了基于工序分批調(diào)度的可行性和有效性。

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

[1] 王萬(wàn)良, 吳啟迪, 宋毅. 求解作業(yè)車(chē)間調(diào)度問(wèn)題的自然改進(jìn)自適應(yīng)遺傳算法 [J]. 系統(tǒng)工程理論與實(shí)踐, 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è)車(chē)間調(diào)度模型與求解 [J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2012, 24(1):120-127.LiuXiaoping,XuBenzhu,PengJun,etal.ModelandSolutionofJob-shopSchedulingforParallelProcesses[J].JournalofComputer-AidedDesign&ComputerGraphics, 2012, 24(1):120-127.

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

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

[6] 陸漢東, 何衛(wèi)平, 周旭, 等. 基于禁忌搜索的柔性作業(yè)車(chē)間分批調(diào)度 [J]. 上海交通大學(xué)學(xué)報(bào), 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] 潘多科, 朱劍英. 多工藝路線(xiàn)的批量生產(chǎn)調(diào)度優(yōu)化[J]. 機(jī)械工程學(xué)報(bào), 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] 孫志峻, 安進(jìn), 黃衛(wèi)清. 作業(yè)車(chē)間多工藝路線(xiàn)批量作業(yè)計(jì)劃優(yōu)化[J].中國(guó)機(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] 陳偉達(dá)，達(dá)慶利. 工藝路線(xiàn)可變車(chē)間作業(yè)調(diào)度的兩級(jí)遺傳算發(fā)[J].系統(tǒng)工程學(xué)報(bào)，2002,17(2):161-166.ChenWeida,DaQingli.Job-shopSchedulingwithAlterableCraftBasedonBilevelGeneticAlgorithms[J].JournalofSystemsEngineering, 2002, 17(2):161-166.

[13] 陶俐言, 聶倩, 王志峰, 等. 面向變批量生產(chǎn)的制造單元構(gòu)建方法[J]. 計(jì)算機(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]. 中國(guó)機(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] 謝志強(qiáng), 楊靜, 楊光, 等. 可動(dòng)態(tài)生成具有優(yōu)先級(jí)工序集的動(dòng)態(tài)Job-Shop調(diào)度算法 [J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(3):502-507.XieZhiqiang,YangJing,YangGuang,etal.DynamicJob-shopSchedulingAlgorithmwithDynamicSetofOperationHavingPriority[J].ChineseJournalofComputers, 2008, 31(3):502-507.

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

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

[19] 蘇子林. 車(chē)間調(diào)度問(wèn)題及其進(jìn)化算法分析[J].機(jī)械工程學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61300118)；安徽省自然科學(xué)基金資助項(xiàng)目(1308085MF102)；安徽省科技攻關(guān)項(xiàng)目(1401B042009)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目(2014HGCH0014)

TP391.7

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