姜 銳 陳亞絨， 管在林 周宏明

1.溫州大學(xué)，溫州，325035

2.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢，430074

0 引言

不同類型產(chǎn)品或工件連續(xù)加工過(guò)程中，通常要考慮發(fā)生在機(jī)器上的換型或安裝時(shí)間及成本，以及由此引起的機(jī)器、工裝夾具、產(chǎn)品、工件的損失或損壞成本。在多品種小批量生產(chǎn)環(huán)境下，為減少因產(chǎn)品范圍快速擴(kuò)展而引起的大量換型或安裝時(shí)間，企業(yè)普遍采用基于成組技術(shù)的混流生產(chǎn)方式，即將結(jié)構(gòu)形狀、工藝以及工裝等相似的產(chǎn)品或工件組合為批量生產(chǎn)，由此產(chǎn)生的調(diào)度問(wèn)題稱為 成 組/工 件 組 調(diào) 度 （group scheduling/family scheduling，GS/FS）問(wèn)題［1－2］。成組調(diào)度問(wèn)題一般包括以下三項(xiàng)任務(wù)：①將工件/零部件分配到某個(gè)加工批；②加工批內(nèi)的工件排序；③加工批在機(jī)器設(shè)備上排序。

成組混流生產(chǎn)的本質(zhì)在于對(duì)同一機(jī)器上具有相似制造特征的不同工件成組批量生產(chǎn)，以減少安裝時(shí)間。相似工件的成批生產(chǎn)能夠通過(guò)減少安裝時(shí)間釋放機(jī)器產(chǎn)能，但同時(shí)也將使延后加工的工件交期受到影響，因此成組調(diào)度需要平衡滿足交期與安裝時(shí)間減少之間的沖突關(guān)系［3］。相較于傳統(tǒng)調(diào)度問(wèn)題，成組調(diào)度問(wèn)題不僅目標(biāo)更多樣化，而且處理的約束也更多。作為一類復(fù)雜的組合優(yōu)化問(wèn)題，成組調(diào)度問(wèn)題的快速求解有賴于高效的調(diào)度方法。

按照機(jī)器的數(shù)量特征可以將成組調(diào)度問(wèn)題分為單機(jī)、并行機(jī)與多機(jī)等類型［4－5］，單機(jī)成組調(diào)度問(wèn)題因大量的工業(yè)應(yīng)用需求備受關(guān)注。Hitomi等［5］最早提出了運(yùn)用分支定界法確定工件和工件組的排序；Ghosh［6］提出了運(yùn)用后向動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)工件的總加權(quán)完成時(shí)間最小化；Panwalkar等［7］提出了按照SPT與EDD規(guī)則實(shí)現(xiàn)單機(jī)成組調(diào)度問(wèn)題總延遲時(shí)間最小化的PSK法；Liao等［8］提出了一種基于啟發(fā)式算法的禁忌搜索方法求解存在主要與次要安裝時(shí)間的成組調(diào)度問(wèn)題；王秀利等［9］針對(duì)總流程時(shí)間最小化的單機(jī)成組作業(yè)優(yōu)化調(diào)度問(wèn)題，提出了基于優(yōu)化性質(zhì)的構(gòu)造性啟發(fā)算法；Mason［10］提出了一種使用SWPT（shortest weighted processing time）規(guī)則的遺傳算法實(shí)現(xiàn)工件的加權(quán)完成時(shí)間最小化；聶黎等［11］針對(duì)最小化提前/拖期懲罰的單機(jī)調(diào)度問(wèn)題，研究了運(yùn)用基因表達(dá)式編程及其改進(jìn)算法前序基因表達(dá)式編程的求解方法；Crauwels等［12］開(kāi)發(fā)了模擬退火、禁忌搜索等多個(gè)鄰域搜索啟發(fā)式方法最小化工件的加權(quán)完成時(shí)間。

以上針對(duì)單機(jī)成組調(diào)度問(wèn)題的研究在不同程度上為相關(guān)的后續(xù)研究提供了基礎(chǔ)，但面對(duì)更為復(fù)雜的現(xiàn)實(shí)問(wèn)題需要更為有效的建模方法和求解方法。本文針對(duì)單機(jī)成組調(diào)度問(wèn)題工件組是否分批、安裝時(shí)間與工件排序是否有關(guān)等復(fù)雜的約束特征，將其作為一類約束滿足問(wèn)題，構(gòu)建了更接近于現(xiàn)實(shí)問(wèn)題表達(dá)的單機(jī)成組調(diào)度約束模型，以最小化加權(quán)流程時(shí)間與加權(quán)拖期為目標(biāo)，設(shè)計(jì)了啟發(fā)式搜索與約束傳播相結(jié)合的求解方法，實(shí)現(xiàn)了不同類型問(wèn)題的快速建模和求解。

