帶有跨工序約束的柔性ｊｏｂ ｓｈｏｐ調(diào)度問(wèn)題

摘 要：飛機(jī)制造企業(yè)的金屬加工車(chē)間是一種小批量、多品種生產(chǎn)，其生產(chǎn)指揮是一種帶有跨工序約束的柔性job shop調(diào)度問(wèn)題。針對(duì)這個(gè)NPhard問(wèn)題，提出一種三階段啟發(fā)式方法，通過(guò)依次完成瓶頸工作中心的判定、設(shè)備分配和任務(wù)排序，使這一問(wèn)題的復(fù)雜度得以逐步降低，從而可以在多項(xiàng)式時(shí)間內(nèi)得到有效的調(diào)度方案。實(shí)際運(yùn)行表明，依據(jù)該啟發(fā)式方法產(chǎn)生的調(diào)度方案，其關(guān)鍵路徑的等待時(shí)間占總完工時(shí)間的比例不足1.5%，取得了滿(mǎn)意的效果。

關(guān)鍵詞：柔性作業(yè)車(chē)間；調(diào)度問(wèn)題；跨工序約束；啟發(fā)式算法

中圖分類(lèi)號(hào)：TP202．7 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)07-2023-04



Scheduling flexible job shop problem with interstage constraint

SHEN Yimin，F(xiàn)AN Yushun

(Dept. of Automation， Tsinghua University， Beijing 100084， China)

Abstract:The metalprocessing shop of airplane manufacturing is a smallbatch and multivariety production where a job shop scheduling problem with interstage constraint needs to be solved.This paper presented a threephase heuristic approach to deal with this NPhard problem. During the process of determining the bottleneck work center， arranging the devices， and ordering the jobs，reduced the complexity of the problem gradually. Therefore obtained an effective solution within polynomial time. Application sample shows that the heuristic approach is satisfactory as the idle time of the critical path is less than 1.5% of the completing time.

Key words:flexible job shop;scheduling problem;interstage constraint;heuristic algorithm

0 引言

中國(guó)航空工業(yè)第一集團(tuán)公司直屬特大型企業(yè)成都飛機(jī)工業(yè)（集團(tuán)）有限責(zé)任公司，是我國(guó)設(shè)計(jì)、研制和生產(chǎn)殲擊機(jī)的重要基地。由于具有批量小、品種多、工藝多樣化的特點(diǎn)，生產(chǎn)調(diào)度一直是其經(jīng)營(yíng)管理中的重要內(nèi)容和難點(diǎn)。本文研究其金屬加工車(chē)間的作業(yè)調(diào)度問(wèn)題。

該車(chē)間包括兩個(gè)柔性工作中心W1、W2。其中，拉伸中心W1包含m1=4臺(tái)拉伸機(jī)U1={M11，M12，M13，M14}，完成零件的預(yù)拉伸和拉伸；熱處理中心W2包含m2=2臺(tái)熱處理爐U2={M21（六米硝鹽爐），M22（八米電爐）}，完成零件的清洗及淬火。

設(shè)有n種零件J={J1，J2，…，Jn}，每種零件有xj(j=1，2，…，n)件。一個(gè)完整的加工流程包括如下工序：

a)換模，在拉伸工作中心W1中進(jìn)行。Jj在某臺(tái)拉伸機(jī)上進(jìn)行預(yù)拉伸、拉伸前，需用tj>0時(shí)間在該設(shè)備上安裝相應(yīng)模具。不同零件模具各不相同，因此如果某臺(tái)拉伸機(jī)在某種零件完成全部預(yù)拉伸、拉伸之前，中途進(jìn)行其他零件的加工，然后繼續(xù)進(jìn)行該種零件的加工，或者某種零件在不同的設(shè)備上進(jìn)行拉伸、預(yù)拉伸，則需要多次換模。

b)預(yù)拉伸。Jj的每件零件的預(yù)拉伸時(shí)間為pj≥0。受工藝限制，Jj只能在U1的一個(gè)非空子集U1jU1上的任何一臺(tái)進(jìn)行加工，U1j由Jj決定。

c)清洗，預(yù)拉伸之后進(jìn)行清洗。Jj的每件零件的清洗時(shí)間為cj≥0，清洗工序不占用設(shè)備時(shí)間。

d)淬火，經(jīng)過(guò)清洗后，在熱處理爐上進(jìn)行淬火。受工藝限制，Jj只能在U2的一個(gè)非空子集U2jU2上的任何一臺(tái)進(jìn)行加工。根據(jù)Jj的尺寸和所選擇熱處理爐M2k的不同，每批可同時(shí)淬火yjk件零件，每批淬火時(shí)間為qjk。

