面向快速制造的车间调度策略研究

【作者】 李进；

【导师】 楼佩煌；

【作者基本信息】 南京航空航天大学 ， 机械电子工程， 2004， 硕士

【摘要】 车间资源的有限性制约着生产任务的完成，能否有效利用车间现有资源完成生产任务，以最快的速度响应市场需求，已经成为决定制造型企业能否赢得市场竞争的关键。因此，车间调度策略一直是制造业研究的热点。但是，资源约束和工艺约束的并存，使得车间调度成为一类NP-hard问题。同时，实际车间中的各种动态事件难以预测，以致车间调度问题异常复杂，迄今为止还没有一种通用有效的调度策略。 本文针对牵拉(Pull)型市场环境的特点，将遗传算法与多代理思想相结合，提出一种基于多代理系统(Multi-Agent System，MAS)和遗传算法(Genetic Algorithm，GA)的动态车间调度模型，并据此构建了一个实用且适应性广的动态车间调度原型系统。首先，本文介绍了车间调度的背景、类型和研究发展状况，并分析了GA和MAS在解决JSSP这类NP-Hard问题方面的前景。接着本文详细探讨了将GA运用在车间调度问题(Job Shop Scheduling Problem，JSSP)中的关键技术，同时对比了二／十进制编码方案的性能。特别地，在将GA应用于JSSP的过程中，死锁问题是讨论的重点，死锁的消除是用GA解决JSSP的前提。针对GA收敛速度较低的情况，文中提出了几种改进方法，使调度系统具有较高的收敛速度，并有柔性路径选择功能。在GA提供了求解JSSP的有效支持的基础上，本文引入多代理思想管理车间生产动态过程，以将动态JSSP分解为一系列静态JSSP，从而能通过GA方法求解。最后，大量的仿真实验证明了基于MAS和GA的车间调度系统在实际应用中的前景。更多还原

【Abstract】 The insufficience of resources in the shopfloor holds back the accomplishment of production plans. In a sense, whether the enterprise can survive market competition is determined by whether it can meet customers’ demands in time, which is further determined by how efficiently the limited resources are used. Consequently, extensive researches have been carried out concerning scheduling methods for shopfloor since scheduling methods help make best use of resources.In real shopfloor scheduling scenarios, resource restriction coexists with process restriction, which makes shopfloor scheduling problems NP-hard. Meanwhile, the changeability of market demand together with the uncertainty in a real job shop adds to the complexity of JSSP. As a result, there exist no effective and widely applicable job shop scheduling methods.This paper puts forward a MAS-GA based dynamic job-shop scheduling model. Our scheme combines the advantages of GA and MAS, taking into consideration the characteristics of the PULL Pattern market. Based on the model, we implemented an effective and widely applicable prototype system for dynamic JSSPs.The first part of the paper introduces the background, the categories and the development of job shop scheduling. Meanwhile, the promising aspects of GA and MAS for solving NP-Hard problems are highlighted. The second chapter analyses in detail how to adapt GA for JSSP, and compares the performances of the GA in binary coding and decimal coding. Also, we put special emphasis on deadlock problems since deadlock is a big obstacle to GA-based JSSP solutions. Considering GA converges slowly, special adaptations are made to the GA constructed in the second chapter. The new GA converges much more quickly and can find the most suitable route for an operation. The fourth chapter introduces MAS mechanism to construct a dynamic job-shop scheduling system, with GA providing basic support. MAS mechanism decomposes a continuous and dynamic job-shop scheduling problem into series of JSSPs so that the predefined GA can work out the schedule. Finally, the results from simulation shows the MAS-GA based scheduling system is promising for practical job-shop scheduling.更多还原