1 單機(jī)成組調(diào)度問(wèn)題描述

起源于人工智能領(lǐng)域的約束滿足技術(shù)通過(guò)分離問(wèn)題的建模與求解算法，以更加接近于現(xiàn)實(shí)世界的方式描述問(wèn)題及其復(fù)雜的約束，利用變量之間的約束關(guān)系傳播與一致性檢驗(yàn)等方法進(jìn)行模型求解，在有效解決復(fù)雜問(wèn)題，特別是在組合優(yōu)化問(wèn)題方面具有非常明顯的優(yōu)勢(shì)。此外，約束滿足方法還允許用戶在不改變算法的情況下，通過(guò)增減約束動(dòng)態(tài)地修改模型，為其他問(wèn)題所重用，因此利用約束滿足方法進(jìn)行生產(chǎn)調(diào)度問(wèn)題建模和求解得到了廣泛的關(guān)注和研究。目前的約束滿足計(jì)劃調(diào)度問(wèn)題研究主要限于傳統(tǒng)的車(chē)間作業(yè)調(diào)度，如Beck等［13］提出了基于資源依賴度和爭(zhēng)用度等動(dòng)態(tài)問(wèn)題結(jié)構(gòu)信息的啟發(fā)式搜索技術(shù)求解車(chē)間調(diào)度問(wèn)題，Watson等［14］研究了混合約束規(guī)劃與局部搜索方法求解車(chē)間調(diào)度問(wèn)題。在運(yùn)用約束滿足的方法解決成組調(diào)度問(wèn)題方面，盡管 Malapert等［15］提出了研究對(duì)象為批處理時(shí)間下的成批以及排序問(wèn)題，但迄今文獻(xiàn)中尚未出現(xiàn)運(yùn)用約束滿足方法的工件可用性條件下的單機(jī)成組調(diào)度問(wèn)題研究。

單機(jī)成組調(diào)度是指將多個(gè)屬于不同工件組的工件加工任務(wù)根據(jù)相似性分派到制造資源的過(guò)程，如圖1所示，其目的是綜合考慮制造資源能力、工件成組特性、工件交期等約束，合理安排工件批和工件的生產(chǎn)活動(dòng)以同時(shí)滿足約束和優(yōu)化目標(biāo)。因此，單機(jī)成組調(diào)度問(wèn)題是一類有限域約束滿足問(wèn)題或約束優(yōu)化問(wèn)題（COPs），且大多數(shù)都是NP難題。

圖1 機(jī)器M1的成組生產(chǎn)示意圖

對(duì)于成組調(diào)度問(wèn)題，一般假設(shè)：每一種工件組的加工都需要精確的安裝時(shí)間，而且此安裝時(shí)間遠(yuǎn)遠(yuǎn)大于工件的加工時(shí)間，該假設(shè)被稱為成組假設(shè)。如果成組假設(shè)成立，則同一工件組內(nèi)的工件在機(jī)器上連續(xù)加工，每一工件組的處理時(shí)間等于該工件組中所有工件的處理時(shí)間總和；否則，同一工件組內(nèi)的工件可分割加工。通常將連續(xù)加工的一系列工件集合稱為一個(gè)加工批，如果加工批中的所有工件加工完成之后通過(guò)托盤(pán)、箱子或拖車(chē)等容器運(yùn)輸?shù)较乱还ば蜻M(jìn)行加工，則稱為批可用性；否則稱為工件可用性。本文的研究對(duì)象為工件可用性條件下的單機(jī)成組調(diào)度問(wèn)題。

表1 成組調(diào)度問(wèn)題的參數(shù)變量與值域

圖2 工件組安裝時(shí)間獨(dú)立于工件組排序且不可分割加工調(diào)度示意圖

圖3 工件組調(diào)度方案中的運(yùn)行含義

圖4 工件組安裝時(shí)間獨(dú)立于工件組排序且可分割加工調(diào)度示意圖

