楊宏安 孫啟峰 郭 杰

西北工業(yè)大學(xué)，西安，710072

0 引言

作業(yè)車(chē)間調(diào)度問(wèn)題（job shop scheduling pr oblems，JSSP）實(shí)質(zhì)是調(diào)度優(yōu)化問(wèn)題，而調(diào)度優(yōu)化問(wèn)題又屬于一類(lèi)典型的約束優(yōu)化問(wèn)題。近年來(lái)，近似調(diào)度方法（如遺傳算法、禁忌搜索、模擬退火和免疫算法等）是國(guó)內(nèi)JSSP研究領(lǐng)域的主流方法，其調(diào)度模型基本上都可以視為在滿(mǎn)足工藝路線、機(jī)床能力和交貨期等約束條件下的單／多目標(biāo)優(yōu)化問(wèn)題，而求解方法均屬于啟發(fā)式搜索。由于JSSP屬于典型的NP困難問(wèn)題，且實(shí)際生產(chǎn)車(chē)間具有大規(guī)模、多任務(wù)、多資源、多約束和動(dòng)態(tài)隨機(jī)性等特點(diǎn)，近似調(diào)度方法真正應(yīng)用于指導(dǎo)企業(yè)生產(chǎn)實(shí)踐的成功案例較少。

約束優(yōu)化問(wèn)題（constrained opti mization problems，COP）是在約束滿(mǎn)足問(wèn)題（constraint satisfaction proble ms，CSP）基礎(chǔ)上發(fā)展而來(lái)的。CSP方法以滿(mǎn)足實(shí)際問(wèn)題的所有約束條件為出發(fā)點(diǎn)，在其模型中不包含目標(biāo)函數(shù)；而COP和CSP的本質(zhì)區(qū)別是在模型中引入了目標(biāo)函數(shù)，從而使之更貼近調(diào)度優(yōu)化問(wèn)題，同時(shí)也使得該類(lèi)問(wèn)題的求解復(fù)雜度顯著提高。作為人工智能中相當(dāng)活躍的研究領(lǐng)域，CSP／COP能很好地描述智能領(lǐng)域的組合、調(diào)度和規(guī)劃等復(fù)雜問(wèn)題，尤其適合于描述和求解大規(guī)模的組合優(yōu)化問(wèn)題。

確定型JSSP和COP都是在事先已知變量和約束的前提下，尋求變量的合理取值，并在滿(mǎn)足所有約束的前提下優(yōu)化特定的目標(biāo)函數(shù)，因此，作業(yè)車(chē)間調(diào)度問(wèn)題和約束優(yōu)化問(wèn)題的相似性和吻合度較高。Fox［1］首次將CSP方法引入車(chē)間調(diào)度問(wèn)題研究之中，并在此基礎(chǔ)上開(kāi)發(fā)出基于啟發(fā)搜索技術(shù)的ISIS調(diào)度系統(tǒng)［2］。Smith等［3］于20世紀(jì)90年代初開(kāi)發(fā)完成基于Macro－Opport unistic的OPIS調(diào)度系統(tǒng)。Sadeh在變量／值排序啟發(fā)算法［4］和 回 溯 處 理［5］等 方 面 進(jìn) 行 了 深 入 研 究。Barták等［6］近年來(lái)在基于約束規(guī)劃的計(jì)劃和調(diào)度方面開(kāi)展了大量研究工作。

國(guó)內(nèi)將CSP方法應(yīng)用于求解JSSP的相關(guān)文獻(xiàn)較少。文獻(xiàn)［7－9］對(duì)基于約束滿(mǎn)足的車(chē)間調(diào)度進(jìn)行了綜述。文獻(xiàn)［10］針對(duì)Job Shop調(diào)度問(wèn)題，采用形式化的約束一致性實(shí)施、操作選擇策略、開(kāi)始時(shí)間選擇策略和不完全回跳策略來(lái)提高約束滿(mǎn)足調(diào)度算法的求解效率。文獻(xiàn)［11］針對(duì)作業(yè)車(chē)間排序重調(diào)度問(wèn)題，提出了一種可分布求解的分級(jí)模型，并對(duì)分級(jí)模型采用改進(jìn)的修復(fù)約束滿(mǎn)足算法進(jìn)行求解。

