不确定条件下单机批调度优化算法研究

发布时间：2018-07-09 19:32

本文选题：生产调度 + 粒子群算法　；参考：《中国矿业大学》2014年硕士论文

【摘要】：生产调度是现代企业生产管理的核心，也是工业生产过程实现高效可靠运行的基础和关键。企业的生产过程需要利用有效的优化技术和生产调度方法来降低成本、减少浪费，增强企业的整体竞争力。实际的生产调度问题大都是动态、不确定、多约束的组合优化问题，已被证明为NP-hard问题，在工业生产、现代物流、计算机科学等领域有着广发的应用，对该类问题的研究对实际生产活动具有很大的理论意义和实用价值。现有文献对于不确定调度问题的研究仍然存在着不足之处。一是研究的不确定性问题约束条件比较单一，较少学者将多种约束融合在一起研究。二是对该类问题的求解主要是利用确定性精确求解方法，在工程应用大规模的调度问题中确定性问题的研究并不能完全表达问题模型，对不确定批调度问题模型构建方式的研究很少。本文的主要工作如下：（1）对于工件动态到达，尺寸有差异，加工时间以及交货期的不确定等多种约束单机批调度问题进行了研究，并且将该类问题扩展到更接近实际生产情况的模糊环境当中，利用模糊数学理论对单机批调度不确定性问题进行建模分析，采用基于工件序列的编码方式，利用分批策略等改善算法的整体性能。（2）利用粒子群算法(PSO)求解了不确定条件单机批调度问题。针对标准PSO算法容易陷入局部最优造成早熟收敛的问题，提出了一种非线性自适应惯性权重因子，并在算法后期对全局最优值做了自适应变异策略的改进。通过实验仿真验证了两种算法的有效性。（3）利用差分进化算法(DE)求解了不确定条件单机批调度问题。对DE算法的差分策略提出了自适应变异算子和随迭代次数递增二次函数的交叉算子，交叉操作采用基于参数交配的交叉方法，变异操作采用替换变异方法。通过实验仿真验证了两种算法的有效性。（4）由于PSO算法存在易陷入局部最优的问题，而差分进化算法是一种基于启发式算法的全局搜索技术。为了更好求解不确定条件单机批调度问题，保持PSO和DE算法种群的多样性和全局搜索能力，，本文在改进PSO和DE算法的基础上，提出了基于双种群的搜索策略的一种混合的差分粒子群算法（DEPSO）。利用DEPSO算法求解不确定条件的单机批调度问题。通过几组仿真实验对比，改进的混合算法(DEPSO)在求解不确定条件单机批调度问题时取得更优的效果。最后，总结全文并提出对今后不确定条件调度问题的展望。该论文有图16幅，表16个，参考文献79篇。
[Abstract]:Production scheduling is the core of modern enterprise production management, and it is also the foundation and key to realize efficient and reliable operation of industrial production process. The production process of enterprises needs to use effective optimization technology and production scheduling methods to reduce costs, reduce waste, and enhance the overall competitiveness of enterprises. The actual production scheduling problems are mostly dynamic, uncertain and multi-constrained combinatorial optimization problems, which have been proved to be NP-hard problems, and have been widely used in industrial production, modern logistics, computer science and other fields. The study of this kind of problems has great theoretical significance and practical value for practical production activities. There are still some shortcomings in the research of uncertain scheduling problems in the existing literature. The first is that the uncertainty constraints are relatively simple, and few scholars study them together. Second, the solution of this kind of problem is mainly using deterministic exact solution method. The research of deterministic problem in large-scale scheduling problem in engineering application can not completely express the model of the problem. There is little research on how to construct uncertain batch scheduling model. The main work of this paper is as follows: (1) the dynamic arrival of the workpiece, the difference in size, the uncertainty of processing time and delivery date, and so on, are studied. And the problem is extended to the fuzzy environment which is closer to the actual production situation, and the uncertainty problem of single machine batch scheduling is modeled and analyzed by using fuzzy mathematics theory, and the coding method based on workpiece sequence is adopted. The whole performance of the algorithm is improved by using batch strategy. (2) Particle Swarm Optimization (PSO) is used to solve the uncertain single-machine batch scheduling problem. Aiming at the problem that standard PSO algorithm is easy to fall into local optimum and cause premature convergence, a nonlinear adaptive inertial weight factor is proposed, and the adaptive mutation strategy for global optimal value is improved in the later stage of the algorithm. The experimental results show that the two algorithms are effective. (3) differential evolutionary algorithm (DE) is used to solve the uncertain single-machine batch scheduling problem. For the difference strategy of DE algorithm, the adaptive mutation operator and the crossover operator with quadratic function increasing with the number of iterations are proposed. The crossover method based on parameter mating and the substitution mutation method are used in the crossover operation. The experimental results show the effectiveness of the two algorithms. (4) the PSO algorithm is easy to fall into the local optimal problem, and the differential evolution algorithm is a global search technology based on heuristic algorithm. In order to solve the uncertain condition single machine batch scheduling problem, and to maintain the diversity of PSO and DE algorithm population and the global search ability, this paper improves the PSO and DE algorithm. A hybrid differential particle swarm optimization (DEPSO) algorithm based on a dual population search strategy is proposed. DEPSO algorithm is used to solve the single machine batch scheduling problem with uncertain conditions. By comparison of several simulation experiments, the improved hybrid algorithm (DEPSO) achieves better results in solving single batch scheduling problem with uncertain conditions. Finally, the paper summarizes the full text and puts forward the prospect of uncertain condition scheduling problem in the future. There are 16 pictures, 16 tables and 79 references.
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TB497;TP18

【参考文献】