作業車間調度問題

（Job-shop Scheduling Problem,簡稱為JSP）

作為一個眾所周知的NP難問題

是生產制造和流程規劃環節最關鍵的問題之一

在該問題中

需要在一組機器上面完成一組工件的加工

每個工件的加工包含多道工序

工序之間需滿足一定的順序約束

每道工序只需要一臺機器進行加工

在某一時刻

一臺機器只能加工一道工序

主要決策內容是對機器上的工序進行排序

以優化指定的性能指標

柔性作業車間調度問題

（Flexible Job-shop Scheduling Problem, 簡稱為FJSP）

是經典JSP的拓展

它與JSP最大的不同 在于

FJSP允許每個工序在任何一臺機器上面進行加工

除了需要對工序進行排序外

還需要決策加工該工序的機器

因此FJSP更加復雜

本文將為大家簡單介紹一下FJSP問題

以及該問題在學術文獻中的經典算例及其求解結果

問題簡介

問題描述

☆一道工序一旦開始加工 就不能中斷

每臺機器一次只能加工一道工序

在初始加工時刻，所有工件和機器都是可用的

FJSP問題有兩個決策內容

（一）是將每道工序分派給可用的機器上面進行加工

（二）是處理每臺機器上工件的加工順序，來優化目標函數

一般來說，該問題的目標是最小化Makespan，通常用L來表示，即從開始加工到所有工件加工完畢總的時長。

符號釋義

舉例

	M1	M2	M3
O（1，1）	8	8	4
O（2，1）		7	3
O（2，2）	3	6	9
O（3，1）	6	3	2
O（3，2）		6	1
O（3，3）		2	9

在上表中M1- M3表示三個加工機器，O(i,j)表示工件i的第j道工序。

一共有3個工件需要進行加工，其中工件1只有一道工序，工件2有兩道工序，工件3需要進行三道工序。

工件2的第一道工序不能在M1機器上進行加工，工件3的第三道工序在機器M3上所需要的加工時間為9。

經典算例&優化算法

接下來本文將會列舉出柔性車間調度常用的幾種算例集

并列出各算例集目前最好或者較好的結果及算法

該部分內容依據相關參考文獻撰寫

Kacem算例集（見參考文獻[1]）

該算例集源自Imed Kacem的文章，由三個不同規模的算例組成，即8X8，10X10，15X10（即15個工件，10個加工機器）。

8X8規模的算例是一個部分柔性的算例，它包含8個工件，8個機器和27個加工工序。所謂部分柔性是指某些工件不能在特定的機器上進行加工，在算例中符號“X”代表不能加工的工件和工序，在實際的處理中，通常會將“X”設為較大的值，通過這種方法可以將部分柔性的算例轉化為完全柔性的算例。

10X10規模的算例是完全柔性的算例，它包含10個工件，10個機器和30個加工工序。完全柔性是指所有的工件及其任意工序都能在任何機器上進行加工。

15X10規模的算例同樣是完全柔性的算例，它包含15個工件，10個機器和56個加工工序。

Kacem算例的求解結果

在分析結果之前，先介紹三個與結果相關的指標

Makespan：即從開始加工到所有工件加工完畢總的時間

Maximal machine workload(W_m)：任意機器上花費的最長加工時間

Total workload (W_T)：所有機器上總的加工時間

以上是五種算法的測試結果，分別為

經典遺傳算法（Genetic Algorithm，GA）(見文獻[1])

局部化+控制遺傳算法（Approach by Localization+Controlled Genetic Algorithm, AL+CGA）(見文獻[1])

粒子群+模擬退火算法（Particle Swarm Optimization+Simulated Annealing,PSO+SA）(見文獻[9])

混合遺傳算法（hybrid Genetic Algorithm, hGA）(見文獻[12])

人工免疫算法（Artificial Immune Algorithm,AIA）(見文獻[5])

其中“*”表示文章中并未給出該指標的相關信息。只有混合遺傳算法(hGA)和人工免疫算法(AIA)給出了相關計算的CPU時間

見下表

其中

混合遺傳算法在8X8,10X10,15X10算例上種群規模取值分別為300，300，500，所用的CPU時間為22.4s ,43.1s ,112.2s。