對(duì)于單機(jī)成組調(diào)度問(wèn)題，如果工件組i或運(yùn)行r（下文統(tǒng)稱為工件組）的安裝時(shí)間與之前處理的工件組無(wú)關(guān)，則認(rèn)為工件組的安裝時(shí)間獨(dú)立于工件組排序；如果安裝時(shí)間依賴于之前處理的工件組，則認(rèn)為工件組的安裝時(shí)間依賴于工件組排序（sequence－dependent setup times，SDST）。

根據(jù)工件可用性條件下的單機(jī)成組調(diào)度問(wèn)題的加工特征，可將其分為4種子問(wèn)題：①工件組安裝時(shí)間獨(dú)立于工件組排序且不可分割加工問(wèn)題；②工件組安裝時(shí)間獨(dú)立于工件組排序可分割加工問(wèn)題；③工件組安裝時(shí)間依賴工件組排序不可分割加工問(wèn)題；④工件組安裝時(shí)間依賴工件組排序可分割加工問(wèn)題。

2 問(wèn)題的約束滿足模型

2.1 單機(jī)成組調(diào)度問(wèn)題的決策變量

成組調(diào)度問(wèn)題旨在為每一個(gè)工件組及工件安排一個(gè)合理的制造期間，保證優(yōu)化目標(biāo)實(shí)現(xiàn)。影響成組調(diào)度目標(biāo)實(shí)現(xiàn)的決策變量主要是序變量，包括工件組排序與工件組內(nèi)工件排序，O（i）表示排在第i位置的工件組序號(hào)，O（i）∈ ｛1，2，…，f｝；O（i，k）表示排在工件組i中第k位置的工件序號(hào)，O（i，k）∈ ｛1，2，…，ni｝。

根據(jù)決策變量，事先給定的參數(shù)變量值將更新，如工件組JO（i）的開(kāi)始加工時(shí)間為st O（i），工件JO（i，k）的開(kāi)始加工時(shí)間為st O（i，k），工件組JO（i）的加工時(shí)間為p O（i），工件JO（i，k）的加工時(shí)間為p O（i，k），其他依此類推。為了用決策變量描述工件組之間的安裝時(shí)間，假設(shè)用F＝｛1，2，…，f｝表示工件組集合，引入虛擬工件組0，生成F0＝ ｛0，1，…，f｝。對(duì)工件組排序，得到序變量集合OF＝ ｛O（0），O（1），…，O（f）｝，則排在第i位置的工件組的安裝時(shí)間為s O（i－1）O（i），如果工件組的安裝時(shí)間與排序無(wú)關(guān)，則為sO（i）。對(duì)于增加的虛擬工件組0，有O（0）＝0，p0＝0，d0＝0，w0＝0。

2.2 單機(jī)成組調(diào)度問(wèn)題的約束

對(duì)于以上給出的4種單機(jī)成組調(diào)度問(wèn)題，運(yùn)用約束滿足方法建模，主要包括如下約束。

（1）工件成組特性約束。

①工件j只能屬于一個(gè)工件組i，即

②屬于工件組i的工件數(shù)量總和為n i，即

③所有工件組的工件數(shù)量ni之和為總工件數(shù)量n，即

④所有運(yùn)行r的工件數(shù)量βr之和為總工件數(shù)量n，即

⑤工件組i或運(yùn)行r的權(quán)重為

（2）工件組的處理時(shí)間約束。

①工件組不可分割加工，將工件組i整體作為一個(gè)復(fù)合工件，其處理時(shí)間為

②工件組可分割加工，用βr表示分割之后運(yùn)行r中的工件數(shù)量，則運(yùn)行r的處理時(shí)間為

（3）工件組的加工時(shí)間滿足以下析取約束：

（4）工件的加工時(shí)間約束。

① 工件JO（i，ni）與工件JO（i＋1，1）的加工時(shí)間滿足以下析取約束：

② 工件JO（i，k）與工件JO（i，k＋1）滿足以下條件：

（5）工件JO（i，k）的完成時(shí)間約束。

（6）工件JO（i，k）的拖期約束。

2.3 單機(jī)成組調(diào)度問(wèn)題的目標(biāo)

成組調(diào)度通過(guò)將相似工件成組加工以減少安裝時(shí)間，可能會(huì)導(dǎo)致工件拖期。在精益生產(chǎn)方式盛行的今天，準(zhǔn)時(shí)是企業(yè)獲得市場(chǎng)競(jìng)爭(zhēng)的關(guān)鍵要素，對(duì)于多品種小批量生產(chǎn)，在進(jìn)行批量成組生產(chǎn)時(shí)，既要節(jié)約安裝時(shí)間，也要保證產(chǎn)品交期。因此，本文以最小化加權(quán)流程時(shí)間與加權(quán)拖期為目標(biāo)，即

