牛力，韓小汀

1.中國人民大學(xué)數(shù)據(jù)工程與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，北京 100872

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

3.北京航空航天大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100191

基于兩階段調(diào)度的制造單元協(xié)同調(diào)度算法研究

牛力1，2，韓小汀3

1.中國人民大學(xué)數(shù)據(jù)工程與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，北京 100872

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

3.北京航空航天大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100191

1 引言

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

調(diào)度問題的NP-難屬性決定了如果大規(guī)模的調(diào)度問題簡單套用小規(guī)模問題的求解方法，計(jì)算時(shí)間和搜索空間產(chǎn)生的組合爆炸將使得求解性能很差[9]，特別是面對多制造單元，且存在跨單元生產(chǎn)的制造環(huán)境下，現(xiàn)有的調(diào)度算法則無法直接進(jìn)行求解。對于單元調(diào)度的求解方法，不同的學(xué)者給出了不同的解決方案。其中，在進(jìn)行大規(guī)模調(diào)度分解方面，文獻(xiàn)[10]按照單元制造的思路對調(diào)度環(huán)境進(jìn)行分解，然后對獨(dú)立的制造單元單獨(dú)調(diào)度，最后將結(jié)果整合成為整體問題調(diào)度方案；文獻(xiàn)[11]將單元調(diào)度問題整體視為一個(gè)大規(guī)模調(diào)度問題，通過建立復(fù)雜的數(shù)學(xué)模型，運(yùn)用多種數(shù)學(xué)方法進(jìn)行求解，得到整個(gè)單元調(diào)度問題的調(diào)度結(jié)果；文獻(xiàn)[12]給出了一種基于啟發(fā)式規(guī)則框架的單元調(diào)度問題求解方法，可以根據(jù)不同調(diào)度性能要求，動(dòng)態(tài)選入啟發(fā)式規(guī)則，并對調(diào)度問題進(jìn)行求解。在調(diào)度問題的求解算法方面，文獻(xiàn)[13]分別給出了兩種遺傳算法進(jìn)行單元構(gòu)造和單元調(diào)度；文獻(xiàn)[14]使用了模擬退火算法進(jìn)行了單元布局和動(dòng)態(tài)制造單元調(diào)度問題的研究。雖然針對單元調(diào)度問題已經(jīng)有了相當(dāng)?shù)难芯砍晒?，現(xiàn)有的研究仍存在以下問題：

（1）調(diào)度算法針對特定問題、特定的調(diào)度性能進(jìn)行設(shè)計(jì)，算法可變動(dòng)性較差，一旦調(diào)度環(huán)境或者調(diào)度目標(biāo)發(fā)生改變，調(diào)度算法往往無法動(dòng)態(tài)調(diào)整；

（2）大多數(shù)算法從整體問題出發(fā)，調(diào)度算法的設(shè)計(jì)重點(diǎn)偏重于整體調(diào)度結(jié)果，對制造單元的調(diào)度算法和調(diào)度結(jié)果都沒有過多的關(guān)注；

（3）在針對制造單元大規(guī)模調(diào)度問題中，現(xiàn)有的算法研究仍然不多，并且算法效率和穩(wěn)定性相對不高。

啟發(fā)式規(guī)則計(jì)算精度不高，無法完全滿足調(diào)度性能的要求，而由于制造單元存在耦合，無法直接使用高效的智能搜索算法直接對其求解。因此，為了提高計(jì)算效率同時(shí)兼顧全局優(yōu)化目標(biāo)，本文將智能搜索算法的調(diào)度精度與啟發(fā)式規(guī)則的計(jì)算效率相融合，設(shè)計(jì)了基于“預(yù)處理”和“整體調(diào)度”的兩階段的制造單元合作協(xié)同調(diào)度算法。

2 柔性制造單元調(diào)度問題背景

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

考慮如上的問題環(huán)境，通過有效的單元設(shè)計(jì)，應(yīng)能達(dá)到以下目標(biāo)：

（1）通過對加工任務(wù)進(jìn)行拆分與批量設(shè)置，并對相應(yīng)的任務(wù)指派最佳加工路徑，以提高加工資源的使用效率；

（2）對分布在不同加工車間內(nèi)的制造資源進(jìn)行布局優(yōu)化，考慮加工任務(wù)的路徑、加工數(shù)量和單元構(gòu)建，調(diào)整機(jī)器布局以實(shí)現(xiàn)最小的加工任務(wù)運(yùn)輸費(fèi)用。

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