目前，國(guó)內(nèi)已開(kāi)始將CSP方法引入到JSSP的研究中，但CSP方法僅以求得調(diào)度問(wèn)題的滿(mǎn)意解為出發(fā)點(diǎn)，而沒(méi)有涉及調(diào)度目標(biāo)函數(shù)的優(yōu)化問(wèn)題。本文以CSP方法為基礎(chǔ)，將提前／拖期優(yōu)化指標(biāo)引入CSP中，使約束滿(mǎn)足問(wèn)題升級(jí)為約束優(yōu)化問(wèn)題；基于COP和JSSP的吻合度考慮，將作業(yè)車(chē)間調(diào)度問(wèn)題轉(zhuǎn)化為約束優(yōu)化問(wèn)題，綜合運(yùn)用COP的四元組建模方法和回溯搜索方法對(duì)JSSP進(jìn)行模型描述和算法求解，旨在構(gòu)建從模型描述、調(diào)度策略設(shè)計(jì)、調(diào)度算法設(shè)計(jì)和仿真試驗(yàn)在內(nèi)的約束優(yōu)化技術(shù)求解JSSP的完整研究框架，并為后續(xù)進(jìn)一步深入研究約束優(yōu)化調(diào)度引擎搭建基礎(chǔ)性支撐平臺(tái)。

1 約束優(yōu)化問(wèn)題

定義1 約束優(yōu)化問(wèn)題由一個(gè)變量集、變量值域、約束集和目標(biāo)函數(shù)組成，可視為一個(gè)四元組P ＝ （V，D，C，O）。其中，V 為變量集，V ＝ ｛V1，V2，…，Vn｝；D為各變量的候選值域集，D ＝ ｛D1，D2，…，Dn｝，C 為變量之間的約束集，C ＝ ｛c1，c2，…，cm｝，O 為目標(biāo)函數(shù)。

定義2 約束優(yōu)化問(wèn)題的解是在滿(mǎn)足全部約束集C的條件下，在變量集V內(nèi)尋求一組變量賦值｛a1，a2，…，an｝并使得目標(biāo)函數(shù)O取得最優(yōu)，其中ai∈Di。

2 約束優(yōu)化調(diào)度模型

2．1 相關(guān)變量說(shuō)明

對(duì)于調(diào)度任務(wù)池內(nèi)的任意零件Ji，假設(shè)Ji的任一加工工序?yàn)镺li，其中，i＝1，2，…，n；l＝1，2，…，m；n為零件數(shù)量，m為零件Ji內(nèi)的工序數(shù)量。表1、表2分別為零件Ji和工序Oli的相關(guān)加工參數(shù)定義。

表1 零件J i相關(guān)參數(shù)定義

表2 工序Oli相關(guān)參數(shù)定義

2．2 約束優(yōu)化調(diào)度模型

根據(jù)定義1，采用COP的四元組分析方法來(lái)構(gòu)建約束優(yōu)化調(diào)度模型。

2．2．1 變量集

作業(yè)車(chē)間調(diào)度的根本任務(wù)是確定各零件加工工序在機(jī)床上的開(kāi)工時(shí)間，因此，變量集的構(gòu)造直接以調(diào)度任務(wù)池內(nèi)各零件的加工工序作為獨(dú)立決策節(jié)點(diǎn)，變量定義為任意零件Ji的任一工序Oli的開(kāi)工時(shí)間stli。

2．2．2 約束集

對(duì)于離散加工型車(chē)間而言，一個(gè)可行調(diào)度方案的先決條件是滿(mǎn)足工藝路線和機(jī)床能力兩類(lèi)硬約束，另外，零部件交貨期約束也是保證整機(jī)配套和成品交付的必備條件。

（1）工藝路線約束。該約束描述了同一零件內(nèi)不同工序之間的時(shí)序關(guān)系。假設(shè)在零件Ji內(nèi)，Oli是工序Oji的下游工序，則工藝路線約束為stji＋duji≤stli。

（2）機(jī)床獨(dú)占性約束。該約束描述了承制機(jī)床上加工工序隊(duì)列的時(shí)序關(guān)系。假設(shè)工序Oli和Okj由同一機(jī)床加工，則二者之間的機(jī)床獨(dú)占性約束為（stli＋duli≤stkj）∨ （stjk＋dujk≤stli）。