e)拉伸，淬火后，零件在拉伸機(jī)上拉伸。Jj每件零件的拉伸時(shí)間為sj。

上述完整過(guò)程如圖1所示。在這個(gè)例子中，xj=5，yjk=2。圖中所標(biāo)數(shù)字為該種零件的件次編號(hào)。



并非所有的零件均需經(jīng)過(guò)換模→預(yù)拉伸→清潔→淬火→拉伸這一完整流程。特別地，當(dāng)不需要預(yù)拉伸和清潔工序時(shí)，換模工序可在淬火之后或同時(shí)進(jìn)行，如圖2所示。

該問(wèn)題可以定義為一種特定的柔性作業(yè)車(chē)間調(diào)度問(wèn)題（flexible job shop scheduling problem，F(xiàn)JSP）FJ2|recrc，Mj，pbatch|Cmax，即2工序柔性job shop（FJ2）、任務(wù)可以重復(fù)進(jìn)入一個(gè)中心（recirculation）、每中心各設(shè)備不同（Mj）、混批加工（pbatch），并附帶如下約束：a)跨工序準(zhǔn)備（setup）時(shí)間。預(yù)拉伸和拉伸如連續(xù)在同一設(shè)備加工，則只需一次setup時(shí)間。b)跨工序時(shí)間窗約束。淬火后應(yīng)力及拉伸矯直，一般要在淬火后若干小時(shí)以?xún)?nèi)完成。因此為保持新淬火狀態(tài)，零件必須在一定時(shí)間內(nèi)在拉伸機(jī)上進(jìn)行拉伸。本文研究的優(yōu)化目標(biāo)是Cmax，即使總完成時(shí)間（makespan）最小。

1 相關(guān)文獻(xiàn)

由于柔性job shop調(diào)度問(wèn)題拓展了傳統(tǒng)job shop問(wèn)題，具有了更大的適應(yīng)性和更高的難度^[1]。目前已有一系列文獻(xiàn)解決FJSP，主要方法包括數(shù)學(xué)規(guī)劃方法^[2]、啟發(fā)式方法^[3]、遺傳算法^[4]、禁忌搜索^[5]、蟻群算法^[6]、模擬退火等^[7]。然而這些方法均未考慮跨工序約束。

文獻(xiàn)[8]考慮到了跨工序的設(shè)備選擇約束，并給出了相應(yīng)的線(xiàn)性規(guī)劃和整數(shù)規(guī)劃方法，但僅適合可搶先或小規(guī)模調(diào)度問(wèn)題；文獻(xiàn)[9]認(rèn)為在job shop問(wèn)題中常用的移動(dòng)瓶頸啟發(fā)式方法（shifting bottleneck heuristic，SBH）^[10]可以移植到柔性問(wèn)題上，但該方法仍然無(wú)法應(yīng)用于具有跨工序約束的FJSP；文獻(xiàn)[11]針對(duì)帶有跨工序約束的柔性flow shop問(wèn)題提出一種遺傳算法，但不適合FJSP。

由于FJSP是NPhard問(wèn)題，為了在多項(xiàng)式時(shí)間內(nèi)獲得滿(mǎn)意解，本文提出一種三階段的啟發(fā)式方法，依次完成瓶頸工作中心的判定、設(shè)備分配、任務(wù)排序來(lái)解決具有跨工序約束的FJSP。最后通過(guò)實(shí)際運(yùn)行數(shù)據(jù)驗(yàn)證本方法的有效性。

2 算法概述

本問(wèn)題的難點(diǎn)主要在于：a)跨工序約束，不同工作中心需要協(xié)調(diào)一致，以保證新淬火狀態(tài)，并減少換模次數(shù)；b）設(shè)備選擇的靈活性，每個(gè)任務(wù)可以選擇不同的設(shè)備進(jìn)行加工；c)任務(wù)排列的靈活性，每個(gè)設(shè)備上任務(wù)可以選擇不同的排列方式。

上述三個(gè)難點(diǎn)造成可行調(diào)度方案空間的指數(shù)增長(zhǎng)，很難通過(guò)一個(gè)方法一次性解決，因此本文提出一種三階段啟發(fā)式方法來(lái)逐一解決這三個(gè)問(wèn)題：

（a）瓶頸工作中心判定，在不考慮跨工序約束的情況下，通過(guò)計(jì)算各工作中心的各設(shè)備負(fù)荷來(lái)獲得中心關(guān)鍵路徑下界，并據(jù)此判斷本車(chē)間的瓶頸工作中心。

