作業車間調度轉換瓶頸算法可行性研究

收稿日期：2007-11-23；修回日期：2008-03-14

基金項目：國家“973”計劃資助項目( 2004CB318000)

作者簡介：黃志(1976-)，男，河南信陽人，博士，主要研究方向為NP難高效算法、人工智能、計算機圖形學、生物計算、運籌學（huangzhi9@gmail.com）; 胡衛軍(1973-)，男， 湖北天門人，講師，博士研究生，主要研究方向為高效算法、計算機圖形學、人工智能.*

(華中科技大學 計算機學院，武漢 430074)

摘 要：討論了轉換瓶頸(SB)算法在解作業車間調度問題時需要解決的子問題。轉換瓶頸算法是解決作業車間調度最小makespan(完工時間)問題的有效啟發式算法。它是基于反復地解決某些單機調度問題這樣的子問題。然而所解決的單機調度問題的解可能會導致算法最終得不到可行解，即使是單機調度最優解也可能得到不可行解。為此，給出了一個簡單的反例證明了產生不可行解的情況，并對產生不可行解的原因作了詳細分析。該研究有利于對轉換瓶頸技術進行更好的理解和應用。

關鍵詞：作業車間調度; NP-難; 轉換瓶頸

中圖分類號：TP301

文獻標志碼：A

文章編號：1001-3695(2008)10-2932-02

Note on infeasibility problem of shifting bottleneck procedure

for job shop scheduling

HUANG Zhi， HU Wei-jun

(School of Computer Science， Huazhong University of Science Technology， Wuhan 430074， China)

Abstract:This paper discussed the subproblem in job shop scheduling problem solved by shifting bottleneck procedure. Shif-ting bottleneck (SB) algorithm was a prominent algorithm for the minimum makespan problem of job shop scheduling. It was based on solving a series of one-machine scheduling problem. However the solution to the one-machine problem might result in the infeasible solution for the job shop scheduling problem. Even the solution was optimal， infeasibility could still be reached. This paper gave a simple counterexample to illustrate the infeasible case. It analyzed the reason of the infeasibility in details. The research is helpful in understanding and utilizing the shifting bottleneck technique.

Key words：job shop scheduling; NP-hard; shifting bottleneck

求解NP難問題一直是計算機科學技術中的一個瓶頸任務。由于人們找不到求解這類問題的有效完整算法，采用啟發式算法求解成為當今研究的一個熱點。作業加工調度問題(JSSP)不僅是NP難的[1]，還被認為是最難的組合最優化問題之一。已經知道，為解決工業生產、經濟管理和網絡通信等諸多方面的一些問題，需要借助于求解這個問題。優質、快速地求解作業加工調度問題，既有重要的理論意義，又能帶來巨大的經濟效益。

對JSSP這樣的NP難問題，當問題規模增大時，目前沒有任何算法能保證在有效的時間內求出其精確解。隨著應用行業規模的不斷擴大以及其對實時性的迫切要求，研究者們提出了許多有效的啟發式方法對此JSSP進行快速近似求解，包括基于優先指派的算法、轉換瓶頸算法[2]、神經網絡算法、基因算法、禁忌搜索算法[3]、混合式算法[4，5]等。其中，轉換瓶頸算法是一種著名的算法[6]。該方法解JSSP是通過連續有限次地解單機(器)調度這樣的子問題完成的。

1 作業車間調度問題

作業車間調度問題可以描述為: x個工件要在m臺機器上加工，滿足下面的一些約束：a)每個工件在機器上加工的次序給定; b)每臺機器同時只能處理一個工件，一個工件在一臺機器上的處理過程稱為一個工序，工序加工的時間是固定且不可打斷的。要找到使所有工件都完工的時間(makespan)最小的調度。

令N={0，1，… ，n}表示工序集（0和n是開始和結束啞元工序），M為機器集，A為a）中給出的約束工序對的集合，Ek為在機器k上加工的約束工件對，由b）可知這些工序在時間上不能重疊。問題（P）可以形式化地描述如下：min tn

tj-ti≥di， (i，j)∈A，

ti≥0， i∈N，

tj-ti≥di∨ti-tj≥dj， (i，j)∈Ek， k∈M

問題（P）的任一可行解被稱為一個調度。關于對該問題的描述，可以參看文獻[2，7，8]。

問題也可以用分離圖G=(N， A， E)表示。 其中：N是節點集;A為通常的連接邊的集合;E為分離性邊的集合[8]。圖1給出了一個三個工件在三臺機器上加工，共有九個工序的實例。圖中節點對應工序，有向邊對應工件中的工序約束關系，分離邊對應于在相同機器上執行的工序對。邊上的數字是處理時間。

對Ek的一個選擇Sk恰好包含Ek中每對分離邊中的一條。實際上定一個無環的選擇Sk等效于在機器k上對工序進行排序。一個完全的選擇S包含對各臺機器的選擇Sk，k∈M。按分離圖的語言，問題就是找一個使有向圖DS中最長路徑最小的、無環的、完全的選擇S。

2 轉換瓶頸算法

轉換瓶頸算法是由一系列的解決單機排序(調度)問題組成。令M為所有機器集合，M0是排好序的機器集合。轉換瓶頸算法的基本思想如下：在M\\M0機器中選定一臺瓶頸機m，并對它作優化的排序，M0:=M0∪{m}；然后按次序對M0中的每個關鍵機器k的序列再優化，而保持其他序列固定（不變），也就是令M′0:=M0-{k}并解決P(k，M′0)。反復這樣，直到M0=M。其中：P(k，M0)為