（3）時(shí)間約束。該約束描述了某一零件的釋放期（或投料期）和交貨期約束。對(duì)于零件Ji，其首道工序O1i和末道工序Omi的開(kāi)工時(shí)間應(yīng)滿(mǎn)足Ji的可接受最早釋放期和可接受最晚完工時(shí)間約束：（st1i≥er di）∧ （stmi＋dumi≤lcdi）。

2．2．3 目標(biāo)函數(shù)

（1）提前／拖期調(diào)度成本。針對(duì)調(diào)度任務(wù)池內(nèi)的任一零件Ji，存在以下拖期、庫(kù)存調(diào)度成本：①拖期成本，零件Ji的拖期成本Tar di＝tar di×max（0，Ci－ddi），其中，tar di為Ji的拖期懲罰系數(shù)。②庫(kù)存成本包括零件的在制品流動(dòng)成本和成品庫(kù)存成本兩部份。其中，在制品流動(dòng)成本定義為零件從投料開(kāi)始至實(shí)際加工結(jié)束之間的現(xiàn)場(chǎng)在制品積壓成本。零件Ji的庫(kù)存總成本Invi＝ddi－Ci），其中，invli為工序Oli的在制品庫(kù)存成本系數(shù)。

（2）調(diào)度目標(biāo)。在計(jì)算出任意零件Ji的拖期和提前成本后，整個(gè)調(diào)度任務(wù)集的調(diào)度總成本ScheduleCost調(diào)度目標(biāo)則是在滿(mǎn)足上述所有約束集的前提下，在各工序開(kāi)工時(shí)間值域內(nèi)尋求一組合理取值，使得調(diào)度總成本ScheduleCost最小。

2．3 基于約束傳播的變量值域初始化方法

上述約束優(yōu)化調(diào)度模型業(yè)已構(gòu)造完成COP四元組中的變量集、約束集和目標(biāo)函數(shù)，而變量值域即為各工序開(kāi)工時(shí)間的候選取值時(shí)間窗口。初始搜索狀態(tài)下的工序開(kāi)工時(shí)間值域依據(jù)約束傳播方法產(chǎn)生。

約束傳播方法：各工序最早開(kāi)工時(shí)間根據(jù)零件的最早可接受釋放期沿工藝路線向下游工序依次順序傳播，而工序最晚開(kāi)工時(shí)間則依據(jù)零件的最晚可接受完工時(shí)間沿工藝路線向上游工序依次倒序傳播，從而即可確定各工序的開(kāi)工時(shí)間窗口。以工序Oli為例，其初始搜索狀態(tài)下的開(kāi)工時(shí)間值域計(jì)算如下：

式中，estli＋1為Oli的下道工序的最早開(kāi)工時(shí)間；lstil－1為Oli的上道工序的最晚開(kāi)工時(shí)間。

3 約束優(yōu)化調(diào)度策略設(shè)計(jì)

3．1 兩階段調(diào)度策略

JSSP屬于典型的NP困難問(wèn)題，傳統(tǒng)調(diào)度優(yōu)化方法很難滿(mǎn)足大規(guī)模調(diào)度對(duì)模型描述和計(jì)算效率的更高需求。因此，為降低大規(guī)模JSSP的求解復(fù)雜度和提高調(diào)度算法的實(shí)用性，遵循解決實(shí)際工程問(wèn)題的思維模式和原則，將求解大規(guī)模JSSP劃分為“瓶頸機(jī)床識(shí)別”和“單機(jī)排序優(yōu)化”兩個(gè)階段，即在各搜索空間內(nèi)，首先計(jì)算和識(shí)別出當(dāng)前狀態(tài)下的瓶頸機(jī)床，然后以該瓶頸機(jī)床為載體，對(duì)競(jìng)爭(zhēng)該機(jī)床的多個(gè)工序采用單機(jī)排序優(yōu)化方法進(jìn)行處理。這種貼近生產(chǎn)實(shí)際的處理策略可以有效降低多機(jī)排序優(yōu)化的復(fù)雜度，從而使得求解大規(guī)模JSSP的困難度顯著較低。

3．2 動(dòng)態(tài)修訂搜索空間策略

