作業(yè)車間調(diào)度問(wèn)題

（Job-shop Scheduling Problem,簡(jiǎn)稱為JSP）

作為一個(gè)眾所周知的NP難問(wèn)題

是生產(chǎn)制造和流程規(guī)劃環(huán)節(jié)最關(guān)鍵的問(wèn)題之一

在該問(wèn)題中

需要在一組機(jī)器上面完成一組工件的加工

每個(gè)工件的加工包含多道工序

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

每道工序只需要一臺(tái)機(jī)器進(jìn)行加工

在某一時(shí)刻

一臺(tái)機(jī)器只能加工一道工序

主要決策內(nèi)容是對(duì)機(jī)器上的工序進(jìn)行排序

以優(yōu)化指定的性能指標(biāo)

柔性作業(yè)車間調(diào)度問(wèn)題

（Flexible Job-shop Scheduling Problem, 簡(jiǎn)稱為FJSP）

是經(jīng)典JSP的拓展

它與JSP最大的不同 在于

FJSP允許每個(gè)工序在任何一臺(tái)機(jī)器上面進(jìn)行加工

除了需要對(duì)工序進(jìn)行排序外

還需要決策加工該工序的機(jī)器

因此FJSP更加復(fù)雜

本文將為大家簡(jiǎn)單介紹一下FJSP問(wèn)題

以及該問(wèn)題在學(xué)術(shù)文獻(xiàn)中的經(jīng)典算例及其求解結(jié)果

問(wèn)題簡(jiǎn)介

問(wèn)題描述

☆一道工序一旦開(kāi)始加工 就不能中斷

每臺(tái)機(jī)器一次只能加工一道工序

在初始加工時(shí)刻，所有工件和機(jī)器都是可用的

FJSP問(wèn)題有兩個(gè)決策內(nèi)容

（一）是將每道工序分派給可用的機(jī)器上面進(jìn)行加工

（二）是處理每臺(tái)機(jī)器上工件的加工順序，來(lái)優(yōu)化目標(biāo)函數(shù)

一般來(lái)說(shuō)，該問(wèn)題的目標(biāo)是最小化Makespan，通常用L來(lái)表示，即從開(kāi)始加工到所有工件加工完畢總的時(shí)長(zhǎng)。

符號(hào)釋義

舉例

	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表示三個(gè)加工機(jī)器，O(i,j)表示工件i的第j道工序。

一共有3個(gè)工件需要進(jìn)行加工，其中工件1只有一道工序，工件2有兩道工序，工件3需要進(jìn)行三道工序。

工件2的第一道工序不能在M1機(jī)器上進(jìn)行加工，工件3的第三道工序在機(jī)器M3上所需要的加工時(shí)間為9。

經(jīng)典算例&優(yōu)化算法

接下來(lái)本文將會(huì)列舉出柔性車間調(diào)度常用的幾種算例集

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

該部分內(nèi)容依據(jù)相關(guān)參考文獻(xiàn)撰寫(xiě)

Kacem算例集（見(jiàn)參考文獻(xiàn)[1]）

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

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

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

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

Kacem算例的求解結(jié)果

在分析結(jié)果之前，先介紹三個(gè)與結(jié)果相關(guān)的指標(biāo)

Makespan：即從開(kāi)始加工到所有工件加工完畢總的時(shí)間

Maximal machine workload(W_m)：任意機(jī)器上花費(fèi)的最長(zhǎng)加工時(shí)間

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

以上是五種算法的測(cè)試結(jié)果，分別為

經(jīng)典遺傳算法（Genetic Algorithm，GA）(見(jiàn)文獻(xiàn)[1])

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

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

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

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

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

見(jiàn)下表

其中

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

相比之下

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

由此可見(jiàn)，基于群體進(jìn)化的啟發(fā)式算法在處理Kacem算例時(shí)具有很好的效果，并且研究者們也熱衷于將群體進(jìn)化算法和精確解算法或者一些分派規(guī)則進(jìn)行結(jié)合，以達(dá)到更好的搜索效果。

Fadata 算例(見(jiàn)參考文獻(xiàn)[10])

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

這些測(cè)試算例按照規(guī)?？煞譃閮深?，即小型柔性作業(yè)車間調(diào)度問(wèn)題算例（SFJS1-SFJS10）和中大型柔性作業(yè)車間調(diào)度問(wèn)題算例（MFJS1-MFJS10）。

其中，工件的數(shù)量從2到12不等，機(jī)器數(shù)量從2到8不等，每個(gè)工件的工序數(shù)從2到4不等，該算例中所有工件的工序總數(shù)從4到48不等。

Fadata算例的求解結(jié)果

下表列出了Fadata算例在文獻(xiàn)中的結(jié)果

其中算例的規(guī)模2.2.2

表示工件數(shù)量為2  工序數(shù)量為2  機(jī)器數(shù)量為2 的算例

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

因此

下表中啟發(fā)式算法的Makespan表示運(yùn)行多次（一般取10-20次）

搜索得到的最好解

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

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

以下為四種算法的測(cè)試結(jié)果，分別為

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

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

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

人工免疫算法(見(jiàn)文獻(xiàn)[5])。

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

BRdata 算例（見(jiàn)參考文獻(xiàn)[13]）

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

BRdata 算例的求解結(jié)果

  首先介紹幾種簡(jiǎn)單的分派規(guī)則（Dispatching Rule）

  分派規(guī)則就是指按照某種特定的規(guī)則來(lái)決定下一個(gè)將要生產(chǎn)的工件的調(diào)度方法，由于規(guī)則通常較簡(jiǎn)單，操作性強(qiáng)，在調(diào)度中經(jīng)常被使用。