3 基于兩階段的混合調(diào)度框架

3.1 基于兩階段混合調(diào)度框架設(shè)計(jì)

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

圖1 基于兩階段的混合調(diào)度框架圖

兩階段調(diào)度的制造單元合作協(xié)同調(diào)度算法的優(yōu)勢在于：

（1）在調(diào)度過程，通過制造單元的分解，可以對各個(gè)制造單元并行調(diào)度，將原有的大規(guī)模調(diào)度問題，分解為制造單元內(nèi)調(diào)度問題；

（2）在預(yù)調(diào)度階段中，使用智能搜索算法既可以得到較好的調(diào)度性能，又可以減小計(jì)算規(guī)模；

（3）在預(yù)調(diào)度基礎(chǔ)上進(jìn)行的啟發(fā)式規(guī)則調(diào)度具有一定的“預(yù)測”能力，因此提高了啟發(fā)式規(guī)則調(diào)度的精度，同時(shí)兼顧了計(jì)算性能。

3.2 調(diào)度框架中算法的選取

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

（1）“預(yù)調(diào)度”階段算法選取

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

（2）“整體調(diào)度”階段算法選取

整體調(diào)度是在“預(yù)調(diào)度”的基礎(chǔ)上進(jìn)行的，整體問題的調(diào)度性能在很大程度上依賴“預(yù)調(diào)度”的結(jié)果；且在對整體問題調(diào)度過程中，需要將“預(yù)調(diào)度”結(jié)果作為調(diào)度約束，因此不適合選用智能搜索算法。針對整體調(diào)度階段的特點(diǎn)，可以選擇啟發(fā)式規(guī)則對基于“預(yù)調(diào)度”的整體問題進(jìn)行求解。在整體調(diào)度階段，以G-T[16]活動(dòng)調(diào)度生成器為調(diào)度框架，對特征工件集以外的剩余工序集，按照G-T方法選入競爭工序集；對特征工件集，以一定的規(guī)則按預(yù)調(diào)度結(jié)果將工序選入競爭工序集，然后對競爭工序集通過啟發(fā)式規(guī)則選定優(yōu)先級(jí)高的工序，統(tǒng)一進(jìn)行排序。

4 基于兩階段調(diào)度的制造單元合作協(xié)同調(diào)度算法

4.1 算法的預(yù)處理過程

基于兩階段調(diào)度的制造單元合作協(xié)同調(diào)度算法的預(yù)處理過程需要對特征工件集、預(yù)調(diào)度計(jì)算方法進(jìn)行確定，同時(shí)，需要在整體調(diào)度階段之前得到預(yù)調(diào)度結(jié)果。

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

特征工件集的大小沒有一個(gè)固定的標(biāo)準(zhǔn)，需要根據(jù)調(diào)度問題的特性來動(dòng)態(tài)制定特征工件集的規(guī)模。如果選入的特征工件集規(guī)模較大，雖然得到的預(yù)調(diào)度結(jié)果可以表示更全面的問題特征，容易得到最優(yōu)的整體調(diào)度方案，但對預(yù)調(diào)度的計(jì)算開銷較大，需要耗費(fèi)較多的時(shí)間和資源；如果選入的特征工件集規(guī)模較小，雖然更容易進(jìn)行預(yù)調(diào)度計(jì)算，但由于較小預(yù)調(diào)度結(jié)果可能無法完整的描述整體調(diào)度問題，從而造成整體調(diào)度性能不佳。

針對基于制造單元的調(diào)度問題，各個(gè)制造單元的工件都由單元內(nèi)工件集合與跨單元工件集合構(gòu)成，根據(jù)制造單元構(gòu)建的原則，最優(yōu)的單元構(gòu)建將盡量避免跨單元工件的出現(xiàn)，也就意味單元內(nèi)工件集合代表制造單元的工件特征。因此，在確定特征工件集的步驟中，可以將制造單元的單元內(nèi)工件集作為制造單元的特征工件集。

（2）“預(yù)調(diào)度”結(jié)果處理方法

經(jīng)過調(diào)度計(jì)算，得到以特征工件集為子問題的調(diào)度方案，即特征工件在各個(gè)機(jī)器上的加工順序。預(yù)調(diào)度結(jié)果的建立步驟為：首先將選入的特征工件集和對應(yīng)的機(jī)器集合作為一個(gè)獨(dú)立的調(diào)度子問題；其次，選擇高效和穩(wěn)定的調(diào)度算法對子問題進(jìn)行求解；最后，去掉調(diào)度解中的時(shí)間信息，保留各個(gè)機(jī)器上工件的先后加工次序作為預(yù)調(diào)度結(jié)果。

