• 发文
  • 评论
  • 微博
  • 空间
  • 微信

混合算法(GA+TS)求解作业车间调度问题(JSP)-禁忌搜索部分

程序猿声2020-08-09 11:46发文

程序猿声代码黑科技的分享区

大家好,在上一篇文章中,我们介绍了FJSP问题以及HA算法的GA部分。这一篇文章主要介绍嵌套在其中的Tabu Search部分。

种群进化+邻域搜索的混合算法(GA+TS)求解作业车间调度问题(JSP)-算法介绍


Tabu部分原论文没有很详细的描述,因此很多内容是小编收集各方资料,查阅其他相关文献总结出的结论,小编自己编写了三个tabu search,在这里分别分享介绍一下。如有专门研究这块的同学,欢迎随时指点交流!
代码会在下一期统一给出,请关注我们!
Tabu1-基于编码
在之前的文章中说过,算法对每一代子代的每一个个体,都需要decode成可行解,然后运用禁忌搜索优化解,再编码回GA编码,进入下一代。可想而知,如果tabu写的不好,算法的耗时肯定会很高。
论文中的tabu其实是以第二种为主体的。基于编码的tabu相对而言比较盲目,当初编写时也是基于试一试的心态。
前文提到,对一串合法的OS序列,无论进行怎样的交换、插入运算,都可以解码成可行解;对MS序列,在同一工件范围内任意交换顺序,也可以保证得到可行解。
因此,小编在代码中简单设计了两种邻域:1. 对相邻的OS编码进行交换操作;2. 对MS编码的每个位置分别采用GA中的变异操作。
swap很简单,再重复一下MS的变异:
随机选择MS中一半的数字,随机换为对应操作可以选择的某个机器。例如图中长度为6的MS String,随机选择三个位置,对O11而言,共有三个机器可选择,则随机选择1,2,3中一个数字替换掉原先的2。
邻域部分代码(开启了一个50%的采样):
for (int i = 0; i < chromosome.gene_OS.length - 1; i += 2)
for (int j = i + 1; j < chromosome.gene_OS.length; j += 2)
 if(r.nextDouble() < 0.5)
  OSs.add(swap(chromosome.gene_OS, i, j));
for (int i = 0; i < chromosome.gene_MS.length; i++)
if(r.nextDouble() < 0.5){
 int[] MS = chromosome.gene_MS.clone();
 MSs.add(chromOps.machineSeqMutation(MS));
}
结论:这个邻域设计的比较随意,但经过小编的测试后发现效果不佳,小编在这里建议大家不要使用基于编码的邻域搜索。
Tabu2-基于析取图的k-insertion
析取图
对JSP和FJSP来说,除了用甘特图表示解意外,还有一个很重要的表示解的结构:析取图。


析取图是一张有向图。图中的点表示工序,边代表工序加工的顺序。
边有两种类型,一种是machine arc(也叫disjunctive arc),由同一机器上的前一道工序指向相邻的后一道工序。图中彩线部分表示machine arc。另一种是job arc(也叫conjunction arc),由同一工件上的前一道工序指向相邻的后一道工序。图中黑色实现部分代表job arc。两种边分别表示machine 和job的两个约束,因此一个点最多引申出4条边。
除此之外,图中还有两个超级源点,起始点和终止点(图中的0号start和10号finish)。他们是虚拟的点,代表加工开始和结束。Start点只有job arc,分别连向每个工件的第一道工序;Finish 点也只有job arc,从每个工件的最后一道工序连接到此点。(要注意边的顺序!)
图中的边上没有权值,权值存放在点上,代表加工时间。起始、终止点加工时间为0。
读到这里大家应该能感受到,一幅图实际上已经代表了一个解。点(即工序)的加工开始、结束时间都可以通过最长路算法得出。整个schedule的最大makespan(加工时间)就是起始点到终止点的最长路距离。如果这幅图里没有环,则解可行;否则为不可行解。
这里的最长路又称为critical path(关键路径),即图中粉色框框起的部分。
最长路的算法小编没有找到很好的资料,自以为可以用DFS写,如果在邻域算子后要进行全部工件starting time的更新,那么可以使用bellman-ford算法,这些在小编的代码里都有实现。
结论:很多JSP、FJSP论文的tabu search都是基于析取图进行的,因为可以使用图的特性,毕竟容易操作。
k-insertion
相较于JSP,小编能查到的FJSP的邻域较少,这一部分主要参考一篇2000年的论文 “Effective neighbourhood functions for the fexible job shop problem”,讲解其中的k-insertion邻域。
k-insertion其实就是一个insert操作,简单来说就是将critical path中的每一个操作,分别插入到其他可加工机器的某个位置,形成新解。这里强调,无论什么邻域搜索,一定要在critical path上做文章,才容易改变解的makespan。
实际上,并不是一个机器上的所有位置都需要插入的。如果一道工序由于job边约束,加工时间在考前的位置,那么插入某台机器靠后的位置显然不会使加工时间缩短。考虑到这一点,我们只需要挑出可能使结果更优的位置,执行插入操作。


