基于蜂群繁殖算法的流水车间调度问题研究
发布时间：2019-03-29 12:56
【摘要】：流水车间调度问题在实际制造生产中广泛存在，该类问题的研究一直也是制造业与学术界关心的热点问题。对该问题进行研究，可以有效提高流水车间的生产效率、降低在制品库存、缩短拖后期。在如今制造业竞争日趋激烈、客户需求日益个性化和多样化的时代，显得更为重要。 绝大多数流水车间调度是NP-hard问题。近年来，基于自然规律提出的元启发式算法在求解该问题的过程中显示出了较好的效果。本文所研究的蜂群繁殖算法是结合了群体优化与局部搜索思想的新型优化算法，目前已成功应用于许多组合优化问题中。本文理论结合实践，依次对单目标、多目标流水车间调度以及带有限缓冲区的多目标混合流水车间调度问题进行研究，具体研究内容如下。 (1)在求解单目标置换流水车间调度问题时，提出了一种变邻域搜索与模拟退化算法结合的局部搜索机制来模拟工蜂的行为，提出了改进的蜂群繁殖算法。然后通过对相关基准实例的求解，获得了较好的优化效果，并与其他文献中的结果进行比较验证了该算法的有效性。 (2)多目标优化问题是近几年研究的热点问题。本文针对最大完工时间、总流程时间和总拖期三个典型目标，，研究多目标置换流水车间调度问题。基于Pareto思想提出了一种多蜂王的蜂群繁殖算法，采用聚集距离增加非支配解的分散性以及算法的搜索空间；设计了一种基于Pareto的变邻域搜索算法，以及一种基于记忆机制的交叉操作。通过实例测试并与文献中目前最优非支配解集进行比较，验证了所提出算法的有效性。 (3)混合流水车间调度是流水车间调度问题中最贴近实际的一类问题，在上述研究的基础上，本文针对发动机5C件加工实际应用，基于蜂群繁殖算法研究带有限缓冲区的多目标混合流水车间调度问题。采用了基于置换工件的编码方式，然后通过完整调度构造程序生成可行调度，获得较好的调度结果。通过与已有文献中的实例进行测试比较，验证了算法的有效性。 最后，基于上述研究成果，开发出相应的原型系统，进行了全文总结，并对蜂群算法在流水车间调度问题上的深入研究进行了展望。
[Abstract]:The flow shop scheduling problem exists widely in the actual manufacturing, and the research of this kind of problem has always been a hot issue of concern in the manufacturing and academic circles. The research on this problem can effectively improve the production efficiency of the flow shop, reduce the inventory of in-process products, and shorten the late period. In today's manufacturing industry increasingly fierce competition, customer demand increasingly personalized and diversified era, appears more and more important. Most of the flow shop scheduling is NP-hard problem. In recent years, the meta-heuristic algorithm based on natural law has shown a good effect in the process of solving the problem. The swarm breeding algorithm studied in this paper is a new optimization algorithm which combines the idea of population optimization and local search and has been successfully applied to many combinatorial optimization problems. In this paper, the single-objective, multi-objective flow shop scheduling and multi-objective hybrid flow-shop scheduling with limited buffers are studied in turn by combining theory and practice. The details of the research are as follows. The main results are as follows: (1) when solving the single objective permutation flow shop scheduling problem, a local search mechanism combining variable neighborhood search and simulated degradation algorithm is proposed to simulate the behavior of worker bees, and an improved colony reproduction algorithm is proposed. Then by solving the related benchmark examples, a better optimization effect is obtained, and the effectiveness of the algorithm is verified by comparing with the results in other literatures. (2) Multi-objective optimization is a hot topic in recent years. In this paper, a multi-objective displacement flow shop scheduling problem is studied for three typical objectives: maximum completion time, total process time and total delay. Based on the idea of Pareto, a colony reproduction algorithm for multi-queen bee is proposed. The clustering distance is used to increase the dispersion of the non-branching solution and the search space of the algorithm. A variable neighborhood search algorithm based on Pareto and a cross operation based on memory mechanism are designed. The effectiveness of the proposed algorithm is verified by example testing and comparing with the current optimal non-dominated solution set in the literature. (3) the mixed flow shop scheduling is the most practical one in the flow shop scheduling problem. On the basis of the above research, this paper aims at the practical application of engine 5C parts processing. The multi-objective hybrid flow shop scheduling problem with limited buffer is studied based on colony reproduction algorithm. The coding method based on the replacement workpiece is adopted, and then the feasible scheduling is generated by the complete scheduling construction program, and the better scheduling results are obtained. The validity of the algorithm is verified by testing and comparing with the existing examples in the literature. Finally, based on the above-mentioned research results, the corresponding prototype system is developed, and the whole paper is summarized, and the in-depth research of swarm algorithm in flow shop scheduling is prospected.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TH186;TP301.6
本文编号：2449567
[Abstract]:The flow shop scheduling problem exists widely in the actual manufacturing, and the research of this kind of problem has always been a hot issue of concern in the manufacturing and academic circles. The research on this problem can effectively improve the production efficiency of the flow shop, reduce the inventory of in-process products, and shorten the late period. In today's manufacturing industry increasingly fierce competition, customer demand increasingly personalized and diversified era, appears more and more important. Most of the flow shop scheduling is NP-hard problem. In recent years, the meta-heuristic algorithm based on natural law has shown a good effect in the process of solving the problem. The swarm breeding algorithm studied in this paper is a new optimization algorithm which combines the idea of population optimization and local search and has been successfully applied to many combinatorial optimization problems. In this paper, the single-objective, multi-objective flow shop scheduling and multi-objective hybrid flow-shop scheduling with limited buffers are studied in turn by combining theory and practice. The details of the research are as follows. The main results are as follows: (1) when solving the single objective permutation flow shop scheduling problem, a local search mechanism combining variable neighborhood search and simulated degradation algorithm is proposed to simulate the behavior of worker bees, and an improved colony reproduction algorithm is proposed. Then by solving the related benchmark examples, a better optimization effect is obtained, and the effectiveness of the algorithm is verified by comparing with the results in other literatures. (2) Multi-objective optimization is a hot topic in recent years. In this paper, a multi-objective displacement flow shop scheduling problem is studied for three typical objectives: maximum completion time, total process time and total delay. Based on the idea of Pareto, a colony reproduction algorithm for multi-queen bee is proposed. The clustering distance is used to increase the dispersion of the non-branching solution and the search space of the algorithm. A variable neighborhood search algorithm based on Pareto and a cross operation based on memory mechanism are designed. The effectiveness of the proposed algorithm is verified by example testing and comparing with the current optimal non-dominated solution set in the literature. (3) the mixed flow shop scheduling is the most practical one in the flow shop scheduling problem. On the basis of the above research, this paper aims at the practical application of engine 5C parts processing. The multi-objective hybrid flow shop scheduling problem with limited buffer is studied based on colony reproduction algorithm. The coding method based on the replacement workpiece is adopted, and then the feasible scheduling is generated by the complete scheduling construction program, and the better scheduling results are obtained. The validity of the algorithm is verified by testing and comparing with the existing examples in the literature. Finally, based on the above-mentioned research results, the corresponding prototype system is developed, and the whole paper is summarized, and the in-depth research of swarm algorithm in flow shop scheduling is prospected.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TH186;TP301.6
【参考文献】
相关期刊论文 前2条
1 王炳刚;饶运清;邵新宇;王孟昌;;带有限中间缓冲区的多级并行机问题的求解[J];华中科技大学学报(自然科学版);2009年05期
2 李丽荣,郑金华;基于Pareto Front的多目标遗传算法[J];湘潭大学自然科学学报;2004年01期
本文编号：2449567
本文链接：https://www.wllwen.com/kejilunwen/jixiegongcheng/2449567.html
