基于分支定界算法的集束型裝備調(diào)度研究

羅鈞元 任秀蕊 徐占鑫 呂博凱 常馨月 李林瑛

摘要：考慮有滯留時(shí)間約束的集束型晶圓制造裝備調(diào)度問題，其調(diào)度要同時(shí)考慮晶圓加工排序和機(jī)械手搬運(yùn)作業(yè)排序，給出了基于圖論的分支定界算法，并采用最長路徑方法確定調(diào)度目標(biāo)。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。

關(guān)鍵詞：集束型裝備；分支定界算法；晶圓制造

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）09-0242-02

Abstract：This paper addresses the cluster tools scheduling problem with residency time constraints for wafer fabrication. The scheduling object is to determine both wafer input sequence and transfer robot task sequence. A branch and bound algorithm based graph theory is proposed， and the longest path method is to determine the scheduling object. Experimental example shows that the proposed method is effective.

Key words：Cluster Tools； Branch and bound algorithm； Wafer fabrication

1 引言

集束型裝備由若干單晶圓加工模塊和一個(gè)計(jì)算機(jī)控制的物料搬運(yùn)機(jī)械手組成。晶圓在加工模塊上的停留時(shí)間可以在給定的時(shí)間上下界范圍之內(nèi)柔性變化，稱為滯留時(shí)間約束。該類調(diào)度問題與經(jīng)典的流水車間調(diào)度的區(qū)別在于：不僅要合理安排晶圓加工的排序問題，還要有效地規(guī)劃機(jī)械手搬運(yùn)作業(yè)的排序問題，因此更加復(fù)雜[1，2]。本項(xiàng)目采用JAVA語言編程實(shí)現(xiàn)基于圖論的分支定界算法，該算法設(shè)計(jì)上采用枚舉樹表示晶圓分布和機(jī)械手搬運(yùn)作業(yè)排序，利用深度搜索和廣度搜索遍歷枚舉樹，并采用有向圖的最長路徑算法確定調(diào)度目標(biāo)。

2 問題描述

為了研究集束型裝備的調(diào)度問題，本文從基于圖論的分支定界算法研究，采用遍歷枚舉樹確定晶圓分布情況、機(jī)械手搬運(yùn)作業(yè)順序等，并采用最長路徑確定調(diào)度目標(biāo)。具體的技術(shù)路線如下：首先構(gòu)建包括加工模塊能力約束和機(jī)械手搬運(yùn)能力約束的數(shù)學(xué)規(guī)劃模型，并采用基于Java的IBM CPLEX軟件求解，并作為分支定界算法的比較基準(zhǔn)。其次，研究的分支定界算法主要通過求解一系列的線性規(guī)劃問題來獲得研究問題的最優(yōu)調(diào)度周期時(shí)間。為了有效求解上述線性規(guī)劃問題，將求解T的問題轉(zhuǎn)化成有向圖中求解最長路徑的問題[3]；最后分支定界算法主要由三個(gè)分支定界樹A、B以及C組成，其中樹A、B用來枚舉可能的初始晶圓分布情況和晶圓加工順序，而樹C負(fù)責(zé)枚舉樹A或B中未被刪除的葉節(jié)點(diǎn)對(duì)應(yīng)的機(jī)械手搬運(yùn)作業(yè)順序。

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

3.1 分支定界算法

分枝定界算法由Land等[4]在20世紀(jì)60年代提出，是最為流行的規(guī)劃方法之一，其應(yīng)有非常廣泛。它的基本思想是先求出整數(shù)規(guī)劃問題A所對(duì)應(yīng)的線性規(guī)劃問題B的最優(yōu)解，如果該解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A最優(yōu)目標(biāo)函數(shù)的上界，而A的任意可行解的目標(biāo)函數(shù)值是其最優(yōu)值的下界。然后將B的可行域分成子區(qū)域（稱為分枝），逐步減少上界和增大下界，最終求得最優(yōu)解。在調(diào)度問題的研究上，分枝定界算法一直是最重要的算法之一，如文獻(xiàn)[5～8]分別提出了不同的分枝定界算法，它們的不同主要表現(xiàn)為分支規(guī)則、定界機(jī)制和上界三個(gè)方面的差異。

本文研究的分支定界算法由三個(gè)嵌套的分支定界樹組成，分別稱為分支定界樹A、樹 B和樹C。若從A樹生成的初始工件分布可得知所有工件的加工順序，則直接激活分支定界樹C；反之，則激活分支定界B樹并且接著 A樹的枚舉工作繼續(xù)枚舉剩余工件的加工順序。當(dāng)B樹枚舉完剩余工件的加工順序后，再激活分支定界樹C。A樹和B樹實(shí)質(zhì)上都是在枚舉工件的加工順序，設(shè)計(jì)它們的目的是首先刪除不可能的初始工件分布和確保所有工件的加工順序已知。其次是在A 樹或B樹枚舉完所有工件的加工順序之后，再由分支定界樹C負(fù)責(zé)隱枚舉保存下來的可能的初始工件分布和可能的所有工件的加工順序所對(duì)應(yīng)的機(jī)械手搬運(yùn)作業(yè)順序，這樣做可以縮小搜索空間和節(jié)省搜索時(shí)間。