（b）首先確定瓶頸工作中心的設(shè)備指派，然后通過(guò)求解至多nm1個(gè)相同任務(wù)F3‖Cmax問(wèn)題，完成對(duì)非瓶頸所有任務(wù)指定相應(yīng)的加工設(shè)備，從而將問(wèn)題簡(jiǎn)化為job shop問(wèn)題。

（c）采用啟發(fā)式規(guī)則，同時(shí)對(duì)兩個(gè)工作中心設(shè)備上的任務(wù)進(jìn)行排序，并完成整個(gè)調(diào)度工作。

3 瓶頸工作中心判定

為了有效降低可行解空間的大小，首先按照最大負(fù)荷任務(wù)優(yōu)先的原則對(duì)所有零件進(jìn)行一次設(shè)備預(yù)分配，并據(jù)此得到各工作中心的關(guān)鍵路徑下界，從而判定瓶頸工作中心。具體算法如下所示：

計(jì)算每個(gè)任務(wù)Jj在每個(gè)工序i的設(shè)備k的負(fù)荷：

對(duì)i從1到2循環(huán)

將集合Vik初始化為只能在設(shè)備Mik上加工的零件集合，即

計(jì)算設(shè)備Mik的當(dāng)前負(fù)荷： hik=nj=1，j∈Vikhijk

循環(huán)，直到J-∪mik=1Vik為空集

從尚未分配的零件集合J-∪mik=1Vik中選擇負(fù)荷hijk最大零件Jj

在集合Uij中，選擇負(fù)荷hik較小的設(shè)備Mik

對(duì)比h1、h2，設(shè)i=b使hi最大，則將對(duì)應(yīng)的工作中心Wb設(shè)置為瓶頸工作中心。

其中[a]表示取不小于a的最小整數(shù)。上述算法的計(jì)算復(fù)雜度為O(2n+m1+m2)。這一算法的結(jié)果使后續(xù)得以緊密?chē)@瓶頸工作中心進(jìn)行調(diào)度，從而解決了第2章中的難點(diǎn)a)。

4 設(shè)備指定

4．1 瓶頸工作中心

由于上述算法終止時(shí)，J-∪mik=1Vbk為空集，J=∪mik=1Vbk。且由上述算法過(guò)程可知，不同k對(duì)應(yīng)的Vbk交集為空，{Vbk}mbk=1構(gòu)成了對(duì)J的一個(gè)分類(lèi)。

據(jù)此，若Jj∈Vbkj，即可指定零件Jj在瓶頸工作中心Wb的加工設(shè)備為Mbkj。

4．2 非瓶頸工作中心

在瓶頸工作中心加工設(shè)備已經(jīng)選定的基礎(chǔ)上，以下進(jìn)行非瓶頸工作中心加工設(shè)備的選擇。

4．2．1 構(gòu)造F3|recrc|Cmax問(wèn)題

本節(jié)構(gòu)造一種flow shop調(diào)度問(wèn)題，通過(guò)對(duì)這一調(diào)度問(wèn)題的求解，就能夠給出各種零件從0時(shí)刻開(kāi)始安排的最佳排程方案，并解決其設(shè)備選擇問(wèn)題，即第2章中的難點(diǎn)b）。

對(duì)于非瓶頸工作中心Wd（d=3-b）的每一臺(tái)設(shè)備Mdk和其上可以加工的任一任務(wù)Jj，構(gòu)造一個(gè)特殊的flow shop問(wèn)題F3|recrc|Cmax如下：

a)三個(gè)獨(dú)立設(shè)備A1、A2、A3（分別對(duì)應(yīng)拉伸設(shè)備、虛擬清潔設(shè)備、熱處理設(shè)備）；

b）xj個(gè)相同的任務(wù)在上述設(shè)備上加工；

c)設(shè)備按照相同的順序，依次完成五個(gè)工序T1~T5（分別對(duì)應(yīng)換模、預(yù)拉伸、清潔、淬火和拉伸），每個(gè)工序的加工設(shè)備依次為A1、A1、A2、A3、A1；

d）T1、T3同時(shí)可以加工任意多個(gè)任務(wù)，T2、T5同時(shí)只能加工一個(gè)任務(wù)，T3同時(shí)可以加工yjk個(gè)任務(wù)；

e)每個(gè)任務(wù)在每個(gè)設(shè)備上的加工時(shí)間，依次為tj、pj、cj、qjk、sj；

f)優(yōu)化目標(biāo)為完成時(shí)間Cmax。

