曹琛祺　金偉祖

摘要：提出了一種解決作業(yè)車間調度問題的算法。使用禁忌搜索算法作為生成訓練集的工具，通過對調度序列進行處理，將調度問題轉化為一個分類問題，從而使用人工神經網絡構建分類器。對于新的調度實例，利用訓練得到的分類器得出優(yōu)先級，再利用優(yōu)先級得到調度序列。并在最后對調度器的實際效果使用測試實例進行了驗證。

關鍵詞：作業(yè)車間；調度算法；禁忌搜索；人工神經網絡

中圖分類號：TP312 文獻標識碼：A 文章編號：1009-3044（2016）30-0204-04

Job-shop Scheduling using Artificial Neural Network

CAO Chen-qi，JIN Wei-zu

（Tongji University， School of Software Engineering， Shanghai 201804， China）

Abstract：Present an algorithm to solve the job-shop scheduling problem. The tabu search algorithm is used as the tool to generate the training set. The scheduling problem is transformed into a classification problem by transforming the scheduling sequence. The artificial neural network is used to construct the classifier. For the new scheduling example， the trained classifier is used to derive the priority， and then the priority is used to obtain the scheduling sequence. Finally， the test results are verified by the test cases.

Key words： job-shop； scheduling algorithm； tabu search； artificial neural network

作業(yè)車間調度問題（Job-shop scheduling Problem，JSP）[1]，是一個NP 難問題[2]。在作業(yè)車間調度中，多個并行執(zhí)行的任務需要在多個機器中調度執(zhí)行，目標是得到一個可行的最優(yōu)調度使得最大完工時間（makespan）最短。

作業(yè)車間調度問題是一個很有名的優(yōu)化問題，已有許多不同算法用于解 決這一問題。如禁忌搜索（Tabu Search）算法 [3]，模擬退火（Simulated Annealing）算法 [4， 5]，神經網絡（Neural Network）算法 [6]，遺傳算法（Genetic Algorithm）[7]，粒子群優(yōu)化（Particle Swarm Optimization）算 法 [8]，蟻群優(yōu)化（Ant Colony Optimization）算法 [9] 等。

人工智能的目標是構造一種智能機械，使之能夠學習、模仿和展現近乎 于人的智慧。人工神經網絡（Artificial Neural Network）[10] 便是其中的一種，其作為機器學習的一種重要的工具已被廣泛使用。一個神經網絡由多層的節(jié)點組成，節(jié)點間用加權邊相連。連接的權值代表了連接的強度，其符號則代表了激發(fā)或抑制作用。神經網絡將學習的知識以網絡內部結構、激活函數、權值與偏差值的形式記憶下來。

本文將使用人工神經網絡來解決作業(yè)車間調度問題。首先，設計一種人工神經網絡，定義輸入與輸出，以及內部結構、激活函數等參數。其次，使用禁忌搜索算法作為一種工具，提供訓練實例，從而進行訓練。最后，利用訓練完成的神經網絡，便可對同種的車間調度問題實例進行快速調度。

1 問題描述

1.1 定義

作業(yè)車間調度問題（JSP）的定義如下：

有一個作業(yè)的集合{Ji}1≤i≤n，其中包括n個作業(yè)，另有一個機器的集合{Mj}1≤j≤m，其中包括m個機器。這n個作業(yè)將會在這m個機器上執(zhí)行。將一個作業(yè)Ji在某個機器Mj上的運行過程定義為工序Oij。在JSP中，Oij對于給定的Ji，它們的順序是固定的，即作業(yè)必須按照給定的順序依次在相應的機器上執(zhí)行。當一道工序Oij在機器Mj上執(zhí)行時，在執(zhí)行時間pij內，工序是不能夠被打斷的，因此JSP屬于非搶占式調度問題。

在這些定義的基礎上一個對于JSP的調度可以定義為一個完工時間的集合{cij}1≤i≤n，1≤j≤m，集合中的元素滿足上文中的所有約束。完成所有工序所需的時間稱定義為最大完工時間L，即集合{cij}中的最大值。

作業(yè)車間調度問題的目標是得到一個有效的調度，使得最L最小。

