基于兩階段調度的制造單元協同調度算法研究

牛力，韓小汀

1.中國人民大學數據工程與知識工程教育部重點實驗室，北京 100872

2.中國人民大學信息資源管理學院，北京 100872

3.北京航空航天大學經濟管理學院，北京 100191

基于兩階段調度的制造單元協同調度算法研究

牛力1，2，韓小汀3

1.中國人民大學數據工程與知識工程教育部重點實驗室，北京 100872

2.中國人民大學信息資源管理學院，北京 100872

3.北京航空航天大學經濟管理學院，北京 100191

1 引言

作為成組技術（Group Technology，GT）的延伸，單元制造技術（Cellular Manufacturing，CM）[1]結合工作車間方式的靈活性和流水線方式的高效率，能以近似剛性流水線的費用來生產多品種小批量的產品[2]，以其特有的優勢吸引了眾多研究人員的注意[3-5]。CM在包括減少物料處理成本、準備時間、在制品庫存、完工時間等方面有較大的優勢[6]。單元構建、單元布局和單元管理與調度是制造單元研究的三個主要方面[6]。當前大部分研究仍注重于單元構建和單元布局方面[2，4，6-8]，而生產調度和單元管理方面成果極其有限，特別在基于單元制造技術的調度算法研究方面的工作還沒有深入展開。因此，如何將先進有效地制造單元技術運用到生產調度優化問題中，并在此基礎上拓展調度算法研究，無論對于發展基于制造單元的調度問題理論研究還是豐富生產調度算法研究，都具有很強的理論價值和現實意義。

調度問題的NP-難屬性決定了如果大規模的調度問題簡單套用小規模問題的求解方法，計算時間和搜索空間產生的組合爆炸將使得求解性能很差[9]，特別是面對多制造單元，且存在跨單元生產的制造環境下，現有的調度算法則無法直接進行求解。對于單元調度的求解方法，不同的學者給出了不同的解決方案。其中，在進行大規模調度分解方面，文獻[10]按照單元制造的思路對調度環境進行分解，然后對獨立的制造單元單獨調度，最后將結果整合成為整體問題調度方案；文獻[11]將單元調度問題整體視為一個大規模調度問題，通過建立復雜的數學模型，運用多種數學方法進行求解，得到整個單元調度問題的調度結果；文獻[12]給出了一種基于啟發式規則框架的單元調度問題求解方法，可以根據不同調度性能要求，動態選入啟發式規則，并對調度問題進行求解。在調度問題的求解算法方面，文獻[13]分別給出了兩種遺傳算法進行單元構造和單元調度；文獻[14]使用了模擬退火算法進行了單元布局和動態制造單元調度問題的研究。雖然針對單元調度問題已經有了相當的研究成果，但是，現有的研究仍存在以下問題：

（1）調度算法針對特定問題、特定的調度性能進行設計，算法可變動性較差，一旦調度環境或者調度目標發生改變，調度算法往往無法動態調整；

（2）大多數算法從整體問題出發，調度算法的設計重點偏重于整體調度結果，對制造單元的調度算法和調度結果都沒有過多的關注；

（3）在針對制造單元大規模調度問題中，現有的算法研究仍然不多，并且算法效率和穩定性相對不高。

啟發式規則計算精度不高，無法完全滿足調度性能的要求，而由于制造單元存在耦合，無法直接使用高效的智能搜索算法直接對其求解。因此，為了提高計算效率同時兼顧全局優化目標，本文將智能搜索算法的調度精度與啟發式規則的計算效率相融合，設計了基于“預處理”和“整體調度”的兩階段的制造單元合作協同調度算法。

2 柔性制造單元調度問題背景

本文所研究的制造環境如下：企業擁有多個不同的加工車間，并且擁有一定種類和數量的制造資源（機器），這些制造資源分布在該企業的各個加工車間內，為了滿足不同的生產任務，制造資源可以重新進行物理布局，且制造資源的移動將產生重布局費用。針對給定的加工任務集，待加工產品（工件）有多個種類且每個種類包含一定的加工批量，同時，每種產品的加工路徑都不唯一，也即屬于開放車間環境（Open Shop），在對產品進行加工時，產品可以拆分為多個批次且按不同的加工路線進行[8]。

考慮如上的問題環境，通過有效的單元設計，應能達到以下目標：

（1）通過對加工任務進行拆分與批量設置，并對相應的任務指派最佳加工路徑，以提高加工資源的使用效率；

