【作者】 李新宇；

【导师】 邵新宇； 高亮；

【作者基本信息】 华中科技大学 ， 工业工程， 2009， 博士

【摘要】 工艺规划和车间调度是制造系统中两个十分重要的子系统。在传统的研究中,研究人员将工艺规划和车间调度作为各自独立的系统,分别对两者进行独立的研究,对它们的集成研究还不够。然而事实上,如果把工艺规划和车间调度系统进行集成可以较好地提高制造系统的工作效率。所以,工艺规划与车间调度集成越来越受到学者和工程技术人员的重视。工艺规划与车间调度集成(IPPS)问题是最困难的NP-Complete组合优化问题之一,经过几十年的发展,研究人员提出了不少求解该问题的方法,但是至今最好的算法仍很难有效地的求解该问题。本文的主要目的是深入研究IPPS问题,探索该问题在不同条件下高效的求解方法。首先,本文深入研究了IPPS优化模型:基于作业车间调度的混合整数规划模型,提出了IPPS问题的数学模型,并提出了集成优化策略对IPPS问题进行求解,该策略为后续研究提供指导;然后,根据提出的集成优化策略,分别对各部分进行详细研究:一、深入研究了遗传算法在柔性工艺规划问题中的应用。提出了针对柔性工艺规划问题的多部分编码方式,这更有利于算法算子的操作;并提出了新的交叉方法,避免了非法解的产生,提高了求解效率;针对编码特点,设计了相应的变异算子。使用实例对改进的遗传算法进行了测试,并与其它算法进行了比较,验证了该编码方法和操作算子的有效性和优越性。二、在以上研究的基础上,深入研究了改进遗传算法求解IPPS问题。基于以上的集成优化策略,提出了改进遗传算法求解IPPS问题的流程,在该流程中:车间调度问题的染色体编码采用基于工序的编码,采用活动调度的解码方式;结合问题本身特点设计了车间调度问题的交叉算子和变异算子。使用基准实例测试改进的遗传算法,并与其它算法进行了比较,验证了该算法的有效性和优越性。研究表明单一算法较难解决复杂的组合优化问题,几种优化算法的合理混合能提供更强大的搜索能力。本文将具有较强全局搜索能力的遗传算法和具有较强局部搜索能力的禁忌搜索算法有机结合,提出了求解IPPS问题的混合优化算法。该算法能较好地平衡其集中搜索和分散搜索的能力,弥补了单一算法各自的缺点。针对IPPS问题的特点,选取并改进了相应的邻域结构。采用基准实例测试提出的混合算法,并与其它算法进行比较,结果显示了混合算法的有效性和优越性。在企业的实际生产中,多目标问题普遍存在。在现阶段,对IPPS的研究主要是集中在单目标问题上。本文在对单目标IPPS问题研究成果的基础上,对多目标IPPS问题进行了较深入的研究,提出了一个基于多目标进化算法的求解方法来对多目标IPPS问题进行研究,然后采用实例测试提出的求解算法,验证了该算法的有效性。传统上,针对IPPS的研究大多集中在静态环境下,但是实际生产过程中存在着种种随机的和不确定的干扰因素。静态IPPS的结果很难适应实际生产的需要,有必要对已有的结果根据这些变化进行及时的调整。本文结合实际生产的需求对动态环境下的IPPS问题进行了研究,是传统IPPS问题的一种扩展。结合动态调度的己有研究成果以及前面提出的优化算法,提出了一种基于改进遗传算法的动态调度策略。然后对以上提出的策略进行仿真测试,验证了该策略的可行性和有效性。本文结合以上理论研究成果和工程实例,设计开发了IPPS原型系统。该原型系统利用提出的方法对柔性工艺规划问题和IPPS问题进行优化。最后对全文进行了总结,展望了进一步的研究方向。更多还原

【Abstract】 Process planning and Scheduling are two of the most important sub-systems in manufacturing systems. In traditional approach, process planning and scheduling were carried out sequentially. The researchers did not pay much attention on the integration of them. This approach has become an obstacle to improve the productivity and responsiveness of manufacturing systems. However, in fact, the integrated process planning and scheduling (IPPS) can greatly enhance the productivity of the manufacturing system. Therefore, IPPS has attracted more and more researchers and engineers.IPPS is one of the most complicated NP- Complete combinational optimization problems. After more than 20 years of development, researchers had proposed several methods. However, the state-of-the-art algorithms also can not solve this problem effectively. The main purpose of this dissertation is to do the deep research on IPPS problem and to explore the effective solution methods of this problem under different situations. Firstly, based on the mathematical model of job shop scheduling problem, the mathematical model of IPPS and an integration optimization strategy have been proposed. This strategy can guide the following research works of the dissertation. Then, according to this strategy, we do the research on each part detailedly: 1) Making deep research on the flexible process planning (FPP) problem with genetic algorithm (GA). In this part, the multi-parts representation method has been proposed. This method is more conducive to the design and operations of the genetic operators. The new crossover operator has been proposed to avoid the unreasonable solutions and improve the solution efficiency. Based on the features of this representation, the relative mutation operator has been designed. To verify the feasibility and performance of the proposed approach, experimental studies have been conducted. The experimental results show that the proposed approach is very effective; 2) Based on the previous works, making deep research on the IPPS problem. In this part, the flow chart of GA based on the previous integration optimization strategy has been proposed. In this approach, the operation-based representation method and active scheduling decoding method have been used for the scheduling problem. The crossover and mutation operators have been designed. Several experiments have been used to verify the feasibility and performance of the proposed approach. The results show that the research on IPPS is necessary and the proposed method is very effective to solve IPPS problem.The researches show that one single algorithm can not solve the complex combinational optimization problems effectively. And, the hybrid algorithms can provide more powerful searching ability. One hybrid algorithm which is mixed by the GA with strong global searching ability and tabu search with strong local searching ability has been proposed to solve IPPS problem. This algorithm can balance its diversification and intensification very well during the searching process. Based on the features of IPPS problem, effective neighborhood has been selected and modified. To verify the feasibility and performance of the proposed approach, experimental studies have been conducted and comparisons have been made between this approach and some other works. The experimental results show that the hybrid algorithm has achieved significant improvement.In the real production environment, there are many multi-objective problems. However, in the current stage, the most researches on IPPS focus on the single objective problem. Therefore, the research on the multi-objective IPPS problem is necessary and has been done in this dissertation. Based on the previous works on the single objective IPPS problem and multi-objective evolutionary algorithm, one solution method has been proposed to solve the multi-objective IPPS problem. To verify the feasibility and performance of the proposed approach, experimental studies have been conducted. The experimental results show that the proposed method is effective.In traditional approach, the most researches focus on the static IPPS problem. However, in the real production environment, there exist many unexpected events to interfere in the normal production process. Therefore, the results of the static IPPS can not fit the real production very well. In this dissertation, the research on the dynamic IPPS has been done. It is the extension of the static IPPS. Based on the previous work of the static IPPS and proposed optimization algorithms, one dynamic scheduling strategy based on the improved GA has been proposed. To verify the feasibility and performance of the proposed approach, it has been applied to solve several dynamic events in the real production environment. The results show that the proposed method is effective.The IPPS simulation system has been designed and developed based on the above research works. This system can use the proposed algorithms to solve the FPP and IPPS problems. One practical case study has been used to verify the feasibility and performance of this system.Finally, the researches in the dissertation are summarized and some future research directions have been presented.更多还原