3 基于約束滿足的問(wèn)題求解方法

針對(duì)成組調(diào)度問(wèn)題的多目標(biāo)優(yōu)化，目前文獻(xiàn)中一般通過(guò)為各個(gè)目標(biāo)設(shè)置權(quán)重等方法將多目標(biāo)優(yōu)化轉(zhuǎn)化為單目標(biāo)優(yōu)化，具有一定的主觀性，且求解的復(fù)雜性高。因此，本文將最小化加權(quán)流程時(shí)間與加權(quán)拖期目標(biāo)的優(yōu)化分為兩個(gè)階段完成。第一階段，以最小化加權(quán)流程時(shí)間為目標(biāo)，對(duì)工件組進(jìn)行排序或?qū)⒐ぜM分割成運(yùn)行，確定運(yùn)行的排序；第二階段，以確定的排序作為初始解，其對(duì)應(yīng)的加權(quán)流程時(shí)間作為約束，優(yōu)化工件組或運(yùn)行排序，最小化加權(quán)拖期。算法主流程如圖5所示，圖中①～④分別對(duì)應(yīng)單機(jī)成組調(diào)度問(wèn)題的4種子問(wèn)題。

3.1 工件組分割條件

圖5 單機(jī)成組調(diào)度問(wèn)題的算法流程

3.2 最小化加權(quán)流程時(shí)間的變量排序啟發(fā)式搜索算法

（1）工作組內(nèi)工件排序初始化。對(duì)于工件組Ji中的工件J ik按照SWPT規(guī)則排序，如果此值相同，按照加權(quán)最早交期（weighted earliest duedate，WEDD）規(guī)則排序，得到工件組Ji的排序集合

令β＝ ?，η＝1，進(jìn)入步驟（2）。

對(duì)于成組調(diào)度，組內(nèi)工件的排序運(yùn)用WEDD規(guī)則是可行的，但是工件組中任意一個(gè)工件都可能產(chǎn)生最大拖期，因此需要對(duì)工件組的交期進(jìn)行調(diào)整。假設(shè)工件組i內(nèi)的工件已經(jīng)按照WEDD規(guī)則排序，且工件組從st O（i）開(kāi)始加工，則工件組i中k位置的工件J O（i，k）的拖期時(shí)間為

式（13）中，qO（i，k）＝p i－ （p O（i，1）＋p O（i，2）＋ …＋p O（i，k）），表示工件JO（i，k）完成之后的工件組剩余處理時(shí)間。如果定 義工件JO（i，k）的工件組調(diào)整交期d′O（i，k）＝d O（i，k）＋q O（i，k），則工件組中工件的最大拖 期 是 maxk（cO（i，k）－d O（i，k））＝st O（i）＋p O（i） －mink（d′O（i，k））。因此，定義 工 件 組的交 期d O（i）＝mink（d′O（i，k））。一旦工件組中工件按照 WEDD 規(guī)則排序，此值很容易確定，且不依賴于工件組的開(kāi)始處理時(shí)間。

3.3 最小化加權(quán)拖期的變量排序啟發(fā)式搜索與前向約束傳播混合方法

以第一階段獲得排序S為初始可行解，按照“如果對(duì)于所有工件組i，g，q，安裝時(shí)間滿足siq≤sig＋sgq，即三角不等式，則最優(yōu)解中工件組的排序依然滿足交期按照非降順序排列［2］”規(guī)則，設(shè)計(jì)了以工件組排序變量啟發(fā)式搜索與前向約束傳播混合的算法（與3.2節(jié)類似，這里給出的算法適用于安裝時(shí)間依賴工件組排序的問(wèn)題）。

圖6 工件組排序規(guī)則

表2 深度優(yōu)先搜索域縮減規(guī)則

（4）按照已經(jīng)排序的工件組變量生成調(diào)度方案。

5 實(shí)例驗(yàn)證