（2）對分布在不同加工車間內的制造資源進行布局優化，考慮加工任務的路徑、加工數量和單元構建，調整機器布局以實現最小的加工任務運輸費用。

文獻[8]在融合物理制造單元和邏輯制造單元優勢的基礎上，研究了加工車間資源布局可變且存在生產任務多加工路線環境下的柔性制造單元構建問題。在綜合產品的加工成本、加工車間之間的運輸成本、加工車間內的運輸成本、跨單元操作的額外成本、制造資源移動成本等，并且綜合考慮了加工車間內資源限制、單元內資源限制、單元數量限制后，進行了加工產品的路徑選擇、批量設置、生產資源布局和制造單元構建的工作。通過數值實驗對模型進行了分析和驗證，實驗證明柔性制造單元構建模型可以有效地減少總制造成本。

3 基于兩階段的混合調度框架

3.1 基于兩階段混合調度框架設計

針對上述問題，本文提出了基于“預處理”和“整體調度”兩個階段的調度問題求解過程。兩階段求解的思想是：第一階段，將調度問題進行分割，選取調度問題的特征工件集，接著對特征工件集進行“預調度”處理，將“預處理”的排序結果，形成對整體調度問題的一種預測；第二階段，根據“預調度”結果對整體問題進行“整體調度”，進而最終確定各個工件在機器上的加工順序。基于以上設計思想，提出如圖1所示的基于兩階段的混合調度框架，通過兩階段對問題的處理，可以將大規模的問題分解為較小的問題進行處理，既能夠保證一定的調度精度，又可以提高整體的計算效率。

圖1 基于兩階段的混合調度框架圖

兩階段調度的制造單元合作協同調度算法的優勢在于：

（1）在調度過程，通過制造單元的分解，可以對各個制造單元并行調度，將原有的大規模調度問題，分解為制造單元內調度問題；

（2）在預調度階段中，使用智能搜索算法既可以得到較好的調度性能，又可以減小計算規模；

（3）在預調度基礎上進行的啟發式規則調度具有一定的“預測”能力，因此提高了啟發式規則調度的精度，同時兼顧了計算性能。

3.2 調度框架中算法的選取

調度算法的性能將直接影響到調度結果的優劣，在基于兩階段的混合調度框架中，需要在每一個階段內選取各自的調度算法進行問題調度。在以上的求解過程中，本文使用一種“精確”與“近似”計算相結合的計算思路，一方面，對特征工件集進行“精確”計算，使用智能搜索算法對問題求解，既降低了問題搜索空間，又有助于在合理的系統開銷內得到理想的調度結果；另一方面，在“預調度”的指導下，對剩余工件集使用啟發式規則進行“近似”求解，可以用較小的計算空間和時間空間得到精度較高的解。通過“精確”與“近似”計算相結合的設計思路，既利用啟發式規則求解效率高的優點，又通過“預調度”避免了啟發式規則“預測距離”短，無法獲取全局調度信息的劣勢。

（1）“預調度”階段算法選取

在“預調度”階段中，首先需要對特征工件集進行調度排序，因此，性能更優的調度算法將直接得到更好的調度結果，從而為進一步的整體調度打下良好的基礎。在“預調度”階段中，由于特征工件集的規模相對較小，因此，可以選擇成熟的智能搜索算法進行計算，如遺傳算法、模擬退火算法、神經網絡算法等，上述算法在求解小規模調度問題中都被證明取得了較好的調度結果[15]。并且，仿真實驗也證明，選擇調度性能更優的調度算法能夠取得更好的整體調度結果，因此，在預調度階段，調度算法的選擇策略為盡可能選取調度性能更優的智能調度算法。

（2）“整體調度”階段算法選取

整體調度是在“預調度”的基礎上進行的，整體問題的調度性能在很大程度上依賴“預調度”的結果；且在對整體問題調度過程中，需要將“預調度”結果作為調度約束，因此不適合選用智能搜索算法。針對整體調度階段的特點，可以選擇啟發式規則對基于“預調度”的整體問題進行求解。在整體調度階段，以G-T[16]活動調度生成器為調度框架，對特征工件集以外的剩余工序集，按照G-T方法選入競爭工序集；對特征工件集，以一定的規則按預調度結果將工序選入競爭工序集，然后對競爭工序集通過啟發式規則選定優先級高的工序，統一進行排序。

4 基于兩階段調度的制造單元合作協同調度算法

4.1 算法的預處理過程

