作业车间调度问题该如何解决？种群进化+邻域搜索的混合算法
表a代表算例。
算例中有三个工件需要加工，每个工件分别有两道工序（不同工件加工工序不一定一样多）。除了J3的工序T2（task）外，所有工序都可以在三台机器上加工，对应的加工时间如表a所示。
表b的OS String和MS String代表染色体编码。
OS String中有N个数字（N代表总工序数），每一位数字代表一道工序对应的工件。简单的说，在decode的过程中，优先安排靠左的工件到对应机器上。同一数字出现的次数代表工件的第k道工序，例如第一个“1”代表O11，也就是J1T1。第二个“3”代表O31，J3T1。第三个“1”代表O12，J1T2。
MS String中也有N个数字，代表每个工件选择的机器。MS的顺序按照工件顺序排列，如图，J1、J2、J3都有2道工序，那么第一位数字“2”则代表O11，J1T1，需要安排在第二个可以加工的机器上。注意这里的数字不代表机器序号，代表的是可加工的机器。例如最后一位数字“2”，代表的不是machine2，因为J3T3无法在machine2上加工；它代表的是J3T3第二个可加工的机器，也就是machine3。
表c用甘特图表示了表b中编码解码出的一个可行解。
最基本的思路是按照OS的顺序，在甘特图中一个接一个填入工序。但这样做后你会发现，O22本应该出现在O12后面（在OS中第二个2出现在第二个1后面），但它却跑到了O12前面；但是，图中的解确实可行，而且优于我们之前的做法。这就涉及一个查找的过程，是decode中的一个优化。
这里介绍一下如何优化decode。首先，我们设定 （allowing starting time），代表Oij的在工序约束（必须在同一工件上一道工序结束后才能开始加工）下的最早允许开始时间；代表Oij的结束时间。则我们得到公式。
从第一道工序开始按OS的顺序，安排工序Oij：
计算检查工序所在加工机器中的所有空闲时间区间。例如对O22而言，其所在加工机器M1中的空闲时间区间有一个：。，则设置当前工序Oij的开始时间。其中表示Oij在机器k上加工的时间。否则，检查下一个空闲时间区间。若所有区间都不满足，放置机器最后。设置工序加工结束时间。
编码的过程则比较简单。MS编码自不用说，按顺序把机器需要排列好就行；OS编码论文中没提编码方法，小编觉得可以对所有工序直接按照starting time排序，再按规则填入数字即可。简单试验后发现，对一串染色体进行这样的解码编码后得到的染色体与原本的染色体是相同的。
除了编码解码外，其他交叉、变异、选择部分与一般的GA算法没有太大差别。对一串合法的OS序列，无论进行怎样的交换、插入运算，都可以解码成可行解。对MS序列，在同一工件范围内任意交换顺序，也可以保证得到可行解。所以后续处理相对常规。
分享
图片新闻
最新活动更多
-
5月8-10日立即报名>> 国际物流解决方案展览会
-
5月16日火热报名>>> OFweek锂电/半导体行业数字化转型在线研讨会
-
5月22日火热报名中 >> 瓦楞行业张力控制解决方案在线研讨会
-
5月31日立即报名>> 【线下论坛】新唐科技2024未来创新峰会
-
8月27-29日马上报名>>> 2024（第五届）全球数字经济产业大会暨展览会
-
8月27-29日火热报名>>> 全数会2024中国深圳智能制造与机器人展览会
推荐专题
发表评论
请输入评论内容...
请输入评论/评论长度6~500个字
暂无评论
暂无评论