因工藝路線和機(jī)床獨(dú)占性?xún)深?lèi)硬約束的存在，已調(diào)度工序的賦值結(jié)果勢(shì)必影響剩余搜索空間內(nèi)相關(guān)工序的開(kāi)工時(shí)間值域，進(jìn)而對(duì)下一搜索空間內(nèi)的瓶頸機(jī)床識(shí)別、變量排序和值排序等環(huán)節(jié)產(chǎn)生連鎖影響。因此，引入動(dòng)態(tài)修訂搜索空間的調(diào)度策略，根據(jù)已調(diào)度中間結(jié)果和約束集，調(diào)整和過(guò)濾剩余搜索空間各工序開(kāi)工時(shí)間的值域，及時(shí)修訂搜索空間的概率計(jì)算，以保證啟發(fā)規(guī)則始終指向于當(dāng)前搜索狀態(tài)下的瓶頸機(jī)床，從而為第二階段的單機(jī)排序優(yōu)化提供計(jì)算依據(jù)。

4 “Thrashing”現(xiàn)象消減機(jī)制

“Thrashing”現(xiàn)象是指在回溯算法搜索過(guò)程中頻繁發(fā)生約束沖突的現(xiàn)象?！癟hrashing”現(xiàn)象的存在嚴(yán)重制約回溯搜索的求解效率，并有可能導(dǎo)致回溯搜索進(jìn)程陷入死循環(huán)。文獻(xiàn)［12］通過(guò)大量調(diào)度實(shí)例發(fā)現(xiàn)：采用CSP方法求解調(diào)度問(wèn)題時(shí)，絕大多數(shù)問(wèn)題屬于兩類(lèi)情況：一類(lèi)是無(wú)回溯求解調(diào)度問(wèn)題，另一類(lèi)則是搜索進(jìn)程頻繁出現(xiàn)“Thrashing”現(xiàn)象。

大規(guī)模JSSP具有約束松馳度緊、約束內(nèi)聯(lián)度高等特征，回溯發(fā)生不可避免。因此，關(guān)注“Thrashing”、減小“Thrashing”發(fā)生概率是設(shè)計(jì)回溯搜索算法時(shí)不可回避的重要環(huán)節(jié)。在約束優(yōu)化調(diào)度算法設(shè)計(jì)時(shí)，可采用一致性預(yù)處理機(jī)制和回溯前移機(jī)制來(lái)減少“Thrashing”頻發(fā)。

（1）一致性預(yù)處理機(jī)制。隨著調(diào)度進(jìn)程的推進(jìn)，由于已調(diào)度工序開(kāi)工時(shí)間的確定，受約束優(yōu)化調(diào)度模型中兩類(lèi)硬約束的影響，剩余調(diào)度空間中與已調(diào)度工序相關(guān)的變量值域勢(shì)必包含潛在沖突值，而這些潛在沖突值的存在可能導(dǎo)致后續(xù)搜索過(guò)程發(fā)生約束沖突。因此，通過(guò)采用一致性預(yù)處理機(jī)制，依據(jù)已調(diào)度中間結(jié)果對(duì)剩余搜索空間相關(guān)變量集的值域預(yù)先實(shí)施修剪和過(guò)濾，以剔除其值域內(nèi)的潛在沖突值，從而減少剩余變量值域發(fā)生約束沖突的概率。

（2）回溯前移機(jī)制。約束集在回溯搜索過(guò)程中存在“前緊后松”的特點(diǎn)，即在搜索初期，工序變量之間的約束松弛度較緊，而隨著調(diào)度進(jìn)程的推進(jìn)，在前期滿(mǎn)足瓶頸機(jī)床和關(guān)鍵工序變量賦值后，后期的搜索過(guò)程則呈現(xiàn)約束相對(duì)較松的特點(diǎn)。因此，采用回溯前移機(jī)制，將搜索進(jìn)程發(fā)生約束沖突的時(shí)間點(diǎn)前移，及早暴露、識(shí)別并滿(mǎn)足制約整個(gè)搜索過(guò)程中的瓶頸機(jī)床和關(guān)鍵工序賦值，以避免搜索后期出現(xiàn)約束沖突而導(dǎo)致已調(diào)度中間結(jié)果發(fā)生大面積回溯。

5 約束優(yōu)化調(diào)度算法設(shè)計(jì)