基于兩階段調度的制造單元合作協同調度算法的預處理過程需要對特征工件集、預調度計算方法進行確定，同時，需要在整體調度階段之前得到預調度結果。

（1）制造單元特征工件集的選定

特征工件集的大小沒有一個固定的標準，需要根據調度問題的特性來動態制定特征工件集的規模。如果選入的特征工件集規模較大，雖然得到的預調度結果可以表示更全面的問題特征，容易得到最優的整體調度方案，但對預調度的計算開銷較大，需要耗費較多的時間和資源；如果選入的特征工件集規模較小，雖然更容易進行預調度計算，但由于較小預調度結果可能無法完整的描述整體調度問題，從而造成整體調度性能不佳。

針對基于制造單元的調度問題，各個制造單元的工件都由單元內工件集合與跨單元工件集合構成，根據制造單元構建的原則，最優的單元構建將盡量避免跨單元工件的出現，也就意味單元內工件集合代表制造單元的工件特征。因此，在確定特征工件集的步驟中，可以將制造單元的單元內工件集作為制造單元的特征工件集。

（2）“預調度”結果處理方法

經過調度計算，得到以特征工件集為子問題的調度方案，即特征工件在各個機器上的加工順序。預調度結果的建立步驟為：首先將選入的特征工件集和對應的機器集合作為一個獨立的調度子問題；其次，選擇高效和穩定的調度算法對子問題進行求解；最后，去掉調度解中的時間信息，保留各個機器上工件的先后加工次序作為預調度結果。

（3）基于預調度結果的工序選入方法

在“整體調度”階段，需要將預調度階段的結果體現在整體調度中，本節介紹在G-T活動調度生成器框架下的基于預調度結果的工序選入方法。在G-T活動調度生成器方法中，需要將所有待調度的工序選入待調度工序集，并根據待調度工序集進行調度，而基于預調度結果的兩階段調度過程中，特征工件集在各個機器上的先后加工次序已經確定，因此需要設計基于預調度結果的工序選入方法，將預調度結果與整體調度結合。首先，令矩陣表示單元Ck的預調度結果，第m行第i列的元素[m，i]表示機器m上第i個操作，其值為相應的工件號，[m，·]表示機器m上的各個工件的先后加工次序。工序選入步驟如下：

步驟4（更新過程）將[m，i]的第m行所有元素依次左移一位，尾部空出位置補0。

步驟5若特征工件集CJ的所有工件都已判斷，則轉入整體調度。

4.2 算法的流程

基于兩階段調度的制造單元合作協同調度算法在制造單元預調度的基礎上，以G-T活動調度器為基本框架，采用制造單元合作協同技術，對問題進行求解。兩階段算法流程如下：

（1）制造單元預調度階段

步驟1根據調度問題環境，選取各單元的單元內工件集為特征工件集CJ。

步驟2針對各個單元的特征工件集CJ，選用智能搜索算法，對以特征工件集為子問題的調度問題求解。

步驟3通過優化計算，得到各個單元特征工件集中各個工件在各個機器上的加工次序，并將此結果保存為各個制造單元的預調度結果。

（2）制造單元合作協同調度階段

步驟1（單元調度）單元Ck已調度集合P=?，令是單元Ck的待調度工序集合。

步驟2（待調度工序選入）對制造單元內的所有工件進行判斷，對沒有工序在中的所有工件按如下工序選入方法操作：

①如果該工件不屬于特征工件集，則直接將該工件未加工的首道工序加入；

②如果該工件屬于特征工件集，按照特征工件集選入方法將工序入。

步驟3（機器選擇）計算當前部分調度集合中的最早完成時間：

其中，ri，j和pi，j分別為工序Oi，j的釋放時間和加工時間，并令mn表示能夠令t()達到最小值的機器，如果存在多個，則任選其一。

步驟4令表示機器mn上所有操作的集合：

步驟8（單元協同）如果工序屬于代理工件，則根據單元協同技術[17]，進行制造單元協同操作。步驟9（更新預調度結果）如果工序屬于特征工件集內的工件Ji，則更新工序所使用機器的預調度結果，將該機器預調度結果的當前待加工首工件Ji刪除，并依次將其他工件前提。

步驟10如果P為完整調度，則停止；否則返回步驟2。

5 仿真計算及分析

通過兩種規模不同的制造環境，使用基于兩階段調度的制造單元合作協同調度算法對問題進行仿真計算。在算法設置中，分別選取了兩種預調度算法和兩種整體調度規則，用來分析不同方法對調度結果的影響。兩種仿真環境實驗結果表明，使用基于兩階段調度的制造單元合作協同調度算法可以得到更優的調度結果。