相比之下

人工免疫算法在種群規模增大的情況下，CPU時間在8X8和10X1算例上遠遠小于混合遺傳算法，分別只需要0.76s和8.97s就能找到較好的解，在大規模算例（15X10）上所用的時間相差不大。

由此可見，基于群體進化的啟發式算法在處理Kacem算例時具有很好的效果，并且研究者們也熱衷于將群體進化算法和精確解算法或者一些分派規則進行結合，以達到更好的搜索效果。

Fadata 算例(見參考文獻[10])

Fadata算例集出自Fattahi等人的文章中。

這些測試算例按照規模可分為兩類，即小型柔性作業車間調度問題算例（SFJS1-SFJS10）和中大型柔性作業車間調度問題算例（MFJS1-MFJS10）。

其中，工件的數量從2到12不等，機器數量從2到8不等，每個工件的工序數從2到4不等，該算例中所有工件的工序總數從4到48不等。

Fadata算例的求解結果

下表列出了Fadata算例在文獻中的結果

其中算例的規模2.2.2

表示工件數量為2  工序數量為2  機器數量為2 的算例

由于用啟發式算法每次搜索到的最終解可能存在差異性

因此

下表中啟發式算法的Makespan表示運行多次（一般取10-20次）

搜索得到的最好解

令n表示算法運行的次數，集合N={L₁,L₂,...,L_n}表示每次運行結果的集合，則下表中啟發式算法的Makespan=min{L₁,L₂,...,L_n}。

偏差（P）則表示每次運行結果與最小值Makespan 之間差距的平均值，即：

以下為四種算法的測試結果，分別為

分支定界算法（Branch and Bound）(見文獻[10])

整合模擬退火算法（Integrated Approach with Simulated Annealing，ISA）(見文獻[10])

整合禁忌搜索算法（Integrated Approach with Tabu Search，ITS）(見文獻[10])

人工免疫算法(見文獻[5])。

注：在分支定界算法求解MFJS1大規模問題時，（396，470）其中396表示目標函數的下界，470則表示規定時間內(3600s)求到的上界，即最好可行解的目標函數的值。

BRdata 算例（見參考文獻[13]）

 該算例集出自Brandimarte的文章，由MK01-MK10總共10個測試算例組成，這些算例都是給定取值范圍使用均勻分布隨機生成。工件數從10到20不等，機器數從4到15不等，每個工件的工序數從5到15不等，所有工件的工序總數從55到240不等。

BRdata 算例的求解結果

  首先介紹幾種簡單的分派規則（Dispatching Rule）

  分派規則就是指按照某種特定的規則來決定下一個將要生產的工件的調度方法，由于規則通常較簡單，操作性強，在調度中經常被使用。

最常見的規則有

FCFS（First Come First Serve，先到先服務規則）

EDD（Earliest Due Data，優先完成工期最緊的工件）

RANDOM（隨機挑選的規則）

等等

下面是文獻[13]中所用使用的分派規則

SPT(Shortest Processing Time Rule):優先選擇加工時間最短的工件MWKR(Most Work Remaining Rule)：優先選擇余下加工時間最長的工件LWRK(Least Work Remaining Rule)：優先選擇余下加工時間最短的工件

該算例同樣少不了用群體啟發式算法進行求解的研究

主要介紹兩種

人工免疫算法和遺傳算法

Hudata算例(見參考文獻[3])

該算例出自Hurink等人的文章

根據每個工件可選機器的平均數量

該算例的規模有所不同

工件數從4到50不等

機器數從5到15不等

每個工件的工序數從5到15不等

所有工件的工序總數從20到500不等

Hudata算例的求解結果

SB(Shifting Bottleneck[2])：瓶頸移動法

主要思路是通過不斷識別機器集合中的瓶頸機器，并將該機器上的工件重新排序的方法。

總結

（1）從各種算例的規模來看，文獻中用來測試的算例大多規模比較小，下表統計了以上四組算例集中規模最大的算例，其中，Kacem和Fadata算例集中最大機器數量為10，最大工件數量為15，最大工序數量為56，規模相對較小。

而BRdata和Hudata算例集規模雖然大一些，最大算例也僅僅15個機器，50個工件，500道工序。