遵循上述的兩階段調(diào)度和動(dòng)態(tài)修訂搜索空間的調(diào)度策略，結(jié)合“Thrashing”現(xiàn)象消減機(jī)制，在深度優(yōu)先搜索算法的基礎(chǔ)上，設(shè)計(jì)了圖1所示的約束優(yōu)化調(diào)度算法（constrained opti mization schedule al gorit h m，COSA）框架。其中，Un Sched為待調(diào)度工序集；Sched為已調(diào)度結(jié)果集；Op為各搜索狀態(tài)下的變量排序啟發(fā)結(jié)果（即關(guān)鍵工序）；St為Op的開(kāi)工時(shí)間賦值。該算法的步驟如下：

（1）初始化。系統(tǒng)啟動(dòng)后，首先初始化待調(diào)度工序集Un Sched和已調(diào)度結(jié)果集Sched，并設(shè)置時(shí)間粒度、回溯閾值等系統(tǒng)參數(shù)。

（2）初始化工序開(kāi)工時(shí)間窗。依據(jù)前述約束傳播方法產(chǎn)生初始搜索狀態(tài)下各工序開(kāi)工時(shí)間的值域。

（3）搜索結(jié)束判定。檢測(cè)Un Sched內(nèi)有無(wú)剩余待調(diào)度工序，如果UnSched＝?，則整個(gè)搜索進(jìn)程結(jié)束，算法最終求得調(diào)度解或證明調(diào)度問(wèn)題無(wú)解，否則，則進(jìn)入下一步。

（4）一致性預(yù)處理。遵循一致性預(yù)處理機(jī)制，采用文獻(xiàn)［13］提出的動(dòng)態(tài)一致性增強(qiáng)算法，依據(jù)上次搜索狀態(tài)下的關(guān)鍵工序賦值（Op，St），結(jié)合工序路線和機(jī)床獨(dú)占性2類(lèi)硬約束對(duì)剩余搜索空間實(shí)施預(yù)修剪。

（5）約束沖突檢測(cè)。檢驗(yàn)上次搜索狀態(tài)下的關(guān)鍵工序賦值（Op，St）與Sched內(nèi)已調(diào)度中間結(jié)果有無(wú)約束沖突，若發(fā)生沖突，則進(jìn)行順序回溯處理［5］，若無(wú)沖突，則進(jìn)入下一步。

（6）瓶頸機(jī)床識(shí)別。根據(jù)回溯前移機(jī)制，采用文獻(xiàn)［14］提出的瓶頸機(jī)床動(dòng)態(tài)識(shí)別方法：首先依據(jù)上述約束優(yōu)化調(diào)度模型對(duì)剩余搜索空間的工序開(kāi)工時(shí)間集進(jìn)行提前／拖期成本計(jì)算，再進(jìn)行當(dāng)前搜索空間的概率計(jì)算，即依次計(jì)算各工序開(kāi)工時(shí)間的主觀概率、工序?qū)C(jī)床的獨(dú)立需求概率、機(jī)床累計(jì)需求概率之和，最后以累計(jì)需求概率之和最大的機(jī)床作為當(dāng)前搜索狀態(tài)下的瓶頸機(jī)床。

（7）單機(jī)排序優(yōu)化。以步驟（6）的輸出結(jié)果瓶頸機(jī)床作為輸入?yún)?shù)，采用文獻(xiàn)［14］提出的工序變量排序和賦值優(yōu)化方法，輸出當(dāng)前搜索狀態(tài)下的關(guān)鍵工序開(kāi)工時(shí)間取值。① 工序變量?jī)?yōu)化排序：以競(jìng)爭(zhēng)同一瓶頸機(jī)床的所有待調(diào)度工序作為排序?qū)ο?，以工序?qū)C(jī)床的獨(dú)立需求概率值作為排序準(zhǔn)則，在競(jìng)爭(zhēng)高峰時(shí)段選擇獨(dú)立需求概率值最大的工序作為當(dāng)前搜索狀態(tài)下的變量排序輸出結(jié)果Op。②關(guān)鍵工序賦值優(yōu)化：以工序變量?jī)?yōu)化排序輸出結(jié)果Op為輸入，在Op剩余值域內(nèi)選擇調(diào)度成本最小的開(kāi)工時(shí)間作為關(guān)鍵工序Op的最終賦值St。

（8）將關(guān)鍵工序賦值結(jié)果（Op，St）保存進(jìn)Sched，同時(shí)從Un Sched中剔除工序Op，算法進(jìn)入步驟（3），繼續(xù)以上循環(huán)處理。

圖1 約束優(yōu)化調(diào)度算法