4．2．2 求解F3|recrc|Cmax問(wèn)題

已經(jīng)證明，以Cmax為優(yōu)化目標(biāo)的flow shop問(wèn)題僅有F2‖Cmax是多項(xiàng)式時(shí)間可解的

對(duì)于如圖2的加工流程，只需對(duì)上述F3‖Cmax問(wèn)題的設(shè)備環(huán)境進(jìn)行適當(dāng)變更即可相應(yīng)處理，本文不再贅述。

4．2．3 設(shè)備選擇

對(duì)于每個(gè)任務(wù)Jj，按照如下優(yōu)先順序選擇非瓶頸工序的加工設(shè)備Mdkj：a)使上述F3|recrc|Cmax問(wèn)題最優(yōu)解Cmax最小的Mdk優(yōu)先；b)相同Cmax的設(shè)備，其負(fù)荷hdk最小的Mdk優(yōu)先。

本階段的計(jì)算復(fù)雜度為O(n2m1)。

5 零件排程

通過(guò)前述兩個(gè)階段，達(dá)到了兩個(gè)目的：a）每種零件Jj的每個(gè)工序都分配給了惟一的設(shè)備Mdkj和Mbkj。b）以0時(shí)刻為基準(zhǔn)，即假設(shè)Jj從0時(shí)刻開(kāi)始加工，startij、endij給出了Jj在兩個(gè)工作中心開(kāi)始、完成加工的相對(duì)時(shí)間。

在此基礎(chǔ)上，第三階段對(duì)零件進(jìn)行排序，計(jì)算各工序加工的絕對(duì)時(shí)間，即解決第2章中的難點(diǎn)c)。算法流程如下所示：

將每一設(shè)備的空閑時(shí)間窗設(shè)置為0到無(wú)窮大（或一個(gè)足夠大的正數(shù)）

啟發(fā)式優(yōu)先規(guī)則的原理在于：a)優(yōu)先安排Wb中負(fù)荷hbk大的設(shè)備可加工的零件，能夠使瓶頸生產(chǎn)設(shè)備的利用率盡量提高；b)優(yōu)先安排Tj小的零件有助于降低設(shè)備空閑時(shí)間；c)由于隨著調(diào)度的進(jìn)行，大的時(shí)間窗會(huì)被逐步分割為小的時(shí)間窗，負(fù)荷hbjk大的零件優(yōu)先安排，有助于提高時(shí)間窗利用效率。

本階段的算法復(fù)雜度為O(n2)。

6 實(shí)際運(yùn)用效果

將本文方法應(yīng)用于成飛集團(tuán)金屬加工車(chē)間2007年9~11月的實(shí)際生產(chǎn)任務(wù)，該組任務(wù)包含432個(gè)批次任務(wù)，涉及不同的零件425種、7 438件，平均每種零件17.50件，屬于典型的小批量、多品種生產(chǎn)。

經(jīng)過(guò)本算法第一步后，各設(shè)備負(fù)荷下界如表1所示。

熱處理爐合計(jì)55 245432

從表1中得出，拉伸、熱處理中心的關(guān)鍵路徑下界分別為98 710和32 065 min，因此拉伸機(jī)被確定為關(guān)鍵工作中心。

運(yùn)行第二、第三階段算法后得到一種調(diào)度方案，按照這一調(diào)度方案，自9月1日開(kāi)始投產(chǎn)到11月9日所有任務(wù)全部完成，歷時(shí)70天。所有設(shè)備的完工總時(shí)間及利用率如表2所示。

由于拉伸機(jī)M11負(fù)荷最重，M11的加工流程是整個(gè)調(diào)度問(wèn)題的關(guān)鍵路徑。在調(diào)度方案中，M11的總時(shí)間為99 920 min，相比其有效工作負(fù)荷98 710 min，僅超出不足1.5%，等待時(shí)間僅1 210 min，設(shè)備利用非常充分。因此該調(diào)度結(jié)果已極為接近最優(yōu)解。將整個(gè)生產(chǎn)期間的投產(chǎn)任務(wù)負(fù)荷按旬進(jìn)行統(tǒng)計(jì)，如圖6所示。

從圖6中可以看出，各設(shè)備的負(fù)荷未出現(xiàn)明顯起伏。各加工設(shè)備，特別是主要的重負(fù)荷設(shè)備（M11和M12）呈現(xiàn)均衡投產(chǎn)的良好態(tài)勢(shì)。

