約束優(yōu)化求解作業(yè)車間調(diào)度問題研究

楊宏安 孫啟峰 郭 杰

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

0 引言

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

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

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

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

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

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

定義1 約束優(yōu)化問題由一個變量集、變量值域、約束集和目標(biāo)函數(shù)組成，可視為一個四元組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)化問題的解是在滿足全部約束集C的條件下，在變量集V內(nèi)尋求一組變量賦值｛a1，a2，…，an｝并使得目標(biāo)函數(shù)O取得最優(yōu)，其中ai∈Di。

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

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

對于調(diào)度任務(wù)池內(nèi)的任意零件Ji，假設(shè)Ji的任一加工工序為Oli，其中，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的四元組分析方法來構(gòu)建約束優(yōu)化調(diào)度模型。

2．2．1 變量集

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

2．2．2 約束集

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

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

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

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

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

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

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

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

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

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

式中，estli＋1為Oli的下道工序的最早開工時間；lstil－1為Oli的上道工序的最晚開工時間。

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

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

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

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

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

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

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

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

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

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

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

遵循上述的兩階段調(diào)度和動態(tài)修訂搜索空間的調(diào)度策略，結(jié)合“Thrashing”現(xiàn)象消減機制，在深度優(yōu)先搜索算法的基礎(chǔ)上，設(shè)計了圖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的開工時間賦值。該算法的步驟如下：

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

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

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

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

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

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

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

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

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

6 仿真試驗

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

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

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

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

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

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

6．2 參數(shù)設(shè)置和評價指標(biāo)設(shè)計

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

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

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

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

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

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

6．2．2 評價指標(biāo)設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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

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

［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］ 郭冬芬，李鐵克．基于約束滿足的車間調(diào)度算法綜述［J］，計算機集成制造系統(tǒng)，2007，13（1）：117－125．

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

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

［11］ 上官春霞，周泓，師瑞峰，等．作業(yè)車間排序重調(diào)度問題及其改進修復(fù)約束滿足算法［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］ 楊宏安，孫樹棟，司書賓．基于動態(tài)一致性增強技術(shù)的Job Shop調(diào)度算法研究［J］，西北工業(yè)大學(xué)學(xué)報，2007，25（4）：523－527．

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

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