1.2 JSP的圖表示法

對于JSP的調度可以化為一個析取圖（disjunctive graph）[11]，如圖 1中所示，每個節(jié)點代表一個作業(yè)，節(jié)點0代表所有工序的開始，節(jié)點*代表所有工序的結束。每條合取邊代表同一工作中工序間的先后約束，每條析取邊則連接同一機器上的不同工序。邊的權值取決于邊所連接的工序所需的時間。對于JSP的一個調度，可以視作對于析取邊連接的工序的先后順序的確立。而該調度的完工時間則是析取圖的從起始點到終點最大路徑值。

2 算法描述

2.1 人工神經網絡的設計

2.1.1 輸入屬性的選取與轉化

考慮到作業(yè)車間調度問題的特點，參考[13]，工序的以下屬性被提取出來作為神經網絡輸入：工序號、處理時間、剩余時間、機器負載。同時，每個屬性的具體值轉化為類別值：

工序號：每個工序在所屬工作內的序號，由于工序在工作內的順序是一定的，所以這個序號也是一定的。工序號按照第一、前半、后半、最后被分為4類。

處理時間：每個工序在機器上運行所需要的時間。按照運行時間的范圍均勻分為低、中、高3類。

剩余時間：假設所屬工作剩余的工序都不會被打斷的情況下，所有剩余的工序運行結束所需的時間。即該工作未執(zhí)行的（不包括當前工序的）所有工序的運行時間的和。按照剩余時間的范圍均勻分為低、中、高3類。

機器負載：機器上所有預定執(zhí)行工序的處理時間的總和。按照機器負載的范圍均勻分為低和高2類。

2.1.2 目標輸出的選取與轉化

假設一共有N道工序，那么工序在調度序列中的序號范圍便是[1；N]。直接將此序號作為輸出會導致輸出范圍過于龐大，且對于不同問題也會導致輸出的范圍不同。另外對于作業(yè)車間調度問題來說，最優(yōu)調度并不唯一，這意味著對于一個工序來說，它的序號并不確定。直接使用序號作為輸出會大大增加學習的難度。因此，可將序號的范圍均勻分為多個類別，將類別作為輸出可以很好地解決以上的問題。在本文中，將范圍[1；N]均勻的分為6類，序號的值越小，優(yōu)先級的值也越小，對應優(yōu)先級則越高，分別為優(yōu)先級0，1，2，3，4，5。

2.1.3 神經網絡的結構

在本文中使用的人工神經網絡的類型是多層感知器（Multilayer Perceptron，MLP）[14]。MLP的結構如圖 2所示，由多層的節(jié)點組成，每層節(jié)點與下一層的所有節(jié)點相連，每個連接對應一個權值。輸入層對應著作為分類依據輸入的工序屬性。由于輸入包括4個屬性，因此輸入層有4個節(jié)點。隱層連接著輸入與輸出層，2隱層分別有4個和3個節(jié)點。輸出層設置1個節(jié)點代表序列的優(yōu)先級。

2.1.4 實現細節(jié)

使用交叉驗證可以有效地防止過度訓練（over training）的發(fā)生。使用交叉驗證時，將訓練數據分為訓練集（training set），驗證集（validation set）和測試集（test set）。在訓練的過程中，只使用訓練集作為神經網絡的輸入，同時使用無關的驗證集來驗證網絡的正確性。如果訓練的網絡在訓練集中連續(xù)多個世代（epoch）的代價都沒有降低，則停止訓練。這樣，得到的模型變不會是對于特定訓練集特化的模型，而是可以用來判斷所有輸入的泛用模型。禁忌搜索算法每次的輸出的調度結果是不同的，因此通過多次運行可以得到足夠多的訓練集，訓練集、驗證集和測試集分別分配70%、15%和15%的數據。

在人工神經網絡中，訓練算法用于判斷何時停止訓練可以使輸入與輸出的關系更好的記憶在神經網絡中。本文選用誤差反向傳播（back propagation）算法[15]作為訓練算法。該算法的思想是通過輸出與目標的誤差得到隱層到輸出層以及輸入層到隱層新的權值，從而更新網絡。通過不斷更新來使代價函數的返回值變得最小。學習率決定了神經網絡在調整權值時的幅度，使用動量記錄上個世代的調整幅度，可以進一步加快訓練的速度。