上述調(diào)度結(jié)果是在保證了預(yù)拉伸、淬火、拉伸連續(xù)進(jìn)行的條件下達(dá)成的，因此能夠確保跨工序的時(shí)間窗和設(shè)備選擇約束得以滿(mǎn)足。不僅如此，這樣的連續(xù)加工調(diào)度方案，在實(shí)際運(yùn)行中便于執(zhí)行，且對(duì)于各種異常情況（如設(shè)備故障、訂單變更）的適應(yīng)能力很強(qiáng)。

7 結(jié)束語(yǔ)

Job shop是調(diào)度問(wèn)題中最困難的問(wèn)題之一，而柔性job shop問(wèn)題FJSP又是其中的難點(diǎn)。本文針對(duì)飛機(jī)制造中的一個(gè)具體FJSP提出一種三階段調(diào)度算法，能夠在多項(xiàng)式時(shí)間O(nm1)內(nèi)獲得滿(mǎn)意解，具有很強(qiáng)的實(shí)用性。

這一方法，可以很容易地?cái)U(kuò)展到更廣泛的場(chǎng)合，如：a)帶有設(shè)備時(shí)間窗的場(chǎng)合。當(dāng)設(shè)備需要定期保養(yǎng)、維修時(shí)，可將第三階段第一步的空閑時(shí)間窗進(jìn)行裁減，使之反映相應(yīng)的停工時(shí)間，即可繼續(xù)使用本文算法。b）帶有投產(chǎn)、完工時(shí)間約束的場(chǎng)合。調(diào)整第三階段的啟發(fā)式優(yōu)先規(guī)則，使投產(chǎn)、完工時(shí)間處于時(shí)間窗以外的任務(wù)具有最低的優(yōu)先級(jí)即可。進(jìn)一步的工作，是對(duì)該調(diào)度問(wèn)題的在線(xiàn)調(diào)度算法進(jìn)行研究，以支持各種滾動(dòng)任務(wù)的調(diào)度。

參考文獻(xiàn)：

［1］吳秀麗，孫樹(shù)棟，楊展，等.多目標(biāo)柔性job shop調(diào)度問(wèn)題的技術(shù)現(xiàn)狀和發(fā)展趨勢(shì)[J].計(jì)算機(jī)應(yīng)用研究，2007，24(3): 1-9.

[2]TORABI S A，KARIMI B，GHOMI S M T F.The common cycle economic lot scheduling in flexible job shops:the finite horizon case[J].International Journal of Production Economics，2005，97(1): 52-65.

[3]陳華平，古春生.隨機(jī)柔性flow shop加權(quán)完成時(shí)間調(diào)度問(wèn)題的啟發(fā)式策略性能分析[J].控制理論與應(yīng)用，2006，23(4):523-525.

[4]張超勇，饒運(yùn)清，李培根，等.柔性作業(yè)車(chē)間調(diào)度問(wèn)題的兩級(jí)遺傳算法[J].機(jī)械工程學(xué)報(bào)，2007，43(4):119124.[5]SCRICH R C，ARMENTANO V A，LAGUNA M.Tardiness minimization in a flexible job shop:a tabu search approach[J].Journal of Intelligent Manufacturing，2004，15(1):103115.

[6]VINCENT T，NICOLAS M，F(xiàn)ABRICE T，et al.An ant colony optimization algorithm to solve a 2machine bicriteria flow shop scheduling problem[J].European Journal of Operational Research，2002，142(2): 250-257.

[7]余建軍，孫樹(shù)棟，王軍強(qiáng)，等.免疫模擬退火算法及其在柔性動(dòng)態(tài)job shop中的應(yīng)用[J].中國(guó)機(jī)械工程，2007，18(7): 793799.

[8]沈益民，范玉順.調(diào)度問(wèn)題微結(jié)構(gòu)及其柔性?xún)?yōu)化[J].自動(dòng)化學(xué)報(bào)，2006，32(2): 264-270.

[9]PINEDO M.Scheduling:theory，algorithms，and systems[M]. 2nd ed. Beijing: Tsinghua University Press，2005: 181.

[10]ADAMS J， BALAS E， ZAWACK D.The shifting bottleneck procedure for job shop scheduling[J].Management Science，1988，34(3):391-401.

[11]SHEN Yimin，F(xiàn)AN Yushun，ZENG Sen.Switching serialnumber coding scheme and its application in FFS scheduling problem with interstage constraints[C]//Proc of the 3rd International Conference on Natural Computation.Los Alamitos: IEEE Computer Society Press，2007:375-379.

[12]BRUCKER P.Scheduling algorithm[M].2nd ed.Berlin:SpringerVerlag，1998:165.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”