柔性作业车间调度问题（Flexible Job-shop Scheduling Problem, 简称为FJSP）

作业车间调度问题

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