系统工程与电子技术 ›› 2019, Vol. 41 ›› Issue (5): 1079-1086.doi: 10.3969/j.issn.1001-506X.2019.05.21

• 系统工程 • 上一篇    下一篇

求解混合流水车间调度的改进贪婪遗传算法

SONG Cunli   

  1. 大连交通大学软件学院, 辽宁 大连 116028
  • 出版日期:2019-04-30 发布日期:2019-04-29

Improved greedy genetic algorithm for solving the hybrid flow-shop scheduling problem

SONG Cunli   

  1. College of Software, Dalian Jiaotong University, Dalian 116028, China
  • Online:2019-04-30 Published:2019-04-29

PDF (PC)

摘要：

针对最小化最大完工时间的带有不相关并行机的混合流水车间调度问题,提出了改进贪婪遗传算法。首先,该算法染色体编码采用基于工件加工顺序的编码,解码提出了两种设备分配方案,并考虑到不同阶段加工设备配置不同对算法的影响,采用了正序解码和逆序解码加再调度并用的解码策略。其次,提出贪婪交叉算子和贪婪变异算子,这些算子不仅承担改进种群,增加种群多样性的功能,同时还具有较强的局部搜索能力。最后通过正交实验确定算法的参数设置,与已有算法对已知案例的求解结果进行了比较,说明了该算法的有效性。同时实验表明了正序和逆序解码策略的必要性以及正序或逆序解码的时机。

关键词: 混合流水车间调度, 贪婪遗传算法, 正序和逆序解码, 最小化最大完工时间

Abstract:

The greedy genetic algorithm is proposed to solve the hybrid flow shop scheduling problem with unrelated parallel machines for minimizing makespan. Firstly, the chromosome coding is based on the job processing sequence and two kinds of machine allocation schemes are considered. Considering the influence of different stages’ equipment configuration on the result of scheduling, the forward or reverse decoding strategy with the corresponding rescheduling method are used. Moreover, the greedy crossover and mutation operators are proposed. They not only improve the quality and diversity of the population, but also have a strong local search ability. Finally, the orthogonal experiment is done to determine the parameters of the algorithm, the computation results on the known cases show that the effectiveness of the algorithm compared with the known algorithms. At the same time, the experiments also show the necessity of the forward and reverse decoding strategy and the timing of using them.

Key words: hybrid flow-shop scheduling problem, greedy genetic algorithm, forward and reverse decoding, makespan

京ICP备11035014号-5
版权所有 © 2019 北京航天情报与信息研究所《系统工程与电子技术》编辑部
通讯地址：北京市142信箱32分箱《系统工程与电子技术》编辑部(100854)
电　话：(010)68388406/68386014    E-mail：xtgcydzjs@126.com(系统工程与电子技术)/jseeoffice@126.com(JSEE)
本系统由北京玛格泰克科技发展有限公司设计开发