论文中对每个机器上的工序根据starting time(开始加工的时间)进行排序,然后根据公式计算出两个边界:L_k, R_k。再通过二分查找找到这两个位置。经过证明,只有两者的并集(图中中间的部分)插入后可能优化结果。这里的计算公式需要定义一些新变量,难度不大但是不好讲清,想要深入研究的同学可以下载代码、论文进一步研究,这里暂时不多说了。
前面我们反复强调,我们的tabu是要嵌入到每一个个体中的,因此计算速度一定要快。如果对TS的每一个解都精确运算出makespan,速度会很慢(第一个tabu就是这样的)。因此,我们需要特殊的估值方法。
论文中的估值是一个上界。只需要根据前文定义的一些变量进行简单的加减乘除运算即可得出,极大优化了时间复杂度。这里同样不多解释。
然而,在实现析取图的k-insertion后,小编发现自己实现的速度依旧很慢,嵌入个体后算法根本跑不动。因此小编尝试了一下GA和TS的并行操作,用GA的初始解进行TS操作,发现结果却是有优化,但是时间还是太久。小编目前也找不到代码资料,只能自行编写,因此陷入瓶颈。有了解这块的同学可以和小编进一步交流!
这里再提一句,JSP、FJSP的tabu禁忌表可以用插入或交换前后的的位置,制作一个二维表来表示,用单纯的解作为禁忌对象会拖慢速度。
结论:Tabu2效果不错,但是可能是因为析取图部分没有写好,时间容易爆炸。
Tabu3-基于甘特图的JSP N1邻域
前面的tabu2是一种FJSP的邻域结构,搜索的是插入不同机器的解空间。如果不插入不同机器呢?
很显然,问题转化为JSP。
因此,小编在咨询了一些专业人士后,打算尝试加入JSP的tabu search。


JSP的tabu邻域比FJSP多一些,比较知名的有N1,N4,N5,N6等邻域(参考:A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem)。小编目前简单实现了N1的邻域,通过类似甘特图的形式作为解的结构。
在介绍N1之前还要提到一个critical block的概念。在critical path中,如果有若干个连续的工序是在同一机器上加工的,则称其为一个critical block。很多tabu邻域都是在critical block内进行操作,包括这里说的N1。
N1的邻域为:在所有critical block内,交换两个相邻工序在机器上的加工位置。
由于甘特图的形式表示解没有图的性质,因此计算makespan、更新starting time的方法和析取图中又有所不同。简单来说,需要像GA中查找空闲时间区间一样不断插入,然后更新时间。
简单实现后说下小编实现+测试后的结论:时间上勉强可以接受,不至于跑不出来;但是解的质量不够理想。但至少说明嵌入个体是可行的。
这里提供一个进一步改进的思路:将第三部分的JSP的tabu邻域和第二部分的k-insertion结合起来,因为我做第三部分的时候没有写成析取图,所以这部分没有做。结合之后还要将第二部分进一步改进,至少时间上要缩短,再嵌入到个体中。
Tabu部分大致就介绍到这里,剩下还会有一篇具体讲解小编实现的代码。讲解有些地方不够详细,要具体研究的小伙伴还是推荐好好研读论文。
参考
[1]Li, Xinyu , and L. Gao . "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem." International Journal of Production Economics 174.Apr.(2016):93-110.
[2]Zhang, Chao Yong , P. G. Li , and Y. R. Zailin Guan . "A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem." Computers & Operations Research 34.11(2007):3229-3242.
[3]Mastrolilli, Monaldo , and L. M. Gambardella . "Effective Neighbourhood Functions for the Flexible Job Shop Problem." Journal of Scheduling 3.1(2015):3-20.
[4]Zhang, Guohui , L. Gao , and Y. Shi . "An effective genetic algorithm for the flexible job-shop scheduling problem." Expert Systems with Applications 38.4(2011):3563-3573.

声明:本文为OFweek维科号作者发布,不代表OFweek维科号立场。如有侵权或其他问题,请及时联系我们举报。
2
评论

评论

    相关阅读

      暂无数据

      程序猿声

      编程爱好者的聚居地,代码黑科技的...

      举报文章问题

      ×
      • 营销广告
      • 重复、旧闻
      • 格式问题
      • 低俗
      • 标题夸张
      • 与事实不符
      • 疑似抄袭
      • 我有话要说
      确定取消

      举报评论问题

      ×
      • 淫秽色情
      • 营销广告
      • 恶意攻击谩骂
      • 我要吐槽
      确定取消

      用户登录×

      请输入用户名/手机/邮箱

      请输入密码