6 仿真試驗(yàn)

6．1 調(diào)度用例設(shè)計(jì)

隨機(jī)生成80個(gè)調(diào)度問(wèn)題，通過(guò)調(diào)整拖期系數(shù)τ、交貨期分布R和瓶頸機(jī)床數(shù)量Nbtnk三個(gè)參數(shù)的不同組合產(chǎn)生8組調(diào)度問(wèn)題（表3），每組調(diào)度問(wèn)題包括10個(gè)調(diào)度子問(wèn)題，每個(gè)調(diào)度子問(wèn)題包含20個(gè)零件和5臺(tái)機(jī)床，各零件均包含5道工序，且根據(jù)線性工藝路線依次經(jīng)過(guò)5臺(tái)機(jī)床，各工件經(jīng)過(guò)機(jī)床的順序隨機(jī)產(chǎn)生。

表3 調(diào)度參數(shù)設(shè)置表

（1）拖期系數(shù)τ：用以調(diào)整各零件交貨期的平均松弛度。各零件的平均交貨期設(shè)定為（1－τ）M，其中，M ＝為 零件數(shù)量，Rbtnk為瓶頸機(jī)床為競(jìng)爭(zhēng)機(jī)床Ri的所有工序的平均加工周期。

（2）交貨期分布R：用以調(diào)節(jié)不同零件交貨期的集中程度，各零件的交貨期依據(jù)（1－τ）×M×U（1－R／2，1＋R／2）隨機(jī)產(chǎn)生。R 值越小，表示各零件交貨期分布越集中，調(diào)度難度更大。

（3）瓶頸機(jī)床數(shù)量Nbtnk：用來(lái)調(diào)節(jié)初始狀態(tài)下調(diào)度任務(wù)集內(nèi)的瓶頸機(jī)床數(shù)量。

6．2 參數(shù)設(shè)置和評(píng)價(jià)指標(biāo)設(shè)計(jì)

6．2．1 加工參數(shù)設(shè)置

（1）零件批量Si依據(jù)U（1，7）等概率隨機(jī)生成。

（2）工序加工周期duli按Si×U（0．5，1．5）等概率隨機(jī)生成。

（3）零件拖期懲罰系數(shù)tar di按5U（1，2Si）等概率隨機(jī)產(chǎn)生。

（4）庫(kù)存成本系數(shù)invli：考慮到庫(kù)存成本與零件批量、原材料價(jià)格等因素相關(guān)，在該試驗(yàn)中，將invli設(shè)置為零件批量Si，暫未考慮材料價(jià)格因素的影響。

（5）最早可接受釋放期er di和最晚可接受的完工時(shí)間lcdi：為增加調(diào)度問(wèn)題的復(fù)雜度，上述8組調(diào)度子問(wèn)題內(nèi)所有零件均設(shè)置為相同的最早可接受釋放期er di＝0和最晚可接受完工時(shí)間lcdi＝2 M。

6．2．2 評(píng)價(jià)指標(biāo)設(shè)計(jì)

選擇包括上述約束優(yōu)化調(diào)度模型中的調(diào)度總成本在內(nèi)的4個(gè)評(píng)價(jià)指標(biāo)來(lái)評(píng)估算法性能。其中，平均加權(quán)拖期用來(lái)評(píng)測(cè)調(diào)度拖期性能好壞；平均加權(quán)流動(dòng)時(shí)間用以評(píng)測(cè)零件加工過(guò)程中的在制品庫(kù)存成本；平均加權(quán)系統(tǒng)時(shí)間用來(lái)評(píng)測(cè)零件的成品庫(kù)存成本和在制品庫(kù)存成本。

（1）平均加權(quán)拖期成本。該評(píng)價(jià)指標(biāo)是指各零件拖期成本的加權(quán)平均值，即

（2）平均加權(quán)流動(dòng)時(shí)間。該評(píng)價(jià)指標(biāo)是指各零件從開(kāi)始加工至加工結(jié)束所需時(shí)間的加權(quán)平均值，用以評(píng)價(jià)在制品的流動(dòng)庫(kù)存成本，其表達(dá)式為

（3）平均加權(quán)系統(tǒng)時(shí)間。該評(píng)價(jià)指標(biāo)包括零件因提前完工而產(chǎn)生的成品庫(kù)存成本和在制品庫(kù)存成本兩部分，該指標(biāo)綜合反映了各零件庫(kù)存成本和在制品庫(kù)存成本，表達(dá)式為