最常見(jiàn)的規(guī)則有

FCFS（First Come First Serve，先到先服務(wù)規(guī)則）

EDD（Earliest Due Data，優(yōu)先完成工期最緊的工件）

RANDOM（隨機(jī)挑選的規(guī)則）

等等

下面是文獻(xiàn)[13]中所用使用的分派規(guī)則

SPT(Shortest Processing Time Rule):優(yōu)先選擇加工時(shí)間最短的工件MWKR(Most Work Remaining Rule)：優(yōu)先選擇余下加工時(shí)間最長(zhǎng)的工件LWRK(Least Work Remaining Rule)：優(yōu)先選擇余下加工時(shí)間最短的工件

該算例同樣少不了用群體啟發(fā)式算法進(jìn)行求解的研究

主要介紹兩種

人工免疫算法和遺傳算法

Hudata算例(見(jiàn)參考文獻(xiàn)[3])

該算例出自Hurink等人的文章

根據(jù)每個(gè)工件可選機(jī)器的平均數(shù)量

該算例的規(guī)模有所不同

工件數(shù)從4到50不等

機(jī)器數(shù)從5到15不等

每個(gè)工件的工序數(shù)從5到15不等

所有工件的工序總數(shù)從20到500不等

Hudata算例的求解結(jié)果

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

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

總結(jié)

（1）從各種算例的規(guī)模來(lái)看，文獻(xiàn)中用來(lái)測(cè)試的算例大多規(guī)模比較小，下表統(tǒng)計(jì)了以上四組算例集中規(guī)模最大的算例，其中，Kacem和Fadata算例集中最大機(jī)器數(shù)量為10，最大工件數(shù)量為15，最大工序數(shù)量為56，規(guī)模相對(duì)較小。

而B(niǎo)Rdata和Hudata算例集規(guī)模雖然大一些，最大算例也僅僅15個(gè)機(jī)器，50個(gè)工件，500道工序。

實(shí)際情況中，工廠在面對(duì)大規(guī)模生產(chǎn)時(shí)，要處理的工件可能成千上萬(wàn)，其工序數(shù)量也會(huì)相當(dāng)巨大，因此處理大規(guī)模生產(chǎn)時(shí)對(duì)算法和運(yùn)行時(shí)間的要求將會(huì)更為苛刻。

（2）從所用算法的角度來(lái)看，精確算法、分派規(guī)則、基于鄰域的啟發(fā)式算法和種群進(jìn)化類的啟發(fā)式算法均有使用。

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

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

隨著研究的深入

越來(lái)越多的文章更傾向于采用混合啟發(fā)式來(lái)求解

通過(guò)在經(jīng)典啟發(fā)式算法的基礎(chǔ)上

依據(jù)問(wèn)題特點(diǎn)

添加一些精確解或分派規(guī)則的思想來(lái)使得算法更加高效

（3）從算法的CPU時(shí)間來(lái)看，如下圖所示：

以Fadata算例集為例，橫軸分別表示Fadata算例集的20規(guī)模不同的算例，縱軸表示CPU運(yùn)行時(shí)間，單位為秒?？梢钥吹剑S著算例規(guī)模的逐漸增大，分支定界算法的CPU時(shí)間呈指數(shù)式增長(zhǎng)，在實(shí)際操作中為防止運(yùn)行時(shí)間過(guò)長(zhǎng)而人為設(shè)置終止時(shí)間為3600秒。而啟發(fā)式算法隨著算例規(guī)模的增大，雖然運(yùn)行時(shí)間也會(huì)增加，但是增長(zhǎng)速度遠(yuǎn)遠(yuǎn)小于分支定界算法。

對(duì)于大規(guī)模問(wèn)題，以上四個(gè)算例集中最大規(guī)模的算例為15個(gè)機(jī)器，50個(gè)工件和500道工序，以Fadata算例來(lái)看，最大規(guī)模的算例為MFJS10，其中機(jī)器個(gè)數(shù)為8，工件個(gè)數(shù)為12，工序數(shù)為4，整合模擬退火算法和整合禁忌搜索算法的運(yùn)行時(shí)間分別為850s和763s，效率較高的人工免疫算法運(yùn)行時(shí)間為30.94s，但考慮到算例規(guī)模并不是很大，因此啟發(fā)式算法在運(yùn)行時(shí)間上表現(xiàn)出的效果也并不理想。在實(shí)際中，企業(yè)面臨的規(guī)模更大，工件的數(shù)目很容易過(guò)千，甚至達(dá)到幾萬(wàn)的級(jí)別。如果使用文獻(xiàn)中的算法去解決企業(yè)實(shí)際問(wèn)題，其求解耗時(shí)會(huì)非常的長(zhǎng)，無(wú)法滿足企業(yè)快速?zèng)Q策的需求。

   綜上所述，精確算法對(duì)于處理小規(guī)模算例，能夠很快得到較好解甚至最優(yōu)解，而啟發(fā)式算法雖然得到的不一定是最優(yōu)解，但卻能較好地處理規(guī)模相對(duì)較大的問(wèn)題，它能夠在較短的時(shí)間內(nèi)得到大規(guī)模問(wèn)題的較好解甚至最優(yōu)解。但是總體來(lái)看，啟發(fā)式算法對(duì)于處理很大規(guī)模的問(wèn)題，效果也并不理想。

參考文獻(xiàn)

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