一种启发式算法和改进遗传混合算法在流水车间重调度中的应用

Application of a heuristic algorithm and improved genetic hybrid algorithm in production rescheduling

摘要:

在解决以合同惩罚和存储成本最小化为优化目标的流水车间重调度问题时，提出了一种启发式算法和改进的遗传混合算法。传统的遗传算法是一种基于优胜劣汰的随机、自适应的优化算法。通过复制，交叉和变异，将问题解编码所表示的“染色体”群在逐代进化，最终收敛到最合适的群体，从而得到问题的最优或满意解。但缺点是求解结果依赖于初始值，且运行时间过长。因此对传统遗传算法做了相应的改进，考虑到启发式算法的快速性，为充分发挥俩种算法的优势，提出启发式算法和改进遗传混合算法。最后对性能进行分析；试验结果表明：该算法运行时间短，且在大规模数据集下，更易于靠近全局最优解。

Abstract:

A heuristic algorithm and an improved genetic hybrid algorithm are proposed to solve the rescheduling problem of flow shop with the objective of minimizing the contract penalty and storage cost. The traditional genetic algorithm is a random and adaptive optimization algorithm based on the survival of the fittest. By means of replication, crossover and mutation, the "chromosome" group represented by the solution coding is evolved from generation to generation, and finally converges to the most appropriate group, so as to obtain the optimal or satisfactory solution of the problem. But the disadvantage is that the solution depends on the initial value, and the running time is too long. In order to give full play to the advantages of the two algorithms, a heuristic algorithm and an improved genetic hybrid algorithm are proposed. Finally, the performance of the algorithm is analyzed, and the experimental results show that the algorithm runs in a short time, and is easier to approach the global optimal solution in a large data set.