6．3 仿真結(jié)果分析

文獻(xiàn)［15］針對(duì)提前／拖期調(diào)度問(wèn)題，提出了兩種有效的Tardy／Early排序規(guī)則，即線性E／T排序（LIN－ET）規(guī)則和指數(shù)E／T排序（EXP－ET）規(guī)則，并通過(guò)試驗(yàn)證明這兩種排序規(guī)則在降低提前／拖期成本方面具有優(yōu)勢(shì)。仿真試驗(yàn)環(huán)境為：CPU為Intel 2．4GHz，內(nèi)存為1．98GB；仿真軟件采用MATLAB 7．0。該試驗(yàn)以上述調(diào)度用例為測(cè)試對(duì)象，將本文提出的約束優(yōu)化調(diào)度算法COSA和LIN－ET、EXP－ET兩種規(guī)則進(jìn)行比較。圖2～圖5分別表示COSA和LIN－ET、EXP－ET在平均調(diào)度總成本、平均加權(quán)拖期、平均加權(quán)流動(dòng)時(shí)間和平均加權(quán)系統(tǒng)時(shí)間4個(gè)評(píng)價(jià)指標(biāo)下的試驗(yàn)結(jié)果。

圖2 平均調(diào)度總成本仿真結(jié)果

在仿真試驗(yàn)中，COSA在總共80次試驗(yàn)中，平均搜索效率（定義為待調(diào)度工序總數(shù)和求得調(diào)度解所產(chǎn)生的搜索狀態(tài)數(shù)的比值）為85．6%，平均計(jì)算時(shí)間為35s。說(shuō)明COSA能夠有效降低“Thrashing”頻發(fā)現(xiàn)象，從而保證搜索算法以較高的搜素效率和較小的計(jì)算成本求得E／T調(diào)度問(wèn)題的優(yōu)化解。

圖3 平均加權(quán)拖期成本仿真結(jié)果

圖4 平均加權(quán)流動(dòng)時(shí)間仿真結(jié)果

圖5 平均加權(quán)系統(tǒng)時(shí)間仿真結(jié)果

從圖2可以看出：COSA在總共8組試驗(yàn)中，除第7組試驗(yàn)外，其余7組試驗(yàn)得到的平均調(diào)度總成本均小于LIN－ET和EXP－ET。從圖3可以看出：對(duì)于拖期成本指標(biāo)而言，COSA和EXP－ET的性能基本相當(dāng)，但要優(yōu)于LIN－ET在拖期成本方面的表現(xiàn)。

從圖4、圖5可以得知：COSA在壓縮在制品庫(kù)存和成品庫(kù)存兩項(xiàng)指標(biāo)上明顯優(yōu)于LIN－ET和EXP－ET。尤其在調(diào)度環(huán)境最為苛刻的第8組試驗(yàn)（瓶頸機(jī)床數(shù)量多，交貨期松弛度緊，且各零件交貨期分布較集中）中，當(dāng)LIN－ET和EXP－ET的在制品庫(kù)存成本和成品庫(kù)存成本大幅攀升（達(dá)到峰值）的情況下，而COSA則維持在一個(gè)相對(duì)較低的庫(kù)存水平。

與EXP－ET規(guī)則（該方法性能優(yōu)于LINET）相比較而言，在共8組仿真試驗(yàn)中，COSA降低在制品流動(dòng)庫(kù)存成本15%～35%，降低成品和在制品庫(kù)存總成本10%～30%，壓縮平均調(diào)度總成本8%以上。

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

本文在滿(mǎn)足工藝路線、機(jī)床能力和交貨期約束條件的前提下，將提前／拖期成本指標(biāo)引入調(diào)度問(wèn)題，從而將約束滿(mǎn)足求解JSSP的傳統(tǒng)方式轉(zhuǎn)化為約束優(yōu)化求解；遵循解決實(shí)際工程問(wèn)題的思維模式和原則，將復(fù)雜的調(diào)度優(yōu)化問(wèn)題劃分為瓶頸機(jī)床優(yōu)先識(shí)別和單機(jī)排序優(yōu)化兩個(gè)階段，以降低大規(guī)模JSSP的計(jì)算復(fù)雜度和提高調(diào)度方法的實(shí)用性；為了降低回溯搜索中的“Thrashing”現(xiàn)象發(fā)生概率，引入一致性預(yù)處理機(jī)制以事先修剪和過(guò)濾剩余搜索空間的潛在沖突源，回溯前移機(jī)制可以有效避免搜索后期出現(xiàn)約束沖突而導(dǎo)致已調(diào)度中間結(jié)果發(fā)生大面積回溯的弊端。