min tn

tj –ti ≥di， (i， j)∈∪(Sp: p∈M0)∪A，

ti≥0， i∈N，

tj–ti ≥di∨ti–tj≥dj， (i，j)∈Ek

由于問題P(k，M0)等價于[2]問題P*(k，M0)，而問題P*(k，M0)相對更簡單，算法以解問題P*(k，M0)來替代解問題P(k，M0)。P*(k，M0)的描述如下：min tn

tn-ti≥di+qi，

ti≥ri， i∈N*，

tj-ti≥di∨ti-tj≥dj， (i，j)∈Ek )其中：N*是在機器k上加工的工序集合；ri=L(0，i)，qi=L(i， n) -di。L(i， j)是在圖DT中從節點i到j的最長路徑的長度(T=∪(Sp:p∈M0))。

3 不可行解問題

從形式上看問題P(k， M0) 與P*(k，M0)是不同的，是否它們確實如文獻[2]所說是等價的呢？如果不是等價的，問題P*(k， M0)的解是否可能導致不可行解的產生？問題P*(k， M0)的最優解是否可能導致不可行解的產生？下面通過反例來說明。

如圖2所示，本文給出的實例有兩個工件和三臺機器，共有五個工序。工件1包括工序1、2和3；工件2包括工序4和5。工序1、2、5在機器1上加工；工序3在機器2上加工；工序4在機器3上加工。實有向邊表示了工序之間的工件約束關系，即前一道工序結束后才能開始下一道工序。邊上的數字表示箭頭始端的工序所需的加工時間。

下面用轉換瓶頸方法來解這個實例。既然機器2和3分別只加工一個工序，只需對機器1上加工的工序排序即可。要對瓶頸機(機器1)排序，筆者需解決單機問題P(1， M0)。min t6t6-t3≥10，t3-t2≥10

t2-t1≥10，t6-t5≥100

t5-t4≥100

t0≥0，t1≥0，t2≥0

t3≥0，t4≥0， t5≥0，t6≥0

t1-t3≥10∨t3-t1≥10

t1-t5≥100∨t5-t1≥10

t3-t5≥10∨t5-t3≥10



轉換瓶頸算法中，Adams等人實際不是解決P(1， M0)，而是解決P*(1， M0)問題。min t6t6-t1≥30，t6-t3≥30，t6-t5≥30，

t1≥0，t2≥20， t5≥0，t6≥200

t1-t3≥10∨t3-t1≥10

t1-t5≥100∨t5-t1≥10

t3-t5≥100∨t5-t3≥10



容易看出圖3所示的解是P*(1， M0)問題的最優解。這里t6=200， t1=30， t5=100， t0=0。但是這個最優解是不可行的，因為它會導致回路，如圖4所示。圖4中，工序1、2和3形成了回路(1→2→3→1)，該解是不可行解。

因為問題P*(1， M0)與問題P(1， M0)是不同的。從P(1， M0)的約束條件可以得到P*(1， M0)的約束條件。例如P*(1， M0)中t6-t1≥30，可以從P(1， M0)中的t6-t3≥30，t3-t2≥10和t2-t1≥10推導出。然而可以從P(1， M0)中的條件t3-t2≥10和t2-t1≥10推導出t3- t1≥20，卻不能從P*(1， M0)中的條件推導出t3- t1≥20。t3- t1≥20要求工序3在工序1開始后至少20個單位時間后才能開始。產生環的原因在于由問題P(1， M0)變到P*(1， M0)時，有些條件丟失了。

這個反例證明了即使是問題P*(k， M0)的最優解也可能導致不可行解。問題P(k， M0)與P*(k， M0)是不等價的，由問題P(k， M0)的約束條件得到P*(k， M0)的約束條件時，有些約束條件丟失了。

4 結束語

轉換瓶頸技術是著名的作業車間調度啟發式算法，可是該算法存在可能得到不可行解的缺陷。本文對這方面的缺陷進行了討論，給出了反例分析并證明了轉換瓶頸技術中解決子問題(單機調度問題)時由于丟失了一些約束條件，存在得到不可行解的情況。

參考文獻：

[1]GAREY M R， JOHNSON D S. Computer and intractability: a guide to the theory of NP-completeness[M]. [S.l.]: Freeman Press， 1979.

[2]ADAMS J， BALAS E， ZAWACK D. The shifting bottleneck procedure for job shop scheduling[J]. Management Science， 1988， 34(3): 391-401.

[3]黃志，黃文奇. 一種基于禁忌搜索技術的作業車間調度算法[J]. 小型微型計算機系統， 2006， 27(1):97-100.

[4]HUANG Wen-qi， HUANG Zhi. Algorithm based on taboo search and shifting bottleneck for job shop scheduling[J]. Journal of Computer Science and Technology， 2004， 19(6):776-781.

[5]HUANG Zhi， HUANG Wen-qi. An algorithm based on taboo search and shifting bottleneck for job shop scheduling[C]//Proc of International Conference on Management Science Engineering. Harbin:[s.n.]， 2004: 560-564.

[6]SARAL M，CHATTERJEE A K. On the representation of the one machine sequencing problem in the shifting bottleneck heuristic[J]. European Journal of Operational Research， 2007，182(1):475-479.

[7]CONWAY R N， MAXWELL W L， MILLER L W. Theory of scheduling[M]. [S.l.]: Addison-Wesley Press， 1967.

[8]BALAS E. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm[J]. Operations Research， 1969， 17(6): 941-957.