5.1 仿真環境規模參數設置

這里使用文獻[12]提出單元調度仿真環境設計方法，隨機生成工件的加工時間、加工路線等，并對工件設計相應的跨單元生產過程。首先通過小規模的問題環境1，展示算法的在不同預調度方法下的調度結果，然后通過大規模問題環境2，比較和分析算法的調度性能。兩個仿真環境的參數設置如表1所示。

表1 基于兩階段調度算法的仿真性能比較

5.2 調度算法選取及參數設置

（1）優化目標

以所有工件的“最大完成時間”最小化為目標進行優化。

（2）預調度算法選取及參數設置

預調度結果的優劣將直接決定問題的調度性能，為方便進行算法性能比較，本文選用傳統遺傳算法與一種改進遺傳算法——和聲遺傳混合算法（Harmony Search Genetic Algorithm，HSGA）[17]，通過這兩種算法來分析預調度算法對整體調度結果的影響。

GA算法參數為：種群規模為300個，交叉概率取1，變異概率取0.2，遺傳代數為400代。

HSGA算法參數為：遺傳算法參數為種群規模為300個，交叉概率取1，遺傳代數為400代；和聲搜索算法參數為記憶考慮概率PHM取0.85，曲調調整率Ppitch取0.25，和聲搜索代數為200代。

（3）整體調度規則選取

通過與制造環境2中啟發式規則仿真結果的對比[12]，在優化最大完工時間時，“LPT”規則在3個算例中得到最優解，“IMOD”規則[18]在2個算例中得到最優解。因此，本文分別選取“LPT”規則和“IMOD”規則作為整體調度規則。

5.3 制造環境1的仿真結果分析與評價

5.3.1 仿真環境1的仿真過程

仿真環境1分別使用GA算法和HSGA算法作為預調度方法，“LPT”規則和“IMOD”規則作為整體調度規則，組合成4種算法對此仿真案例計算，并與基于啟發式規則得到的最優結果進行對比分析。

5.3.2 調度過程分析

（1）調度結果整體分析

基于兩階段調度的制造單元合作協同算法仿真實驗結果，如表2所示。將各個算法的調度結果與使用啟發式規則算法得到的各個調度性能的最優值進行比較，在以最小化“最大完工時間”為優化目標時，使用基于兩階段調度的制造單元合作協同算法整體調度性能優于啟發式規則調度算法。4種不同的兩階段調度算法在優化“最大完工時間”目標時，“最大完工時間”平均縮短了21.5，效率平均提高10.3%，其中HSGA+LPT的兩階段算法取得了最優結果，“最大完工時間”縮短了32，效率提高了15.5%。通過表2的調度結果可以看出，采用HSGA預調度算法平均效率提高了12.1%，而采用GA預調度算法平均效率提高了8.7%；采用不同的整體調度規則也會對調度結果產生較大的影響，從算例1中數據可以得出，使用“LPT”規則的調度結果優于“IMOD”規則。

表2 基于兩階段調度算法的仿真性能比較

表2中的拖期工件只包含實際工件的拖期數，C**為啟發式規則得到的最優值；C*為使用預調度算法得到的最優值；百分比為較啟發式規則的改善率；“GA”、“HSGA”為預調度算法，“IMOD”、“LPT”為整體調度規則。

（2）預調度結果對比分析

在使用基于兩階段調度的制造單元合作協同調度算法計算過程中，通過GA和HSGA算法，對每個制造單元中的特征工件集進行計算，得到的預調度結果如表3所示。通過對結果進行比較，兩種算法在機器1、機器4、機器10中的調度次序不同。而不同的調度次序產生了不同的整體調度結果，說明了預調度對整體調度結果的影響。

表3 GA與HSGA算法預調度結果對比

5.4 制造環境2的仿真結果分析與評價

5.4.1 仿真環境2的仿真過程

仿真環境2首先隨機生成了規模為100個工件，100臺機器，10個單元的10個仿真算例，然后分別使用GA算法和HSGA算法作為預調度方法，“LPT”規則和“IMOD”規則作為整體調度規則，組合成4種算法分別對10個仿真案例各自進行10次仿真計算，并對整體調度性能結果和制造單元內性能結果進行比較和分析。

5.4.2 整體調度性能比較及分析

