基于人工神經(jīng)網(wǎng)絡(luò)的作業(yè)車間調(diào)度算法

曹琛祺　金偉祖

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

關(guān)鍵詞：作業(yè)車間；調(diào)度算法；禁忌搜索；人工神經(jīng)網(wǎng)絡(luò)

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：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è)車間調(diào)度問題（Job-shop scheduling Problem，JSP）[1]，是一個(gè)NP 難問題[2]。在作業(yè)車間調(diào)度中，多個(gè)并行執(zhí)行的任務(wù)需要在多個(gè)機(jī)器中調(diào)度執(zhí)行，目標(biāo)是得到一個(gè)可行的最優(yōu)調(diào)度使得最大完工時(shí)間（makespan）最短。

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

人工智能的目標(biāo)是構(gòu)造一種智能機(jī)械，使之能夠?qū)W習(xí)、模仿和展現(xiàn)近乎 于人的智慧。人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network）[10] 便是其中的一種，其作為機(jī)器學(xué)習(xí)的一種重要的工具已被廣泛使用。一個(gè)神經(jīng)網(wǎng)絡(luò)由多層的節(jié)點(diǎn)組成，節(jié)點(diǎn)間用加權(quán)邊相連。連接的權(quán)值代表了連接的強(qiáng)度，其符號則代表了激發(fā)或抑制作用。神經(jīng)網(wǎng)絡(luò)將學(xué)習(xí)的知識以網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)、激活函數(shù)、權(quán)值與偏差值的形式記憶下來。

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

1 問題描述

1.1 定義

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

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

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

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

1.2 JSP的圖表示法

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

2 算法描述

2.1 人工神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)

2.1.1 輸入屬性的選取與轉(zhuǎn)化

考慮到作業(yè)車間調(diào)度問題的特點(diǎn)，參考[13]，工序的以下屬性被提取出來作為神經(jīng)網(wǎng)絡(luò)輸入：工序號、處理時(shí)間、剩余時(shí)間、機(jī)器負(fù)載。同時(shí)，每個(gè)屬性的具體值轉(zhuǎn)化為類別值：

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

處理時(shí)間：每個(gè)工序在機(jī)器上運(yùn)行所需要的時(shí)間。按照運(yùn)行時(shí)間的范圍均勻分為低、中、高3類。

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

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

2.1.2 目標(biāo)輸出的選取與轉(zhuǎn)化

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

2.1.3 神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)

在本文中使用的人工神經(jīng)網(wǎng)絡(luò)的類型是多層感知器（Multilayer Perceptron，MLP）[14]。MLP的結(jié)構(gòu)如圖 2所示，由多層的節(jié)點(diǎn)組成，每層節(jié)點(diǎn)與下一層的所有節(jié)點(diǎn)相連，每個(gè)連接對應(yīng)一個(gè)權(quán)值。輸入層對應(yīng)著作為分類依據(jù)輸入的工序?qū)傩浴Ｓ捎谳斎氚?個(gè)屬性，因此輸入層有4個(gè)節(jié)點(diǎn)。隱層連接著輸入與輸出層，2隱層分別有4個(gè)和3個(gè)節(jié)點(diǎn)。輸出層設(shè)置1個(gè)節(jié)點(diǎn)代表序列的優(yōu)先級。

2.1.4 實(shí)現(xiàn)細(xì)節(jié)

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

在人工神經(jīng)網(wǎng)絡(luò)中，訓(xùn)練算法用于判斷何時(shí)停止訓(xùn)練可以使輸入與輸出的關(guān)系更好的記憶在神經(jīng)網(wǎng)絡(luò)中。本文選用誤差反向傳播（back propagation）算法[15]作為訓(xùn)練算法。該算法的思想是通過輸出與目標(biāo)的誤差得到隱層到輸出層以及輸入層到隱層新的權(quán)值，從而更新網(wǎng)絡(luò)。通過不斷更新來使代價(jià)函數(shù)的返回值變得最小。學(xué)習(xí)率決定了神經(jīng)網(wǎng)絡(luò)在調(diào)整權(quán)值時(shí)的幅度，使用動量記錄上個(gè)世代的調(diào)整幅度，可以進(jìn)一步加快訓(xùn)練的速度。

2.2 人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練

在定義了以上的神經(jīng)網(wǎng)絡(luò)后，面對實(shí)際的作業(yè)車間調(diào)度問題，還需要為其提供訓(xùn)練集，訓(xùn)練后便可用來解決今后的作業(yè)車間問題的實(shí)例。因此本文采用的禁忌搜索作為提供訓(xùn)練集的工具。

2.2.1 禁忌搜索算法

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

2.2.2 停止條件

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

· 總迭代次數(shù)達(dá)到閾值

· 結(jié)果未改進(jìn)的迭代次數(shù)達(dá)到閾值

· 找到最優(yōu)解

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

2.2.3 鄰居集合

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

2.2.4 數(shù)據(jù)的轉(zhuǎn)化

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

2.3 人工神經(jīng)網(wǎng)絡(luò)的運(yùn)行

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

2.4 算法總結(jié)

本文的目標(biāo)是利用人工神經(jīng)網(wǎng)絡(luò)來實(shí)現(xiàn)作業(yè)車間問題的調(diào)度。因此，算法主要分訓(xùn)練與運(yùn)行2大步驟：

1） 訓(xùn)練：

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

b） 將最優(yōu)調(diào)度轉(zhuǎn)換為可供分類的輸入數(shù)據(jù)集和分類輸出數(shù)據(jù)集

c） 將輸入輸出集分為訓(xùn)練集、驗(yàn)證集合測試集

d） 使用數(shù)據(jù)集訓(xùn)練神經(jīng)網(wǎng)絡(luò)、得到調(diào)度器

2） 運(yùn)行

a） 使用調(diào)度器調(diào)度之后所有的問題實(shí)例，得到對應(yīng)的調(diào)度結(jié)果

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

3）實(shí)驗(yàn)

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

2.5 訓(xùn)練的結(jié)果

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

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

2.6 調(diào)度的結(jié)果

表 2與表 3中的結(jié)果，顯示了使用禁忌算法和訓(xùn)練完成的人工神經(jīng)網(wǎng)的比較。從表中可知，雖然使用禁忌搜索算法可以得到很好的結(jié)果，但是對于每個(gè)新的實(shí)例需要更多的運(yùn)行時(shí)間。對更加復(fù)雜的實(shí)例，禁忌算法需要過多的時(shí)間。相比之下，神經(jīng)網(wǎng)絡(luò)可以在幾乎一定的時(shí)間內(nèi)給出一個(gè)有一定質(zhì)量的調(diào)度，主要的時(shí)間花費(fèi)是只有一次的訓(xùn)練過程。

3 總結(jié)與展望

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

參考文獻(xiàn)：

[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.