2.2 人工神經網絡的訓練

在定義了以上的神經網絡后，面對實際的作業(yè)車間調度問題，還需要為其提供訓練集，訓練后便可用來解決今后的作業(yè)車間問題的實例。因此本文采用的禁忌搜索作為提供訓練集的工具。

2.2.1 禁忌搜索算法

禁忌搜索算法[12]是一種局部搜索算法。局部搜索算法的搜索過程從一個可能的解決方案開始，得到其鄰居集合，并從中搜索得到一個更好的解決方案，并迭代地執(zhí)行這一步驟，直至達到停止的條件，搜索完成。局部搜索算法的一個缺點是很容易停留在局部最優(yōu)解而無法搜索到全局最優(yōu)解。為了解決這一問題，禁忌搜索引入了禁忌列表（Tabu List）這一結構。禁忌列表中存儲了最近迭代中的局部最優(yōu)解，通過將這些解設為禁忌的方式，避免搜索再次訪問局部最優(yōu)解。

2.2.2 停止條件

禁忌搜索在滿足以下任意停止條件后便結束搜索，返回目前搜索到的最優(yōu)解。

· 總迭代次數達到閾值

· 結果未改進的迭代次數達到閾值

· 找到最優(yōu)解

在本文中禁忌搜索只是作為生成最優(yōu)解的工具，因此由于超過閾值而沒有得到最優(yōu)解的情況只要簡單忽略此次結果便可。

2.2.3 鄰居集合

從2.2節(jié)中可知，車間作業(yè)調度可化為一個析取圖，一個調度的完工時間取決于其中的最長路徑值。由于不在最長路徑上的工序的順序并不影響完工時間，因此對于一個給定的解決方案，可以通過改變其最長路徑中工序的前后順序來得到鄰居集合。

2.2.4 數據的轉化

從禁忌搜索算法中得到是一個工序調度序列，并不能直接作為神經網絡的輸入使用。神經網絡最后將對輸入的每個工序進行分類，因此需要計算出工序的4個屬性值，同時將每個工序的在序列中的位置轉化為優(yōu)先級并作為目標輸出，這樣調度序列便轉化為分類問題。

2.3 人工神經網絡的運行

在得到了訓練集并進行訓練后，便可將新的作業(yè)車間調度問題實例轉化為屬性輸入集，并將其輸入訓練完的神經網絡中，從而分類得到相應的優(yōu)先級。將工序先按照所要運行的機器分配至對應機器，并按照工作內的工序號和優(yōu)先級升序排列，這樣便能得到一個可行的調度，將此作為最終的調度結果。

2.4 算法總結

本文的目標是利用人工神經網絡來實現作業(yè)車間問題的調度。因此，算法主要分訓練與運行2大步驟：

1） 訓練：

a） 獲得最優(yōu)調度

b） 將最優(yōu)調度轉換為可供分類的輸入數據集和分類輸出數據集

c） 將輸入輸出集分為訓練集、驗證集合測試集

d） 使用數據集訓練神經網絡、得到調度器

2） 運行

a） 使用調度器調度之后所有的問題實例，得到對應的調度結果

對于一個作業(yè)車間調度問題，首先利用禁忌搜索算法提供訓練集，訓練神經網絡。之后，對于同一類型的問題便可以直接利用神經網絡分類工序，從而得到調度。這樣的好處是利用神經網絡可以大大節(jié)省調度所需的時間，而且作為花費最多時間的訓練步驟，只需要運行一次。下面的實驗證明了本文的觀點。

3）實驗

實驗均在Think Server RD430上完成，操作系統(tǒng)Red Hat Enterprise Linux Server release 6.3 （Santiago），CPU型號Intel（R） Xeon（R） CPU E5-2420，1.90GHz，個數2，內存16G。

2.5 訓練的結果

