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

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

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

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.