運(yùn)用以上建模與求解方法對(duì)某企業(yè)的成組生產(chǎn)調(diào)度問(wèn)題進(jìn)行了實(shí)例驗(yàn)證。該企業(yè)針對(duì)多品種小批量需求，采用成組生產(chǎn)組織形式，某生產(chǎn)期間有工件加工任務(wù)14項(xiàng)，各項(xiàng)任務(wù)的處理時(shí)間、交貨時(shí)間、權(quán)重以及成組信息如表3所示。

表3 車(chē)間工件生產(chǎn)任務(wù)信息

機(jī)器上的安裝時(shí)間分為兩種，一種是安裝時(shí)間，一種是依賴于工件組排序的安裝時(shí)間，具體數(shù)據(jù)如表4所示。其中第一行和第一列中工作組f1～f5分別表示安裝時(shí)間的計(jì)算起點(diǎn)和終點(diǎn)。

表4 機(jī)器上工件組的安裝時(shí)間 min

4.1 工件組不可分割加工結(jié)果

對(duì)于表3所示的14項(xiàng)工件任務(wù)，當(dāng)工件組不可分割加工時(shí)，則在排序時(shí)將工件組整體作為一個(gè)復(fù)合工件，按照前面提出的方法，計(jì)算各個(gè)復(fù)合工件的加工時(shí)間、權(quán)重和調(diào)整交期，結(jié)果如表5所示。

表5 工件組不可分割加工數(shù)據(jù)表

運(yùn)用本文提出的方法進(jìn)行求解，分別得到工件組安裝時(shí)間與排序有關(guān)、工件組安裝時(shí)間與排序無(wú)關(guān)兩種情況下的結(jié)果，兩種結(jié)果的比較如表6所示。

表6 工件組不可分割加工情況下的兩種運(yùn)算結(jié)果比較

由表6可以看出，安裝時(shí)間與工件組排序無(wú)關(guān)、安裝時(shí)間與工件組排序有關(guān)兩種情況下的最優(yōu)排序方案不同，安裝時(shí)間、目標(biāo)值也存在較大差異。在安裝時(shí)間與工件組排序有關(guān)情況下，通過(guò)合理安排工件組的先后順序，調(diào)整了工件組f4與工件組f3的順序，將安裝時(shí)間從75min縮減為45min，從而縮減了工件組的加權(quán)流程時(shí)間。

4.2 工件組可以分割加工結(jié)果

當(dāng)工件組可以分割加工時(shí)，需要通過(guò)以SWPT為準(zhǔn)則的工件組內(nèi)排序變量賦值，SWEPT為準(zhǔn)則的工件組排序變量賦值，首先對(duì)工件組進(jìn)行分割。運(yùn)行算法發(fā)現(xiàn)，當(dāng)工件組安裝時(shí)間與排序無(wú)關(guān)時(shí)，工件組未進(jìn)行分割，結(jié)果與工件組不可分割加工情況下相同。分析產(chǎn)生這種結(jié)果的原因在于工件組安裝時(shí)間為固定值，且大于等于工件的加工時(shí)間，也就是符合前面提出的成組假設(shè)，在這種情況下，工件組通常是不分割加工的。

當(dāng)工件組的安裝時(shí)間依賴工件組排序時(shí)，對(duì)5個(gè)工件組進(jìn)行分割，得到7個(gè)運(yùn)行，R＝｛r1，r2，r3，r4，r5，r6，r7｝＝ ｛（J11，J13，J12），（J51），（J31，J33，J32）， （J21，J23）， （J52）， （J42，J41，J43），（J22）｝。對(duì)這7個(gè)運(yùn)行進(jìn)行排序，得到最優(yōu)的排序方案為：S＝ ｛（J42，J41，J43），（J31，J33，J32），（J11，J13，J12），（J51），（J52），（J21，J23），（J22）｝。對(duì)應(yīng)的加權(quán)流程時(shí)間為4693min，加權(quán)拖期為1002min，目標(biāo)值為5695min。可以看出，在最優(yōu)排序方案中，屬于同一工件組的運(yùn)行r2＝｛J51｝和運(yùn)行r5＝ ｛J52｝，運(yùn)行r4＝ ｛J21，J23｝和運(yùn)行r7＝ ｛J22｝，由于安裝時(shí)間的緣故，按照先后緊接的順序生產(chǎn)。

5 結(jié)語(yǔ)

