帶有跨工序約束的柔性ｊｏｂ ｓｈｏｐ調度問題
2008-12-31 00:00:00沈益民范玉順
計算機應用研究 2008年7期
摘 要：飛機制造企業的金屬加工車間是一種小批量、多品種生產，其生產指揮是一種帶有跨工序約束的柔性job shop調度問題。針對這個NPhard問題，提出一種三階段啟發式方法，通過依次完成瓶頸工作中心的判定、設備分配和任務排序，使這一問題的復雜度得以逐步降低，從而可以在多項式時間內得到有效的調度方案。實際運行表明，依據該啟發式方法產生的調度方案，其關鍵路徑的等待時間占總完工時間的比例不足1.5%，取得了滿意的效果。
關鍵詞：柔性作業車間；調度問題；跨工序約束；啟發式算法
中圖分類號：TP202．7 文獻標志碼：A
文章編號：1001-3695(2008)07-2023-04
Scheduling flexible job shop problem with interstage constraint
SHEN Yimin，FAN Yushun
(Dept. of Automation， Tsinghua University， Beijing 100084， China)
Abstract:The metalprocessing shop of airplane manufacturing is a smallbatch and multivariety production where a job shop scheduling problem with interstage constraint needs to be solved.This paper presented a threephase heuristic approach to deal with this NPhard 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;interstage constraint;heuristic algorithm
0 引言
中國航空工業第一集團公司直屬特大型企業成都飛機工業（集團）有限責任公司，是我國設計、研制和生產殲擊機的重要基地。由于具有批量小、品種多、工藝多樣化的特點，生產調度一直是其經營管理中的重要內容和難點。本文研究其金屬加工車間的作業調度問題。
該車間包括兩個柔性工作中心W1、W2。其中，拉伸中心W1包含m1=4臺拉伸機U1={M11，M12，M13，M14}，完成零件的預拉伸和拉伸；熱處理中心W2包含m2=2臺熱處理爐U2={M21（六米硝鹽爐），M22（八米電爐）}，完成零件的清洗及淬火。
設有n種零件J={J1，J2，…，Jn}，每種零件有xj(j=1，2，…，n)件。一個完整的加工流程包括如下工序：
a)換模，在拉伸工作中心W1中進行。Jj在某臺拉伸機上進行預拉伸、拉伸前，需用tj>0時間在該設備上安裝相應模具。不同零件模具各不相同，因此如果某臺拉伸機在某種零件完成全部預拉伸、拉伸之前，中途進行其他零件的加工，然后繼續進行該種零件的加工，或者某種零件在不同的設備上進行拉伸、預拉伸，則需要多次換模。
b)預拉伸。Jj的每件零件的預拉伸時間為pj≥0。受工藝限制，Jj只能在U1的一個非空子集U1jU1上的任何一臺進行加工，U1j由Jj決定。
c)清洗，預拉伸之后進行清洗。Jj的每件零件的清洗時間為cj≥0，清洗工序不占用設備時間。
d)淬火，經過清洗后，在熱處理爐上進行淬火。受工藝限制，Jj只能在U2的一個非空子集U2jU2上的任何一臺進行加工。根據Jj的尺寸和所選擇熱處理爐M2k的不同，每批可同時淬火yjk件零件，每批淬火時間為qjk。
e)拉伸，淬火后，零件在拉伸機上拉伸。Jj每件零件的拉伸時間為sj。
上述完整過程如圖1所示。在這個例子中，xj=5，yjk=2。圖中所標數字為該種零件的件次編號。
并非所有的零件均需經過換?！A拉伸→清潔→淬火→拉伸這一完整流程。特別地，當不需要預拉伸和清潔工序時，換模工序可在淬火之后或同時進行，如圖2所示。
該問題可以定義為一種特定的柔性作業車間調度問題（flexible job shop scheduling problem，FJSP）FJ2|recrc，Mj，pbatch|Cmax，即2工序柔性job shop（FJ2）、任務可以重復進入一個中心（recirculation）、每中心各設備不同（Mj）、混批加工（pbatch），并附帶如下約束：a)跨工序準備（setup）時間。預拉伸和拉伸如連續在同一設備加工，則只需一次setup時間。b)跨工序時間窗約束。淬火后應力及拉伸矯直，一般要在淬火后若干小時以內完成。因此為保持新淬火狀態，零件必須在一定時間內在拉伸機上進行拉伸。本文研究的優化目標是Cmax，即使總完成時間（makespan）最小。
1 相關文獻
由于柔性job shop調度問題拓展了傳統job shop問題，具有了更大的適應性和更高的難度[1]。目前已有一系列文獻解決FJSP，主要方法包括數學規劃方法[2]、啟發式方法[3]、遺傳算法[4]、禁忌搜索[5]、蟻群算法[6]、模擬退火等[7]。然而這些方法均未考慮跨工序約束。
文獻[8]考慮到了跨工序的設備選擇約束，并給出了相應的線性規劃和整數規劃方法，但僅適合可搶先或小規模調度問題；文獻[9]認為在job shop問題中常用的移動瓶頸啟發式方法（shifting bottleneck heuristic，SBH）[10]可以移植到柔性問題上，但該方法仍然無法應用于具有跨工序約束的FJSP；文獻[11]針對帶有跨工序約束的柔性flow shop問題提出一種遺傳算法，但不適合FJSP。
由于FJSP是NPhard問題，為了在多項式時間內獲得滿意解，本文提出一種三階段的啟發式方法，依次完成瓶頸工作中心的判定、設備分配、任務排序來解決具有跨工序約束的FJSP。最后通過實際運行數據驗證本方法的有效性。
2 算法概述
本問題的難點主要在于：a)跨工序約束，不同工作中心需要協調一致，以保證新淬火狀態，并減少換模次數；b）設備選擇的靈活性，每個任務可以選擇不同的設備進行加工；c)任務排列的靈活性，每個設備上任務可以選擇不同的排列方式。
上述三個難點造成可行調度方案空間的指數增長，很難通過一個方法一次性解決，因此本文提出一種三階段啟發式方法來逐一解決這三個問題：
（a）瓶頸工作中心判定，在不考慮跨工序約束的情況下，通過計算各工作中心的各設備負荷來獲得中心關鍵路徑下界，并據此判斷本車間的瓶頸工作中心。
（b）首先確定瓶頸工作中心的設備指派，然后通過求解至多nm1個相同任務F3‖Cmax問題，完成對非瓶頸所有任務指定相應的加工設備，從而將問題簡化為job shop問題。
（c）采用啟發式規則，同時對兩個工作中心設備上的任務進行排序，并完成整個調度工作。
3 瓶頸工作中心判定
為了有效降低可行解空間的大小，首先按照最大負荷任務優先的原則對所有零件進行一次設備預分配，并據此得到各工作中心的關鍵路徑下界，從而判定瓶頸工作中心。具體算法如下所示：
計算每個任務Jj在每個工序i的設備k的負荷：
對i從1到2循環
將集合Vik初始化為只能在設備Mik上加工的零件集合，即
計算設備Mik的當前負荷： hik=nj=1，j∈Vikhijk
循環，直到J-∪mik=1Vik為空集
從尚未分配的零件集合J-∪mik=1Vik中選擇負荷hijk最大零件Jj
在集合Uij中，選擇負荷hik較小的設備Mik
對比h1、h2，設i=b使hi最大，則將對應的工作中心Wb設置為瓶頸工作中心。
其中[a]表示取不小于a的最小整數。上述算法的計算復雜度為O(2n+m1+m2)。這一算法的結果使后續得以緊密圍繞瓶頸工作中心進行調度，從而解決了第2章中的難點a)。
4 設備指定
4．1 瓶頸工作中心
由于上述算法終止時，J-∪mik=1Vbk為空集，J=∪mik=1Vbk。且由上述算法過程可知，不同k對應的Vbk交集為空，{Vbk}mbk=1構成了對J的一個分類。
據此，若Jj∈Vbkj，即可指定零件Jj在瓶頸工作中心Wb的加工設備為Mbkj。
4．2 非瓶頸工作中心
在瓶頸工作中心加工設備已經選定的基礎上，以下進行非瓶頸工作中心加工設備的選擇。
4．2．1 構造F3|recrc|Cmax問題
本節構造一種flow shop調度問題，通過對這一調度問題的求解，就能夠給出各種零件從0時刻開始安排的最佳排程方案，并解決其設備選擇問題，即第2章中的難點b）。
對于非瓶頸工作中心Wd（d=3-b）的每一臺設備Mdk和其上可以加工的任一任務Jj，構造一個特殊的flow shop問題F3|recrc|Cmax如下：
a)三個獨立設備A1、A2、A3（分別對應拉伸設備、虛擬清潔設備、熱處理設備）；
b）xj個相同的任務在上述設備上加工；
c)設備按照相同的順序，依次完成五個工序T1~T5（分別對應換模、預拉伸、清潔、淬火和拉伸），每個工序的加工設備依次為A1、A1、A2、A3、A1；
d）T1、T3同時可以加工任意多個任務，T2、T5同時只能加工一個任務，T3同時可以加工yjk個任務；
e)每個任務在每個設備上的加工時間，依次為tj、pj、cj、qjk、sj；
f)優化目標為完成時間Cmax。
4．2．2 求解F3|recrc|Cmax問題
已經證明，以Cmax為優化目標的flow shop問題僅有F2‖Cmax是多項式時間可解的
對于如圖2的加工流程，只需對上述F3‖Cmax問題的設備環境進行適當變更即可相應處理，本文不再贅述。
4．2．3 設備選擇
對于每個任務Jj，按照如下優先順序選擇非瓶頸工序的加工設備Mdkj：a)使上述F3|recrc|Cmax問題最優解Cmax最小的Mdk優先；b)相同Cmax的設備，其負荷hdk最小的Mdk優先。
本階段的計算復雜度為O(n2m1)。
5 零件排程
通過前述兩個階段，達到了兩個目的：a）每種零件Jj的每個工序都分配給了惟一的設備Mdkj和Mbkj。b）以0時刻為基準，即假設Jj從0時刻開始加工，startij、endij給出了Jj在兩個工作中心開始、完成加工的相對時間。
在此基礎上，第三階段對零件進行排序，計算各工序加工的絕對時間，即解決第2章中的難點c)。算法流程如下所示：
將每一設備的空閑時間窗設置為0到無窮大（或一個足夠大的正數）
啟發式優先規則的原理在于：a)優先安排Wb中負荷hbk大的設備可加工的零件，能夠使瓶頸生產設備的利用率盡量提高；b)優先安排Tj小的零件有助于降低設備空閑時間；c)由于隨著調度的進行，大的時間窗會被逐步分割為小的時間窗，負荷hbjk大的零件優先安排，有助于提高時間窗利用效率。
本階段的算法復雜度為O(n2)。
6 實際運用效果
將本文方法應用于成飛集團金屬加工車間2007年9~11月的實際生產任務，該組任務包含432個批次任務，涉及不同的零件425種、7 438件，平均每種零件17.50件，屬于典型的小批量、多品種生產。
經過本算法第一步后，各設備負荷下界如表1所示。
熱處理爐合計55 245432
從表1中得出，拉伸、熱處理中心的關鍵路徑下界分別為98 710和32 065 min，因此拉伸機被確定為關鍵工作中心。
運行第二、第三階段算法后得到一種調度方案，按照這一調度方案，自9月1日開始投產到11月9日所有任務全部完成，歷時70天。所有設備的完工總時間及利用率如表2所示。
由于拉伸機M11負荷最重，M11的加工流程是整個調度問題的關鍵路徑。在調度方案中，M11的總時間為99 920 min，相比其有效工作負荷98 710 min，僅超出不足1.5%，等待時間僅1 210 min，設備利用非常充分。因此該調度結果已極為接近最優解。將整個生產期間的投產任務負荷按旬進行統計，如圖6所示。
從圖6中可以看出，各設備的負荷未出現明顯起伏。各加工設備，特別是主要的重負荷設備（M11和M12）呈現均衡投產的良好態勢。
上述調度結果是在保證了預拉伸、淬火、拉伸連續進行的條件下達成的，因此能夠確?？绻ば虻臅r間窗和設備選擇約束得以滿足。不僅如此，這樣的連續加工調度方案，在實際運行中便于執行，且對于各種異常情況（如設備故障、訂單變更）的適應能力很強。
7 結束語
Job shop是調度問題中最困難的問題之一，而柔性job shop問題FJSP又是其中的難點。本文針對飛機制造中的一個具體FJSP提出一種三階段調度算法，能夠在多項式時間O(nm1)內獲得滿意解，具有很強的實用性。
這一方法，可以很容易地擴展到更廣泛的場合，如：a)帶有設備時間窗的場合。當設備需要定期保養、維修時，可將第三階段第一步的空閑時間窗進行裁減，使之反映相應的停工時間，即可繼續使用本文算法。b）帶有投產、完工時間約束的場合。調整第三階段的啟發式優先規則，使投產、完工時間處于時間窗以外的任務具有最低的優先級即可。進一步的工作，是對該調度問題的在線調度算法進行研究，以支持各種滾動任務的調度。
參考文獻：
［1］吳秀麗，孫樹棟，楊展，等.多目標柔性job shop調度問題的技術現狀和發展趨勢[J].計算機應用研究，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]陳華平，古春生.隨機柔性flow shop加權完成時間調度問題的啟發式策略性能分析[J].控制理論與應用，2006，23(4):523-525.
[4]張超勇，饒運清，李培根，等.柔性作業車間調度問題的兩級遺傳算法[J].機械工程學報，2007，43(4):119124.[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):103115.
[6]VINCENT T，NICOLAS M，FABRICE T，et al.An ant colony optimization algorithm to solve a 2machine bicriteria flow shop scheduling problem[J].European Journal of Operational Research，2002，142(2): 250-257.
[7]余建軍，孫樹棟，王軍強，等.免疫模擬退火算法及其在柔性動態job shop中的應用[J].中國機械工程，2007，18(7): 793799.
[8]沈益民，范玉順.調度問題微結構及其柔性優化[J].自動化學報，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 Yimin，FAN Yushun，ZENG Sen.Switching serialnumber coding scheme and its application in FFS scheduling problem with interstage 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:SpringerVerlag，1998:165.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>
