一类混合生产线调度与数值仿真技术的研究

发布时间：2018-06-11 21:47

本文选题：排序流水车间调度 + 顺序依赖准备时间　；参考：《华南理工大学》2016年博士论文

【摘要】：流水车间是一类典型的混合生产线系统;这类混合生产线系统的相关调度问题,即排序流水车间调度问题(PFSP),广泛存在于制造企业中。随着需调度工件数目的增加,该类问题求解空间的可行解数目将呈现指数式的增长;显然,这类问题是典型的NP问题,所以这类问题是理论研究最为困难的问题之一。基于“总的加权延迟”最小化优化准则下考虑工件顺序依赖准备时间的PFSP问题(SDST-PFSP-WT)和基于制造期最小化优化准则下的零等待PFSP问题(NWPFSP)是分别在一个具有现实优化意义的优化准则下、考虑一个广泛存在的现实约束条件的两个PFSP问题。本文首先研究解决的就是这两个调度问题。多品种、中小容量的混合柔性生产线系统(FMS)当前广泛应用于制造企业中。因为具有工件传输路径柔性、生产节点服务方式柔性及服务选择柔性等共性特征,所以该类型生产系统能够满足企业多品种产品生产的目的。由于购买设备配置一个FMS系统需要花费企业大量的资金成本,所以优化布局这类系统是企业决策者需要重点解决的一个资源调度问题。FMS系统性能分析问题是FMS系统布局优化问题一个重要的基础子问题,数值仿真技术是解决这一基础问题的主要技术手段及方法。针对该类型生产系统的共性特征及面临的共性问题,本文研究解决了FMS系统数值仿真关键技术问题。本文主要的研究内容如下所示:针对SDST-PFSP-WT问题,经过调研国内外相关研究文献发现:插入搜索是一种高效的局部搜索算子;NEH_EWDD启发式算法及迭代贪婪智能算法(IG)分别是当前解决该问题最好的启发式及智能算法,并且上述两个算法都是基于插入搜索实现的。基于插入搜索,本文首先提出了一种有效的回溯算法及启发式算法(HPIS);并且,在此基础上,本文提出了两种具有较高算法性能的基于NEH_EWDD的启发式算法(NEH_EWDD_HPIS和NEH_EWDD_HPIS_ACC)。其次,基于综合上述提出的所有算法或方法,本文对IG算法进行了改进。最后,经过基准实验测试发现:提出的两种基于NEH_EWDD的启发式算法及改进的IG算法在性能上远优于相应的原始算法。针对NWPFSP问题,本文提出了一个混合IG算法解决该调度问题。首先,为了获得具有更好性能的初始解,本文进一步改进了提出的NEH_EWDD_HPIS算法,并将这改进的启发式算法作为混合算法的初始化方法。此外,本文提出了一种基于“块”的解“破坏“策略,并且引入了已经被其它作者证明在解决当前问题中比较有效的基于禁忌的重构方法。此外,本文提出了一种高效的、混合变邻域下降及变邻域搜索等两种搜索策略的局部搜索算法,该算法集成了插入移动搜索、置换移动搜索及块插入移动搜索等三个当前已被证明在解决该问题中比较有效的局部搜索算子。最后,实验证明:提出的算法在性能上优于当前存在的最有效算法。针对复杂FMS数值仿真关键技术问题,在分析这类系统所具有的共性特征及面临诸如工件传输阻塞、工件路由选择及设备多处理选择等共性问题的基础上,本文提出了一种基于拓扑及面向事件的FMS数值仿真技术。基于该数值仿真技术所实现的FMS数值仿真系统能够实现较通用的仿真具有路径柔性、服务方式柔性及服务选择柔性等柔性特征的一类FMS系统。
[Abstract]:Flow shop is a kind of typical hybrid production line system; the related scheduling problem of this kind of hybrid production line system, that is, scheduling flow shop scheduling problem (PFSP), is widely used in manufacturing enterprises. With the increase of the number of required scheduling jobs, the number of feasible solutions for this kind of problem solving space will be exponential growth; obviously, this kind of problem is the problem. It is a typical NP problem, so this kind of problem is one of the most difficult problems in theoretical research. Based on the "total weighted delay" minimization optimization criterion, the PFSP problem (SDST-PFSP-WT) and the zero wait PFSP problem (NWPFSP) based on the minimization optimization criterion (NWPFSP) under the minimum manufacturing time optimization criterion (NWPFSP) are in a present Under the optimization criterion of real optimization, two PFSP problems are considered for a widely existing constraint condition. This paper first studies the two scheduling problems. The hybrid flexible production line system (FMS) with multiple varieties and small and medium capacity is widely used in the manufacturing enterprises. Because of the flexibility of the workpiece transmission path and the production node This type of production system can meet the purpose of the production of many kinds of products. As the purchase equipment is equipped with a FMS system, it takes a lot of cost of funds, so the optimization of the layout is a resource scheduling that the enterprise decision-makers need to focus on. The problem of the performance analysis of the problem.FMS system is an important basic sub problem of the FMS system layout optimization problem. The numerical simulation technology is the main technical means and method to solve this basic problem. In view of the common characteristics of the type production system and the common problems facing this type of production system, the key technical problems of the numerical simulation of the FMS system are studied and solved in this paper. The main research contents of this paper are as follows: in view of the SDST-PFSP-WT problem, the research literature at home and abroad shows that the insertion search is an efficient local search operator, and the NEH_EWDD heuristic algorithm and the iterative greedy intelligent algorithm (IG) are the best heuristic and intelligent algorithms to solve the problem, and the above two algorithms are calculated. The method is based on the insertion search. Based on the insertion search, this paper first proposes an effective backtracking algorithm and heuristic algorithm (HPIS). On this basis, this paper proposes two NEH_EWDD based heuristic algorithms (NEH_EWDD_HPIS and NEH_EWDD_HPIS_ACC) with high algorithm performance (NEH_EWDD_HPIS and NEH_EWDD_HPIS_ACC). Secondly, based on the comprehensive above proposed All the algorithms and methods are improved in this paper. Finally, it is found that the proposed two NEH_EWDD based heuristic algorithms and improved IG algorithms are far superior to the corresponding original algorithms in performance. In this paper, a mixed IG algorithm is proposed to solve the scheduling problem for the NWPFSP problem. First, to obtain the problem. In order to have the initial solution of better performance, this paper further improves the proposed NEH_EWDD_HPIS algorithm and uses this improved heuristic as the initialization method of the hybrid algorithm. In addition, this paper proposes a "block" based solution "destruction" strategy, and introduces a comparison that has been proved by other authors to solve the current problem. In addition, this paper proposes an efficient local search algorithm for two search strategies, such as high efficiency, mixed variable neighborhood descent and variable neighborhood search. This algorithm integrates the insertion mobile search, displacement search and block insertion mobile search, which are currently proved to be more effective in solving the problem. Local search operators. Finally, experiments show that the proposed algorithm is superior to the most effective existing algorithms in performance. Based on the key technical problems of complex FMS numerical simulation, the common characteristics of this kind of system are analyzed, and the common problems such as the blocking of the workpiece transmission, the selection of the workpieces and the selection of the equipment are on the basis of the common problems. In this paper, a FMS numerical simulation technology based on topology and event oriented is proposed. The FMS numerical simulation system based on the numerical simulation technology can achieve a kind of FMS system with flexible characteristics such as path flexibility, service flexibility and service selection flexibility.
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TB497;TP18

【相似文献】