（3）基于預(yù)調(diào)度結(jié)果的工序選入方法

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

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

步驟5若特征工件集CJ的所有工件都已判斷，則轉(zhuǎn)入整體調(diào)度。

4.2 算法的流程

基于兩階段調(diào)度的制造單元合作協(xié)同調(diào)度算法在制造單元預(yù)調(diào)度的基礎(chǔ)上，以G-T活動(dòng)調(diào)度器為基本框架，采用制造單元合作協(xié)同技術(shù)，對問題進(jìn)行求解。兩階段算法流程如下：

（1）制造單元預(yù)調(diào)度階段

步驟1根據(jù)調(diào)度問題環(huán)境，選取各單元的單元內(nèi)工件集為特征工件集CJ。

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

步驟3通過優(yōu)化計(jì)算，得到各個(gè)單元特征工件集中各個(gè)工件在各個(gè)機(jī)器上的加工次序，并將此結(jié)果保存為各個(gè)制造單元的預(yù)調(diào)度結(jié)果。

（2）制造單元合作協(xié)同調(diào)度階段

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

步驟2（待調(diào)度工序選入）對制造單元內(nèi)的所有工件進(jìn)行判斷，對沒有工序在中的所有工件按如下工序選入方法操作：

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

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

步驟3（機(jī)器選擇）計(jì)算當(dāng)前部分調(diào)度集合中的最早完成時(shí)間：

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

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

步驟8（單元協(xié)同）如果工序?qū)儆诖砉ぜ?，則根據(jù)單元協(xié)同技術(shù)[17]，進(jìn)行制造單元協(xié)同操作。步驟9（更新預(yù)調(diào)度結(jié)果）如果工序?qū)儆谔卣鞴ぜ瘍?nèi)的工件Ji，則更新工序所使用機(jī)器的預(yù)調(diào)度結(jié)果，將該機(jī)器預(yù)調(diào)度結(jié)果的當(dāng)前待加工首工件Ji刪除，并依次將其他工件前提。

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

5 仿真計(jì)算及分析

通過兩種規(guī)模不同的制造環(huán)境，使用基于兩階段調(diào)度的制造單元合作協(xié)同調(diào)度算法對問題進(jìn)行仿真計(jì)算。在算法設(shè)置中，分別選取了兩種預(yù)調(diào)度算法和兩種整體調(diào)度規(guī)則，用來分析不同方法對調(diào)度結(jié)果的影響。兩種仿真環(huán)境實(shí)驗(yàn)結(jié)果表明，使用基于兩階段調(diào)度的制造單元合作協(xié)同調(diào)度算法可以得到更優(yōu)的調(diào)度結(jié)果。

5.1 仿真環(huán)境規(guī)模參數(shù)設(shè)置

這里使用文獻(xiàn)[12]提出單元調(diào)度仿真環(huán)境設(shè)計(jì)方法，隨機(jī)生成工件的加工時(shí)間、加工路線等，并對工件設(shè)計(jì)相應(yīng)的跨單元生產(chǎn)過程。首先通過小規(guī)模的問題環(huán)境1，展示算法的在不同預(yù)調(diào)度方法下的調(diào)度結(jié)果，然后通過大規(guī)模問題環(huán)境2，比較和分析算法的調(diào)度性能。兩個(gè)仿真環(huán)境的參數(shù)設(shè)置如表1所示。

表1 基于兩階段調(diào)度算法的仿真性能比較

5.2 調(diào)度算法選取及參數(shù)設(shè)置

（1）優(yōu)化目標(biāo)

以所有工件的“最大完成時(shí)間”最小化為目標(biāo)進(jìn)行優(yōu)化。

（2）預(yù)調(diào)度算法選取及參數(shù)設(shè)置

預(yù)調(diào)度結(jié)果的優(yōu)劣將直接決定問題的調(diào)度性能，為方便進(jìn)行算法性能比較，本文選用傳統(tǒng)遺傳算法與一種改進(jìn)遺傳算法——和聲遺傳混合算法（Harmony Search Genetic Algorithm，HSGA）[17]，通過這兩種算法來分析預(yù)調(diào)度算法對整體調(diào)度結(jié)果的影響。

GA算法參數(shù)為：種群規(guī)模為300個(gè)，交叉概率取1，變異概率取0.2，遺傳代數(shù)為400代。

