【作者】 刘志勇；

【导师】 吕文阁；

【作者基本信息】 广东工业大学 ， 机械设计及理论， 2011， 硕士

【摘要】 制造过程的调度技术,将在很大程度上影响产品生产的周期、成本和效率。优化制造过程调度,可以有效地提高企业的生产管理水平和制造自动化水平,从而提高企业的竞争力。作业车间调度问题是生产调度中许多实际问题的简化模型,是制造类企业无法回避的一个关键且核心的问题。现行的各种调度方法在求解作业车间调度问题时,都存在各种各样的缺陷。因此,改进现有的调度方法或者寻找新的调度方法,始终具有重要的理论价值和实际意义。蚁群算法的搜索机制模拟蚂蚁觅食过程中的群体行为,适合于求解旅行商问题等组合优化问题,但应用于作业车间调度问题的研究不多,且优化效果不明显,也没有一般性规律可循。竞选算法搜索机制模拟竞选活动中对更高支持率的追求动机,目前主要应用于连续域内的各种函数优化问题。本文针对作业车间调度问题,对蚁群算法进行改进,设计了一种新的信息素更新方式；对竞选算法进行离散化设计,探索新的求解作业车间调度问题的调度方法,并对这两种算法进行比较。本文的主要研究结果如下：(1)本文综合分析了蚁群算法的特点及作业车间调度问题的特点,讨论了两种经典的改进蚁群算法—蚁群系统与最大最小蚂蚁系统—的算法思想及求解机制。在此基础上,提出了一种新的改进蚁群算法。为了验证该改进蚁群算法的有效性,将其应用于作业车间调度问题与柔性作业车间调度问题的求解。采用文献中的测试函数进行计算,并将计算结果与文献中的结果进行比较分析。结果表明,该改进蚁群算法大大提高了问题的求解效率及求解结果。(2)介绍了竞选算法的基本思想、基本原理以及在连续优化领域内的应用研究。将竞选算法应用于求解作业车间生产调度问题,采用基于工序的表达法表示问题的解,采用基于关键路径的邻域搜索方法生成局部选民,这两者是竞选算法的离散化设计的核心技术。将离散化的竞选算法求解FT06算例以及LA系列标准调度函数,无论是计算时间,还是计算结果,离散的竞选算法都取得了较好的效果,表明了该改进算法的有效性及可行性。(3)利用Matlab 7编程实现了上述两种算法的操作,构建了一个求解作业车间调度问题的工具包。(4)分析了改进蚁群算法与改进竞选算法两种启发式优化算法在算法特性方面的异同点,并对这两种算法进行求解质量、算法时间复杂度和空间复杂度等方面的比较分析。更多还原

【Abstract】 Scheduling technologies in producing process would affect product produce period, product cost and efficiency. Optimizing scheduling problems in produce process could improve the level of management and manufacturing automatization, which would help manufacturing corporations increase the competition power. Job-shop scheduling problem (JSP) was a simplified model of many practical problems. It was also a core problem corporations could be inevitable to face. But the existing scheduling technologies had different kinds of limitations when they were applied to solve JSPs. So, to improve existing scheduling methods or find new scheduling technologies to solve JSPs accurately and quickly would be provided with an important academic value and practical significance.Ant Colony Optimization (ACO) analogized the social behavior of seeking food of ant colonies, which was good for solving combinational optimization problems, such as Traveling Salesman Problem (TSP), but its study in JSP field was few, the optimization result was not very good, and there was not regular rule to be used. Election Campaign Algorithm (ECA) simulated the pursuit of highest support rate in election activities. At present, ECA was almost used in engineering fields.In order to solve JSPs, this paper designed a new pheromone update rule; an improved ECA was designed to explore new scheduling technologies to solve JSPs. And then these two algorithms were compared in many aspects. The conclusions this paper had gotten followed as:Firstly, this paper presented the characters of ACO and JSP separately. Then this paper introduced the ideas and principles of two classic improved ACO, Ant Colony System (ACS) and Max-Min Colony System (MMAS). This paper proposed an improved ACO based on the characters of ACS and MMAS. And then the improved ACO was applied to solve JSPs and more complicated Production Scheduling problems, Flexible Job-shop Scheduling Problems (FJSPs) mentioned in references. The results demonstrated that the improved ACO could improve the quality and efficiency of solutions after compared the results with the solutions that the other heuristic algorithm got.Secondly, this paper introduced the basic idea, principle and compute process about ECA. ECA has been applied to solve practical engineering problems in many fields. But it would be improved to solve discrete problems. This paper expressed the JSP solution based on operation expression method, and generated local voter based on critical path method neighbor search technology, which was the key technology for the design of improved ECA. This paper Applied the improve ECA to solve instances of FT06, LA01, LA03, LA04 and LA05 and LA15. The results showed the improved ECA could get good optimization solutions in less computing time.Thirdly, this paper programmed to complete the scheduling operations for both algorithms using Matlab 7, and then this paper developed a toolbox to solve JSPs.Fourthly, this paper had an analysis by comparing these two improved algorithms in some characters, such as search efficiency, computational complexity.更多还原