通過使用4種方法對10個算法分別進行10次仿真計算，得到每種算法的最優值、平均值、標準差和最優值相比規則調度最優值的改善率。表4給出了各種方法的結果對比（表中為部分結果），可以得出以下結論：

（1）基于兩階段調度的算法相比啟發式規則得到可以得到更優的解，從數據中可以看出，相比使用啟發式規則的到的最優解，使用兩階段調度的各個算例都有7%左右的性能提升，充分證明了基于兩階段調度的制造單元合作協同算法的有效性。

（2）通過結果可以看出，對使用“LPT”作為整體調度規則時，“HSGA”和“GA”預調度算法在調度性能上平均提升7.6%和5%，而使用“IMOD”作為整體調度規則時，“HSGA”和“GA”預調度算法在調度性能上平均提升6.4%和8.7%，在Benchmark實驗中，“HSGA”算法的調度性能要優于“GA”算法[17]，因此，性能較高的預調度算法將得到更好的整體調度結果。

（3）從表中標準差可以看出，基于兩階段調度的算法計算結果落在相對較小的范圍內，顯示出較強的穩定性。這是由于使用“GA”和“HSGA”算法作為預調度算法時，制造單元的特征工件集相對整體問題規模較小（本文算例中，預調度算法的計算規模為10×8，而整體調度問題規模為100×100），因此調度算法穩定性較高。

（4）從表中數據可以得出，“LPT”與“IMOD”整體調度規則在分別使用兩種預調度算法時，調度性能相差分別為1.4%與1.1%，說明使用不同的整體調度規則對調度結果影響相對較小，而整體調度性能對預調度的結果依賴度較高。

表44 種算法性能比較（部分）

表4中，C*為啟發式規則得到的最優值；百分比為算法最優值較啟發式規則最優值的改善率；“GA”、“HSGA”為預調度算法，“IMOD”、“LPT”為整體調度規則。

圖2展示了在仿真算例1～5中的各個算法的最優值比較。

圖2 算例1～5的調度結果對比

從圖中可以看出，基于兩階段調度的算法得到的調度結果都優于基于啟發式規則的調度結果。

6 結束語

針對大規模調度問題，本文設計了一種基于“預調度”和“整體調度”相結合的兩階段調度算法框架，通過引入“精確”與“近似”兩類算法，既利用啟發式規則求解效率高的優點，又通過“預調度”避免了其“預測距離”短，無法獲取全局調度信息的劣勢，仿真實驗也證明了該算法框架的有效性和穩定性。該算法提出了一種求解大規模單元調度問題的思路，取得了以下的研究成果。

（1）通過制造單元對大規模問題進行分解，將復雜的調度環境分解為規模較小的單元調度問題。針對單元內部調度，設計了特征工件集，并設計了跨單元工件的調度規則，協調單元間調度，從而保證了整體調度。

（2）通過設計兩階段調度框架，避免了智能搜索算法效率不高，而啟發式規則性能不足的問題，相較于使用啟發式規則，通過不同算法組合的兩階段調度算法具有更優的調度性能和算法穩定性。

（3）“預調度”結果對整體調度結果有較大的影響，因此，使用性能更優的預調度算法能大幅提高整體調度性能。

（4）在預調度基礎上進行的啟發式規則調度具有一定的“預測”能力，因此提高了啟發式規則調度的精度，同時兼顧了計算性能。

作為一個開放的調度算法框架，本文已經證明了兩階段調度算法的有效性，但該算法仍具有進一步深入研究的空間：

（1）在今后的研究中可以將調度目標作為調度算法的選擇依據，按照單目標或多目標調度問題選擇不同的調度算法；

（2）可以把性能更優秀的調度算法引入到該算法框架中，并且將該算法框架進行調整修改引入到其他調度模型中。

[1]Naua S，Divakar R.Cellular manufacturing systems design，planning and control[M].London：Chapman&Hall，1996.

[2]Wu Xiaodan，Chu Chaohsien，Wang Yunfeng，et al.A genetic algorithmfor cellular manufacturing design and layout[J]. European Journal of Operational Research，2007，181（1）：156-167.

[3]Li Xiangyong，Baki M F，Aneja Y P.An ant colony optimization metaheuristic for machine—part cell formation problems[J].Computers&Operations Research，2010，37（12）：2071-2081.

[4]Mahadavi I，Paydar M M，Solimanpur M，et al.Genetic algorithm approach for solving a cell formation problem in cellularmanufacturing[J].ExpertSystemswithApplications，2009，36（3）：6598-6604.