HSGA算法參數(shù)為：遺傳算法參數(shù)為種群規(guī)模為300個(gè)，交叉概率取1，遺傳代數(shù)為400代；和聲搜索算法參數(shù)為記憶考慮概率PHM取0.85，曲調(diào)調(diào)整率Ppitch取0.25，和聲搜索代數(shù)為200代。

（3）整體調(diào)度規(guī)則選取

通過與制造環(huán)境2中啟發(fā)式規(guī)則仿真結(jié)果的對比[12]，在優(yōu)化最大完工時(shí)間時(shí)，“LPT”規(guī)則在3個(gè)算例中得到最優(yōu)解，“IMOD”規(guī)則[18]在2個(gè)算例中得到最優(yōu)解。因此，本文分別選取“LPT”規(guī)則和“IMOD”規(guī)則作為整體調(diào)度規(guī)則。

5.3 制造環(huán)境1的仿真結(jié)果分析與評(píng)價(jià)

5.3.1 仿真環(huán)境1的仿真過程

仿真環(huán)境1分別使用GA算法和HSGA算法作為預(yù)調(diào)度方法，“LPT”規(guī)則和“IMOD”規(guī)則作為整體調(diào)度規(guī)則，組合成4種算法對此仿真案例計(jì)算，并與基于啟發(fā)式規(guī)則得到的最優(yōu)結(jié)果進(jìn)行對比分析。

5.3.2 調(diào)度過程分析

（1）調(diào)度結(jié)果整體分析

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

表2 基于兩階段調(diào)度算法的仿真性能比較

表2中的拖期工件只包含實(shí)際工件的拖期數(shù)，C**為啟發(fā)式規(guī)則得到的最優(yōu)值；C*為使用預(yù)調(diào)度算法得到的最優(yōu)值；百分比為較啟發(fā)式規(guī)則的改善率；“GA”、“HSGA”為預(yù)調(diào)度算法，“IMOD”、“LPT”為整體調(diào)度規(guī)則。

（2）預(yù)調(diào)度結(jié)果對比分析

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

表3 GA與HSGA算法預(yù)調(diào)度結(jié)果對比

5.4 制造環(huán)境2的仿真結(jié)果分析與評(píng)價(jià)

5.4.1 仿真環(huán)境2的仿真過程

仿真環(huán)境2首先隨機(jī)生成了規(guī)模為100個(gè)工件，100臺(tái)機(jī)器，10個(gè)單元的10個(gè)仿真算例，然后分別使用GA算法和HSGA算法作為預(yù)調(diào)度方法，“LPT”規(guī)則和“IMOD”規(guī)則作為整體調(diào)度規(guī)則，組合成4種算法分別對10個(gè)仿真案例各自進(jìn)行10次仿真計(jì)算，并對整體調(diào)度性能結(jié)果和制造單元內(nèi)性能結(jié)果進(jìn)行比較和分析。

5.4.2 整體調(diào)度性能比較及分析

通過使用4種方法對10個(gè)算法分別進(jìn)行10次仿真計(jì)算，得到每種算法的最優(yōu)值、平均值、標(biāo)準(zhǔn)差和最優(yōu)值相比規(guī)則調(diào)度最優(yōu)值的改善率。表4給出了各種方法的結(jié)果對比（表中為部分結(jié)果），可以得出以下結(jié)論：

（1）基于兩階段調(diào)度的算法相比啟發(fā)式規(guī)則得到可以得到更優(yōu)的解，從數(shù)據(jù)中可以看出，相比使用啟發(fā)式規(guī)則的到的最優(yōu)解，使用兩階段調(diào)度的各個(gè)算例都有7%左右的性能提升，充分證明了基于兩階段調(diào)度的制造單元合作協(xié)同算法的有效性。

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

（3）從表中標(biāo)準(zhǔn)差可以看出，基于兩階段調(diào)度的算法計(jì)算結(jié)果落在相對較小的范圍內(nèi)，顯示出較強(qiáng)的穩(wěn)定性。這是由于使用“GA”和“HSGA”算法作為預(yù)調(diào)度算法時(shí)，制造單元的特征工件集相對整體問題規(guī)模較?。ū疚乃憷?，預(yù)調(diào)度算法的計(jì)算規(guī)模為10×8，而整體調(diào)度問題規(guī)模為100×100），因此調(diào)度算法穩(wěn)定性較高。

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

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

表4中，C*為啟發(fā)式規(guī)則得到的最優(yōu)值；百分比為算法最優(yōu)值較啟發(fā)式規(guī)則最優(yōu)值的改善率；“GA”、“HSGA”為預(yù)調(diào)度算法，“IMOD”、“LPT”為整體調(diào)度規(guī)則。

