改进的粒子群算法在流水车间调度问题中的研究与应用

发布时间：2018-04-16 23:39

本文选题：模拟退火算法 + 粒子群算法　；参考：《山东师范大学》2017年硕士论文

【摘要】：随着全球贸易的一体化,配置的全球化,顾客需求的多样化,企业间的竞争越来越激烈,尤其是在制造领域,在这种环境下,企业为了生存并且在竞争中取得一定的话语权,越来越重视对于生产的管理。流水车间是现如今企业采用最为广泛的生产作业形式,对其研究对企业的生产具有重要的意义。流水车间调度的主要目标便是根据企业的实际生产状况,合理的安排生产,使企业能够达到所设定的目标,实现利润的最大化。通过研究得知流水车间调度问题是一类典型的NP-Hard问题,求解过程太过复杂,研究者一直试图寻求一种有效的算法能够求解该问题,以便将其应用于实际的生产过程中。本文主要通过改进粒子群算法对置换和无等待的流水生产车间调度问题进行求解。粒子群算法作为一种新的智能优化算法,在搜寻的过程中,既受到个体搜寻的最优位置的影响,也会受到群体的最优位置的影响,具有快速的求解速度和较强的搜寻最优解的能力。因而本文将其应用于求解流水车间调度问题,但通过对粒子群的研究分析后发现粒子群算法主要应用于求解连续的问题,而车间调度问题的最优解是离散的,而且粒子群算法在应用过程中容易过早收敛而陷入某一局部最优的困境。对于粒子群的这些问题,本文为改进粒子群算法提出了改进的模拟退火粒子群算法和纵横交叉粒子群算法,并应用于求解置换流水车间和无等待流水车间调度问题中,基本创新点如下:(1)在置换流水车间问题的求解过程中,鉴于模拟退火算法具有较强的扩展搜寻范围的能力,能够跳出局部最优,将退火策略嵌入到种群粒子的更新过程中,构成模拟退火粒子群算法,通过优化种群的最优解,使粒子群算法摆脱受限于某一局部最优的困镜,在优化的过程中,采用交换、插入、逆序三种邻域搜索机制,根据Metropolis接受准则选取产生的解,并将改进后的算法用于求解置换流水车间数学模型中。(2)在无等待流水车间问题的求解过程中,本文引入了最新提出的纵横交叉算法对粒子群进行了优化,构成纵横交叉粒子群算法,主要依靠纵横交叉的横向交叉增强粒子之间的信息传递和纵向交叉跳出局部最优的能力,采用嵌入式和串行式两种结合方式,对粒子的历史最优位置进行优化,将不同结合方式的纵横交叉粒子群算法应用于求解典型的无等待流水车间调度问题,通过实验证明了嵌入式的纵横交叉粒子群算法具有较好的性能。
[Abstract]:With the integration of global trade, the globalization of distribution, the diversification of customer demand, the competition between enterprises is becoming more and more fierce, especially in the field of manufacturing. In this environment, the enterprises in order to survive and in the competition to obtain a certain right of speech.More and more attention is paid to the management of production.The flow shop is the most widely used production form in enterprises nowadays, and the research on it is of great significance to the production of enterprises.The main goal of the flow shop scheduling is to arrange production reasonably according to the actual production condition of the enterprise, so that the enterprise can achieve the set goal and realize the maximization of profit.It is found that the flow shop scheduling problem is a typical NP-Hard problem and the solution process is too complex. Researchers have been trying to find an effective algorithm to solve the problem in order to apply it to the actual production process.In this paper, the improved particle swarm optimization (PSO) algorithm is used to solve the flow shop scheduling problem with permutation and no waiting.As a new intelligent optimization algorithm, particle swarm optimization (PSO) is not only affected by the optimal location of individual search, but also by the optimal location of population.It has fast solving speed and strong ability of searching for optimal solution.Therefore, this paper applies it to solve the flow shop scheduling problem, but through the research and analysis of particle swarm optimization, it is found that particle swarm optimization algorithm is mainly used to solve continuous problems, and the optimal solution of job shop scheduling problem is discrete.Particle swarm optimization (PSO) is easy to converge prematurely and fall into a local optimal dilemma.For these problems, this paper presents an improved simulated annealing particle swarm optimization algorithm and a longitudinal and horizontal crossover particle swarm optimization algorithm for the improved particle swarm optimization algorithm, and it is applied to solve the scheduling problem of permutation flow shop and waiting free flow shop.The basic innovation is as follows: (1) in the process of solving the replacement flow shop problem, in view of the strong ability of the simulated annealing algorithm to extend the search range, the simulated annealing algorithm can jump out of the local optimum and embed the annealing strategy into the updating process of the population particles.The simulated annealing particle swarm optimization algorithm is constructed. By optimizing the optimal solution of the population, the particle swarm optimization algorithm can get rid of the trapped mirror which is limited by a local optimum. In the process of optimization, three neighborhood search mechanisms, exchange, insert and inverse order, are adopted.According to the Metropolis acceptance criterion, the solution is selected, and the improved algorithm is used to solve the displacement flow shop mathematical model.In this paper, the newly proposed crosswise and vertical crossover algorithm is introduced to optimize the particle swarm optimization, which mainly depends on the horizontal and vertical crossover to enhance the information transfer between the particles and the ability of vertical crossover to jump out of the local optimum.In this paper, the historical optimal position of particles is optimized by using embedded and serial combination, and the crosswise particle swarm optimization (PSO) algorithm with different combination methods is applied to solve the typical job-shop scheduling problem without waiting.The experiments show that the embedded particle swarm optimization algorithm has good performance.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;TB497

【参考文献】