[5]Xambre A R，Vilarinho P M.A simulated annealing approach formanufacturingcellformationwithmultipleidentical machines[J].European Journal of Operational Research，2003，151（2）：434-446.

[6]Papaioannou G，Wilson J M.The evolution of cell formation problem methodologies based on recent studies（1997-2008）：review and directions for future research[J].European Journal of Operational Research，2010，206（3）：509-521.

[7]Ahi A，Aryanezhad M B，Ashtiani B，et al.A novel approach to determine cell formation，intracellular machine layout and cell layout in the CMS problem based on TOPSIS method[J]. Computers&Operations Research，2009，36（5）：1478-1496.

[8]牛力.資源布局可變條件下的開放車間柔性制造單元構建技術研究[J].科學技術與工程，2011，11（25）：6054-6059.

[9]金鋒.吳澄.大規模生產調度問題的研究現狀與展望[J].計算機集成制造系統，2006，12（2）：161-168.

[10]Sun D，Batta R.Scheduling larger job shops：a decomposition approach[J].InternationalJournalofProductionResearch，1996，34（7）：2019-2033.

[11]Yang Wenhwa，Liao Chingjong.Group scheduling on two cells with intercell movement[J].Computers&Operations Research，1996，23（10）：997-1006.

[12]牛力，韓小汀.基于啟發式規則的柔性制造單元合作協同調度算法研究[J].科學技術與工程，2012，12（3）：514-520.

[13]Arkat J，Farahani M H，Hosseini L.Integrating cell formation with cellular layout and operations scheduling[J].The International Journal of Advanced Manufacturing Technology，2012，61：637-647.

[14]Kia R，Baboli A，Javadian N，et al.Solving a group layout design model of a dynamic system with alternative process routings，lot splitting and flexible reconfiguration by simulated annealing[J].Computers&Operations Research，2012，39（11）：2642-2658.

[15]Pinedo M.Scheduling：theory，algorithms and systems[M].New York：Springer-Verlag，2008.

[16]Giffler B，Thompson G L.Algorithms for solving production scheduling problems[J].Operations Research，1960，8（4）：487-503.

[17]牛力.柔性制造環境下的生產調度問題研究[D].北京：北京航空航天大學，2010.

[18]Raman N.Minimum tardiness scheduling in flow shops：construction and evaluation of alternative solution approaches[J]. Journal of Operations Management，1995，12（2）：131-151.

NIU Li1，2,HAN Xiaoting3

1.Key Laboratory of Ministry of Education for Data Engineering and Knowledge Engineering,Renmin University of China,Beijing 100872,China
2.School of Information Resource Management,Renmin University of China,Beijing 100872,China
3.School of Economics and Management,Beihang University,Beijing 100191,China

A two-phase scheduling algorithm including pre-scheduling phase and whole-scheduling phase focused on cellular manufacturing problem is proposed.In order to solve the cellular manufacturing scheduling problem,process decomposition and algorithm optimization technology are used to decompose the large-scale scheduling problem.This algorithm can reduce the problem scale efficiently while the scheduling result is of practical significance for manufacturing practice.Precise calculation and approximate solution is combined in the proposed algorithm,which can enhance computing efficiency while achieving global optimization.The effect of the algorithm is validated by numerical experiments.

flexible manufacturing cell;two-phase scheduling;heuristic algorithm;metaheuristic algorithm

針對單元制造問題，提出了一種基于兩階段的調度算法，通過過程分解和算法優化兩方面實現問題求解。調度過程分為“預調度”和“整體調度”兩個階段，對大規模調度進行調度，不僅有效地降低了問題規模，同時制造單元調度結果對實際生產具有現實意義；調度算法采用了“精確”計算和“近似”求解相結合的方式，既提高計算效率又兼顧了全局優化目標。數值實驗結果表明了的這一設計思路的有效性。

柔性制造單元；兩階段調度；啟發式算法；智能搜索算法

A

TH165；TP39

10.3778/j.issn.1002-8331.1207-0442

NIU Li,HAN Xiaoting.Two-phase co-scheduling algorithm solving cellular manufacturing scheduling problem.Computer Engineering and Applications,2013,49（19）：232-237.

國家自然科學基金（No.71071008）。

牛力（1982—），男，博士，講師，研究領域為系統工程，生產調度；韓小汀（1983—），女，碩士，實驗師，研究方向為復雜系統，社會網絡。E-mail：rucniuli@gmail.com

2012-07-30

2012-09-28

1002-8331（2013）19-0232-06