3.2 基于有向圖的最長路徑算法求解

分支定界算法主要通過求解一系列的線性規(guī)劃問題來獲得研究問題的最優(yōu)生產(chǎn)周期。分枝定界算法中任意節(jié)點(diǎn)[o]對(duì)應(yīng)的線性規(guī)劃問題描述如下：

上述模型的目標(biāo)函數(shù)為最小化生產(chǎn)周期T，約束條件集（式（1））為節(jié)點(diǎn)o對(duì)應(yīng)的n個(gè)約束，這些約束包括加工時(shí)間約束、加工模塊能力約束和機(jī)械手能力約束。約束條件集（式（1））刻畫了集束型裝備機(jī)械手在生產(chǎn)周期內(nèi)搬運(yùn)作業(yè)之間的約束關(guān)系，決策變量[Si]和[Sj]分別表示搬運(yùn)作業(yè)i和搬運(yùn)作業(yè)j的開始時(shí)間，[hk]為生產(chǎn)周期T的整數(shù)系數(shù)，[ak]和[bk]為實(shí)數(shù)常量。約束條件集（式（2））為生產(chǎn)周期T的可行范圍約束，約束條件集（式（3））為決策變量的非負(fù)約束。由于約束條件集（式（1））具有特殊差分約束結(jié)構(gòu)，可以通過圖論方法轉(zhuǎn)化為賦權(quán)有向圖。由此，上述線性規(guī)劃問題被轉(zhuǎn)化為有向賦權(quán)圖中最長路徑問題。由于圖中弧的權(quán)值是T的線性函數(shù)f（T），若圖中有正回路，即回路上所有弧的權(quán)值總和Σf（T）>0，則該問題無解；反之，則該問題有解。周期時(shí)間T則為在可行區(qū)間[e，f]中使圖中不存在正回路的最小值。將求解的調(diào)度問題轉(zhuǎn)化成有向圖中求解最長路徑的問題，即將式（1）轉(zhuǎn)換為圖1中的節(jié)點(diǎn)、邊以及權(quán)值。

3.3 算法流程圖

以下為分支定界算法求解調(diào)度問題的算法流程圖。

4 仿真實(shí)驗(yàn)

根據(jù)如上所述的加工方式，以加工三種不同類型晶圓算例對(duì)分支定界算法進(jìn)行驗(yàn)證。該算例共包括8個(gè)加工模塊，其中1～8號(hào)加工模塊i負(fù)責(zé)晶圓加工，0號(hào)和9號(hào)模塊分別為輸入裝載室和輸出裝載室。晶圓加工時(shí)間約束、機(jī)械手搬運(yùn)時(shí)間見表1～表2。機(jī)械手空駛時(shí)間Cij=5|i-j|，其中i和j為工位號(hào)。

分支定界算法運(yùn)行大約6.00098秒后，求出此問題的最優(yōu)生產(chǎn)周期T=923.00秒，周期開始時(shí)刻的工件初始分布為{1，0，3，0，0，0，0，2，0}，從中可以看出晶圓的最優(yōu)加工順序?yàn)榫A1→晶圓2→晶圓3。

5 結(jié)論

本文提出的算法有效地解決了在具有晶圓滯留時(shí)間約束的集束型裝備的調(diào)度過程中，由于滯留約束限制而產(chǎn)生的沖突和死鎖的問題，為此類集束型裝備的調(diào)度問題提供了一個(gè)可行的方法。實(shí)驗(yàn)結(jié)果驗(yàn)證分支定界算法方法可以有效地解決集束型裝備調(diào)度問題。

參考文獻(xiàn)：

[1] 李林瑛， 盧睿， 李紹華，等. 有滯留時(shí)間約束的集束型裝備在線調(diào)度方法[J]. 系統(tǒng)仿真學(xué)報(bào)， 2017， 29（2）：337-345.

[2] 王躍崗， 車阿大. 基于混合量子進(jìn)化算法的自動(dòng)化制造單元調(diào)度[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2013， 19（9）：2193-2201.

[3] Yan P C， Chu C B， Yang N D， et al. A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows[J]. International Journal of Production Research， 2010， 48（21）：6461-6480.

[4] Land A， Doig A. An automatic method of solving discrete programming problems[J]. Econometrika， 1960， 28（3）：497-520.

[5] Garey M R， Johnson D S， Sethi R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research， 1973， 1（2）：117-129.

[6] Cho Y， Sahni S. Preemptive scheduling of independent jobs with release and due times on open， flow and job shops[J]. Operations Research， 1981， 29：511-522.

[7] Potts C N， var Wassenhove L N. a branch and bound algorithm for the total weighted tardiness problem[J]. Operations Research， 1983， 33：363-377.

[8] Sarin S C， Ahn S， Bishop A B. An improved branching scheme for the branch and bound procedure of scheduling n jobs on m machines to minimize total weighted flowtime[J]. International Journal Production Research， 1988， 26：1183-1191.