圖2展示了在仿真算例1～5中的各個(gè)算法的最優(yōu)值比較。

圖2 算例1～5的調(diào)度結(jié)果對比

從圖中可以看出，基于兩階段調(diào)度的算法得到的調(diào)度結(jié)果都優(yōu)于基于啟發(fā)式規(guī)則的調(diào)度結(jié)果。

6 結(jié)束語

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

（1）通過制造單元對大規(guī)模問題進(jìn)行分解，將復(fù)雜的調(diào)度環(huán)境分解為規(guī)模較小的單元調(diào)度問題。針對單元內(nèi)部調(diào)度，設(shè)計(jì)了特征工件集，并設(shè)計(jì)了跨單元工件的調(diào)度規(guī)則，協(xié)調(diào)單元間調(diào)度，從而保證了整體調(diào)度。

（2）通過設(shè)計(jì)兩階段調(diào)度框架，避免了智能搜索算法效率不高，而啟發(fā)式規(guī)則性能不足的問題，相較于使用啟發(fā)式規(guī)則，通過不同算法組合的兩階段調(diào)度算法具有更優(yōu)的調(diào)度性能和算法穩(wěn)定性。

（3）“預(yù)調(diào)度”結(jié)果對整體調(diào)度結(jié)果有較大的影響，因此，使用性能更優(yōu)的預(yù)調(diào)度算法能大幅提高整體調(diào)度性能。

（4）在預(yù)調(diào)度基礎(chǔ)上進(jìn)行的啟發(fā)式規(guī)則調(diào)度具有一定的“預(yù)測”能力，因此提高了啟發(fā)式規(guī)則調(diào)度的精度，同時(shí)兼顧了計(jì)算性能。

作為一個(gè)開放的調(diào)度算法框架，本文已經(jīng)證明了兩階段調(diào)度算法的有效性，但該算法仍具有進(jìn)一步深入研究的空間：

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

（2）可以把性能更優(yōu)秀的調(diào)度算法引入到該算法框架中，并且將該算法框架進(jìn)行調(diào)整修改引入到其他調(diào)度模型中。

[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]牛力.資源布局可變條件下的開放車間柔性制造單元構(gòu)建技術(shù)研究[J].科學(xué)技術(shù)與工程，2011，11（25）：6054-6059.

[9]金鋒.吳澄.大規(guī)模生產(chǎn)調(diào)度問題的研究現(xiàn)狀與展望[J].計(jì)算機(jī)集成制造系統(tǒng)，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]牛力，韓小汀.基于啟發(fā)式規(guī)則的柔性制造單元合作協(xié)同調(diào)度算法研究[J].科學(xué)技術(shù)與工程，2012，12（3）：514-520.

[13]Arkat J，F(xiàn)arahani 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]牛力.柔性制造環(huán)境下的生產(chǎn)調(diào)度問題研究[D].北京：北京航空航天大學(xué)，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

針對單元制造問題，提出了一種基于兩階段的調(diào)度算法，通過過程分解和算法優(yōu)化兩方面實(shí)現(xiàn)問題求解。調(diào)度過程分為“預(yù)調(diào)度”和“整體調(diào)度”兩個(gè)階段，對大規(guī)模調(diào)度進(jìn)行調(diào)度，不僅有效地降低了問題規(guī)模，同時(shí)制造單元調(diào)度結(jié)果對實(shí)際生產(chǎn)具有現(xiàn)實(shí)意義；調(diào)度算法采用了“精確”計(jì)算和“近似”求解相結(jié)合的方式，既提高計(jì)算效率又兼顧了全局優(yōu)化目標(biāo)。數(shù)值實(shí)驗(yàn)結(jié)果表明了的這一設(shè)計(jì)思路的有效性。

柔性制造單元；兩階段調(diào)度；啟發(fā)式算法；智能搜索算法

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.

國家自然科學(xué)基金（No.71071008）。

牛力（1982—），男，博士，講師，研究領(lǐng)域?yàn)橄到y(tǒng)工程，生產(chǎn)調(diào)度；韓小?。?983—），女，碩士，實(shí)驗(yàn)師，研究方向?yàn)閺?fù)雜系統(tǒng)，社會(huì)網(wǎng)絡(luò)。E-mail：rucniuli@gmail.com

2012-07-30

2012-09-28

1002-8331（2013）19-0232-06