本文針對(duì)單機(jī)成組調(diào)度問(wèn)題，首先根據(jù)工件可用性條件下安裝時(shí)間是否與工件排序相關(guān)、工件組能否分割加工等加工特征，對(duì)單機(jī)成組調(diào)度問(wèn)題進(jìn)行了類型分析；其次，考慮工件成組特性、工件組交期、處理時(shí)間等多種制約條件，借鑒約束滿足的理論和方法，以工件組和工件的排序變量為決策變量，構(gòu)建了約束滿足模型；再次，采用兩階段優(yōu)化方法，設(shè)計(jì)了以問(wèn)題結(jié)構(gòu)和優(yōu)化特征為指導(dǎo)的啟發(fā)式搜索與約束傳播混合的求解方法；最后，運(yùn)用提出的建模和求解方法對(duì)某企業(yè)的成組生產(chǎn)調(diào)度問(wèn)題進(jìn)行了實(shí)例驗(yàn)證。本文提出的方法允許通過(guò)添加或改變少量約束方便地改變問(wèn)題模型，在不改變算法的情況下動(dòng)態(tài)地修改模型，快速地解決單機(jī)成組調(diào)度問(wèn)題的4種子問(wèn)題。

［1］Potts C N.Scheduling Two Job Classes on a Single Machine［J］.Computers ＆ Operations Research，1991，18（5）：411－415.

［2］Webster S，Baker K R.Scheduling Groups of Jobs on a Single Machine［J］.Operations Research，1995，43（4）：692－703.

［3］陳亞絨，管在林，彭運(yùn)芳，等.面向大規(guī)模定制的瓶頸成組調(diào)度啟發(fā)式方法研究［J］.中國(guó)機(jī)械工程，2010，21（8）：957－962.

Chen Yarong，Guan Zailin，Peng Yunfang.Research on Bottleneck Group Scheduling Heuristics for Mass Customization［J］.China Mechanical Engineering，2010，21（8）：957－962.

［4］Potts C N，Kovalyov M Y.Scheduling with Batching：A Review［J］.European Journal of Operational Research，2000，120（2）：228－249.

［5］Hitomi K，Ham I.Operations Scheduling for Group Technology Applications［J］.Annals of the CIRP，1976，25（1）：419－422.

［6］Ghosh J B.Batch Scheduling to Minimize Total Completion Time［J］.Operations Research Letters，1994，6（5）：271－275.

［7］Panwalkar S S，Smith M L，Koulamas C P.A Heuristic for the Single Machine Tardiness Problem［J］.European Journal of Operational Research，1993，70（3）：304－310.

［8］Liao L M，Liao C J.A Tabu Search Approach for Single Machine Scheduling with Major and Minor Setups［J］.International Journal of Industrial Engineering：Theory Applications and Practice，2002，9（2）：174－183.

［9］王秀利，吳惕華，劉磊.一種求解單機(jī)成組作業(yè)優(yōu)化調(diào)度的啟發(fā)算法［J］.計(jì)算機(jī)仿真，2003，20（2）：48－50.

Wang Xiuli，Wu Xihua，Liu Lei.A Heuristic Algorithm for Single Machine Scheduling with Job Class Setups［J］.Computer Simulation，2003，20（2）：48－50.

［10］Mason A J.Genetic Algorithms and Scheduling Problems［D］.Cambridge：University of Cambridge，UK，1992.

［11］聶黎，高亮，胡譯丹.基于前序基因表達(dá)式編程的單機(jī)成組調(diào)度算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，13（11）：2261－2268，2275.

Nie Li，Gao Liang，Hu Yidan.Prefix－gene－expression－programming－based Algorithm for Scheduling Groups of Jobs on a Single Machine［J］.Computer Integrated Manufacturing Systems，2008，13（11）：2261－2268，2275.

［12］Crauwels H A J，Potts C N，van Wassenhove L N.Local Search Heuristics for Single Machine Scheduling with Batch Set－up Times to Minimize Total Weighted Completion Time［J］.Annals of Operations Research，1997，70：261－279.

［13］Beck J C，F(xiàn)ox M S.Dynamic Problem Structure A－nalysis as a Basis for Constraint－directed Scheduling Heuristics［J］.Artificial Intelligence，2000（117）：31－81.

［14］Watson J P，Beck J C.A Hybrid Constraint Programming/Local Search Approach to the Job－Shop Scheduling Problem［C］//Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems.Paris，2008，5015：263－277.

［15］Malapert A，Guéret C，Rousseau LM.A Constraint Programming Approach for a Batch Processing Problem with Non－identical Job Sizes［J］.European Journal of Operational Research，2012，221（3）：533－545.