對于轉化后的作業(yè)車間調度問題的訓練結果可以從表1中的混淆矩陣（confusion table）中看出，此表將Fisher和Thompson（1963）設計的ft06例子作為輸入，ft06中有6個工作，6個機器?；煜仃囷@示了神經網絡實際值與目標值的分布情況，對角線上的數據顯示了正確分類的情況，底部的正確率反映了每個優(yōu)先級各自的正確率以及總體的正確率。

有兩個主要的錯誤的來源。一是由于不唯一的最優(yōu)解造成的。不同的最優(yōu)解導致同一類型的工序可以被分為不同的優(yōu)先級類別，將導致工序被錯誤的分類。另一個可能的原因是在將輸入工序轉化為分類屬性時損失了部分的信息，從而導致分類不完善。

2.6 調度的結果

表 2與表 3中的結果，顯示了使用禁忌算法和訓練完成的人工神經網的比較。從表中可知，雖然使用禁忌搜索算法可以得到很好的結果，但是對于每個新的實例需要更多的運行時間。對更加復雜的實例，禁忌算法需要過多的時間。相比之下，神經網絡可以在幾乎一定的時間內給出一個有一定質量的調度，主要的時間花費是只有一次的訓練過程。

3 總結與展望

本文使用禁忌算法生成訓練集，通過訓練一個人工神經網絡的方法，對于作業(yè)車間調度算法給出了一個可行的調度器。從而使用一種人工智能的方式給出了一個NP難問題的解決方案。在保證調度結果質量的同時保證了較短的運行時間。當然仍有可以改進的空間，如可以通過對于網絡的進一步改進，提高訓練的速度與正確性，同時提升結果的調度質量。

參考文獻：

[1]Bazewicz J， Al E. Scheduling Computer and Manufacturing Processes[J]. Journal of the Operational Research Society， 1997， 48（6）：659-659.

[2]A. S. Jain， S. Meeran. Job-Shop Scheduling Using Neural Networks[J]. International Journal of Production Research， 1998， 36（5）：1249-1272.

[3]Dauzere-Peres S， Paulli J. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search[J]. Annals of Operations Research， 1997， 70（1）：281-306.

[4]K. Steinh?fel， Albrecht A， C.K. Wong. Two simulated annealing-based heuristics for the job shop scheduling problem[J]. European Journal of Operational Research， 1999， 118（3）：524-548.

[5]Matsuo H， Suh C J， Sullivan R S. A Controlled Search Simulated Annealing Method for the General Job-Shop Scheduling Problem[J]. 1988.

[6]Geneste L， Garbot B. Implicit versus explicit knowledge representation in a job-shop scheduling decision support system[J]. International Journal of Expert Systems， 1997， 10（1）：37-52.

[7]Bierwirth C， Mattfeld D C. Production scheduling and rescheduling with genetic algorithms[J]. Evolutionary Computation， 1999， 7（1）：1-17.

[8]Lian Z， Gu X， Jiao B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Chaos Solitons & Fractals， 2006， 183（35）：851-861.

[9]Tahar D N， Yalaoui F， Amodeo L， et al. An ant colony system minimizing total tardiness for hybrid job shop scheduling problem with sequence dependent setup times and release dates[C] 2005.

[10]Zurada B J M. Introduction to Aitifcial Neural Systems[J]. 2012.

[11] Jacek Blazewicz， Erwin Pesch， Malgorzata Sterna. The disjunctive graph machine representation of the job shop scheduling problem[J]. European Journal of Operational Research， 2000， 127（2）：317-331.

[12]Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computer Operations Research， 1986， 13（5）：533-549.

[13]Weckman G R， Ganduri C V， Koonce D A. A neural network job-shop scheduler[J]. Journal of Intelligent Manufacturing， 2008，19（2）：191-201.

[14]Rosenblatt F. Principles of Neurodynamics： Perceptrons and the Theory of Brain Mechanisms[J]. Archives of General Psychiatry， 1962（3）：218-219.

[15]Rumelhart D E， Hinton G E， Williams R J. Learning representations by back-propagating errors[M]. Neurocomputing： foundations of research. MIT Press，1986：533-536.