為綜合測(cè)試COSA算法性能，設(shè)計(jì)了一組交貨期的松弛度和集中度可組合調(diào)整、加工參數(shù)隨機(jī)產(chǎn)生的80個(gè)調(diào)度問(wèn)題，并將COSA與在提前／拖期調(diào)度方面具有優(yōu)勢(shì)的LIN－ET、EXP－ET排序規(guī)則進(jìn)行比較，結(jié)果表明：COSA與EXPET在拖期成本指標(biāo)方面結(jié)果相近，但在減少在制品庫(kù)存成本和成品庫(kù)存成本兩方面具有明顯優(yōu)勢(shì)，從而保證了調(diào)度總成本相對(duì)較低。

［1］ Fox M S．Constraint－directed Search：A Case Study of Job－shop Scheduling［D］．Pittsbur gh：Car negie－Mellon University，1983．

［2］ Fox M S，Smith S F．ISIS－ a Knowledge－based System for Factor y Scheduling［J］．Expert Systems，1984，1（1）：25－49．

［3］ Smith S F，Peng Si Ow，Jean－Yves Porvin．OPIS：an Opportunistic Factory Scheduling System［C］／／Proceedings of the 3rd International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems．Charleston，1990：268－274．

［4］ Sadeh N，F(xiàn)ox M S．Variable and Value Ordering Heuristics f or t he Job Shop Scheduling Constraint Satisfaction Problem ［J］．Artificial Intelligence，1996，86（1）：1－41．

［5］ Sadeh N，Sycara K，Xiong Y．Backtracking Techniques for the Job Shop Scheduling Constraint Satisfaction Problem［J］．Artificial Intelligence，1995，76（1／2）：455－480．

［6］ Barták R，Skalicky T．A Local Approach to Automated Correction of Violated Precedence and Resource Constraints in Manually Altered Schedules［C］／／Proceedins of MISTA 2009：Fourth Multidisciplinary International Scheduling Conference：Theory and Applications．Dublin，Ireland，2009：507－517．

［7］ Barták R．Constraint Satisfaction Techniques in Planning and Scheduling：An Introduction［J］．In Archives of Control Sciences，2008，18（2）：141－158．

［8］ 郭冬芬，李鐵克．基于約束滿(mǎn)足的車(chē)間調(diào)度算法綜述［J］，計(jì)算機(jī)集成制造系統(tǒng)，2007，13（1）：117－125．

［9］ 段黎明，陳進(jìn)，劉飛．基于約束分析的Job Shop調(diào)度算法的綜述［J］．重慶大學(xué)學(xué)報(bào)，1998，21（1）：133－138．

［10］ 陳恩紅，薛瀚宏．基于約束滿(mǎn)足的Job Shop調(diào)度問(wèn)題求解方法研究［J］．軟件學(xué)報(bào)，1998，9（12）：946－948．

［11］ 上官春霞，周泓，師瑞峰，等．作業(yè)車(chē)間排序重調(diào)度問(wèn)題及其改進(jìn)修復(fù)約束滿(mǎn)足算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2008，14（9）：1742－1751．

［12］ Dechter R，Meiri I．Experimental Evaluation of Preprocessing Techniques in Constraint Satisfaction Problems［C］／／Proceedings of the Eleventh International Joint Conference on Artificial Intelligence．Detroit，1989：271－277．

［13］ 楊宏安，孫樹(shù)棟，司書(shū)賓．基于動(dòng)態(tài)一致性增強(qiáng)技術(shù)的Job Shop調(diào)度算法研究［J］，西北工業(yè)大學(xué)學(xué)報(bào)，2007，25（4）：523－527．

［14］ 楊宏安．基于COP的作業(yè)車(chē)間調(diào)度問(wèn)題研究［D］．西安：西北工業(yè)大學(xué)，2007．

［15］ Peng S O，Morton T．The Single Machine Early／Tardy Problem［J］．Management Science，1989，35（2）：177－191．