實際情況中，工廠在面對大規模生產時，要處理的工件可能成千上萬，其工序數量也會相當巨大，因此處理大規模生產時對算法和運行時間的要求將會更為苛刻。

（2）從所用算法的角度來看，精確算法、分派規則、基于鄰域的啟發式算法和種群進化類的啟發式算法均有使用。

其中在參考的13篇文獻中，基于精確算法和分派規則的文章只有3篇，而基于鄰域搜索的啟發式算法有4篇，余下6篇均為種群進化算法。

鄰域搜索算法中用的最多的是禁忌搜索算法，而種群進化算法則以遺傳算法為主。

隨著研究的深入

越來越多的文章更傾向于采用混合啟發式來求解

通過在經典啟發式算法的基礎上

依據問題特點

添加一些精確解或分派規則的思想來使得算法更加高效

（3）從算法的CPU時間來看，如下圖所示：

以Fadata算例集為例，橫軸分別表示Fadata算例集的20規模不同的算例，縱軸表示CPU運行時間，單位為秒。可以看到，隨著算例規模的逐漸增大，分支定界算法的CPU時間呈指數式增長，在實際操作中為防止運行時間過長而人為設置終止時間為3600秒。而啟發式算法隨著算例規模的增大，雖然運行時間也會增加，但是增長速度遠遠小于分支定界算法。

對于大規模問題，以上四個算例集中最大規模的算例為15個機器，50個工件和500道工序，以Fadata算例來看，最大規模的算例為MFJS10，其中機器個數為8，工件個數為12，工序數為4，整合模擬退火算法和整合禁忌搜索算法的運行時間分別為850s和763s，效率較高的人工免疫算法運行時間為30.94s，但考慮到算例規模并不是很大，因此啟發式算法在運行時間上表現出的效果也并不理想。在實際中，企業面臨的規模更大，工件的數目很容易過千，甚至達到幾萬的級別。如果使用文獻中的算法去解決企業實際問題，其求解耗時會非常的長，無法滿足企業快速決策的需求。

   綜上所述，精確算法對于處理小規模算例，能夠很快得到較好解甚至最優解，而啟發式算法雖然得到的不一定是最優解，但卻能較好地處理規模相對較大的問題，它能夠在較短的時間內得到大規模問題的較好解甚至最優解。但是總體來看，啟發式算法對于處理很大規模的問題，效果也并不理想。

參考文獻

[1].Imed Kacem, Slim Hammadi, Pierre Borne, 2002. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part C.32,1-13.

[2].Joseph Adams, Egon Balas, Daniel Zawack, 1988. The shifting bottleneck procedure for job shop scheduling.Management Science. 34,391-401.

[3].Johann Hurink, Bernd Jurisch, Monika Thole, 1994. Tabu search for the job-shop scheduling problem with multi-purpose machines.OR Spektrum. 15,205-215.

[4].Wang Shuangxi, Zhang Chaoyong, Jin Liangliang, 2014. A hybrid genetic algorithm for flexible job-shop scheduling problem.Advanced Materials Research.889,1179-1184.

[5].A.Bagheri, M.Zandiehb, Iraj Mahdavi, M.YazdaniAn, 2010. An artificial immune algorithm for the flexible job-shop scheduling problem.Future Generation Computer Systems. 26,533-541.

[6].Zhang Guohui, Gao Liang, Shi Yang, 2011. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications .38,3563-3573.

[7].Li Junqing, Pan Quanke, Liang YunChia, 2010. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering .59, 647-662.

[8].M. Yazdani, M. Amiri, M. Zandieh, 2010. Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Systems with Applications.37,678-687.

[9].Xia Weijun, Wu Zhiming, 2005. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering.48, 409-425.

[10].Parviz Fattahi, Mohammad Saidi Mehrabad, Fariborz Jolai, 2007. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf .18,331-342.

[11].F. Pezzellaa, G. Morganti, G. Ciaschetti, 2008. A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research. 35, 3202-3212.

[12].Jie Gao, Linyan Sun, Mitsuo Gen, 2007. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research. 35, 2892-2907.

[13].P. Brandimarte, 1993. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research.41, 157-183.