單機成組調度問題的約束滿足建模與求解方法

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

1.溫州大學，溫州，325035

2.華中科技大學數字制造裝備與技術國家重點實驗室，武漢，430074

0 引言

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

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

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

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

1 單機成組調度問題描述

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

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

圖1 機器M1的成組生產示意圖

對于成組調度問題，一般假設：每一種工件組的加工都需要精確的安裝時間，而且此安裝時間遠遠大于工件的加工時間，該假設被稱為成組假設。如果成組假設成立，則同一工件組內的工件在機器上連續(xù)加工，每一工件組的處理時間等于該工件組中所有工件的處理時間總和；否則，同一工件組內的工件可分割加工。通常將連續(xù)加工的一系列工件集合稱為一個加工批，如果加工批中的所有工件加工完成之后通過托盤、箱子或拖車等容器運輸到下一工序進行加工，則稱為批可用性；否則稱為工件可用性。本文的研究對象為工件可用性條件下的單機成組調度問題。

表1 成組調度問題的參數變量與值域

圖2 工件組安裝時間獨立于工件組排序且不可分割加工調度示意圖

圖3 工件組調度方案中的運行含義

圖4 工件組安裝時間獨立于工件組排序且可分割加工調度示意圖

對于單機成組調度問題，如果工件組i或運行r（下文統(tǒng)稱為工件組）的安裝時間與之前處理的工件組無關，則認為工件組的安裝時間獨立于工件組排序；如果安裝時間依賴于之前處理的工件組，則認為工件組的安裝時間依賴于工件組排序（sequence－dependent setup times，SDST）。

根據工件可用性條件下的單機成組調度問題的加工特征，可將其分為4種子問題：①工件組安裝時間獨立于工件組排序且不可分割加工問題；②工件組安裝時間獨立于工件組排序可分割加工問題；③工件組安裝時間依賴工件組排序不可分割加工問題；④工件組安裝時間依賴工件組排序可分割加工問題。

2 問題的約束滿足模型

2.1 單機成組調度問題的決策變量

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

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

2.2 單機成組調度問題的約束

對于以上給出的4種單機成組調度問題，運用約束滿足方法建模，主要包括如下約束。

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

①工件j只能屬于一個工件組i，即

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

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

④所有運行r的工件數量βr之和為總工件數量n，即

⑤工件組i或運行r的權重為

（2）工件組的處理時間約束。

①工件組不可分割加工，將工件組i整體作為一個復合工件，其處理時間為

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

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

（4）工件的加工時間約束。

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

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

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

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

2.3 單機成組調度問題的目標

成組調度通過將相似工件成組加工以減少安裝時間，可能會導致工件拖期。在精益生產方式盛行的今天，準時是企業(yè)獲得市場競爭的關鍵要素，對于多品種小批量生產，在進行批量成組生產時，既要節(jié)約安裝時間，也要保證產品交期。因此，本文以最小化加權流程時間與加權拖期為目標，即

3 基于約束滿足的問題求解方法

針對成組調度問題的多目標優(yōu)化，目前文獻中一般通過為各個目標設置權重等方法將多目標優(yōu)化轉化為單目標優(yōu)化，具有一定的主觀性，且求解的復雜性高。因此，本文將最小化加權流程時間與加權拖期目標的優(yōu)化分為兩個階段完成。第一階段，以最小化加權流程時間為目標，對工件組進行排序或將工件組分割成運行，確定運行的排序；第二階段，以確定的排序作為初始解，其對應的加權流程時間作為約束，優(yōu)化工件組或運行排序，最小化加權拖期。算法主流程如圖5所示，圖中①～④分別對應單機成組調度問題的4種子問題。

3.1 工件組分割條件

圖5 單機成組調度問題的算法流程

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

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

令β＝ ?，η＝1，進入步驟（2）。

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

式（13）中，qO（i，k）＝p i－ （p O（i，1）＋p O（i，2）＋ …＋p O（i，k）），表示工件JO（i，k）完成之后的工件組剩余處理時間。如果定 義工件JO（i，k）的工件組調整交期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ī)則排序，此值很容易確定，且不依賴于工件組的開始處理時間。

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

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

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

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

（4）按照已經排序的工件組變量生成調度方案。

5 實例驗證

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

表3 車間工件生產任務信息

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

表4 機器上工件組的安裝時間 min

4.1 工件組不可分割加工結果

對于表3所示的14項工件任務，當工件組不可分割加工時，則在排序時將工件組整體作為一個復合工件，按照前面提出的方法，計算各個復合工件的加工時間、權重和調整交期，結果如表5所示。

表5 工件組不可分割加工數據表

運用本文提出的方法進行求解，分別得到工件組安裝時間與排序有關、工件組安裝時間與排序無關兩種情況下的結果，兩種結果的比較如表6所示。

表6 工件組不可分割加工情況下的兩種運算結果比較

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

4.2 工件組可以分割加工結果

當工件組可以分割加工時，需要通過以SWPT為準則的工件組內排序變量賦值，SWEPT為準則的工件組排序變量賦值，首先對工件組進行分割。運行算法發(fā)現，當工件組安裝時間與排序無關時，工件組未進行分割，結果與工件組不可分割加工情況下相同。分析產生這種結果的原因在于工件組安裝時間為固定值，且大于等于工件的加工時間，也就是符合前面提出的成組假設，在這種情況下，工件組通常是不分割加工的。

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

5 結語

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

［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］陳亞絨，管在林，彭運芳，等.面向大規(guī)模定制的瓶頸成組調度啟發(fā)式方法研究［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］王秀利，吳惕華，劉磊.一種求解單機成組作業(yè)優(yōu)化調度的啟發(fā)算法［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］聶黎，高亮，胡譯丹.基于前序基因表達式編程的單機成組調度算法［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，Fox 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.