【作者】 徐新黎；

【导师】 王万良；

【作者基本信息】 浙江工业大学 ， 控制理论与控制工程， 2009， 博士

【摘要】 生产调度是目前生产管理中最为薄弱,也是最为困难的一环,已成为目前计算机集成制造系统研究中的一个瓶颈问题。自五十年代以来,学术界已广泛地研究了生产调度问题,取得了许多研究成果,但由于其本身的复杂性,至今尚未形成系统的理论与方法。如阿将经典调度理论与生产实际相结合,提高对企业生产控制的精确性、及时性和有效性,是多年来研究人员和企业界关注的问题。由于多Agent系统是通过在一系列分散的自治智能体间进行协调和合作来解决问题的,具有自治、分布、动态等一些自然特性,可以满足复杂的、柔性的、鲁棒的和动态的制造系统生产调度的需要,因此引入多Agent技术是解决上述问题的良好方案之一。本文主要研究了基于多Agent的生产调度系统模型,提出了基于Hopfield神经网络和基于免疫算法的几种改进作业车间调度方法,以及基于多Agent的动态调度方法。具体研究内容如下:(1)首先阐述了课题的研究背景及意义,给出了生产调度问题的描述和分类。在对国内外大量文献总结提炼的基础上,总结了生产调度问题的国内外研究现状,分析了生产调度研究中存在的问题。(2)针对不确定的和不断变化的制造系统环境下复杂的生产调度问题,特别是那些短期的、敏捷性要求较高的动态调度问题,建立了基于多Agent的生产计划与车间调度系统模型,给出了管理Agent、资源Agent、任务Agent和计算Agent的具体功能。对企业多个并行车间的生产计划优化分配问题进行研究,提出了多Agent之间的改进合同网协商策略,并给出了多Agent并行车间计划优化模型的具体实现过程,仿真实验表明了该模型的有效性。(3)为了克服基于Hopfield神经网络的作业车间调度方法易得到不可行解这一不足,提出了基于操作编码的离散Hopfield神经网络(DHNN)作业车间调度方法,给出了包括行约束、列约束、全局约束和目标约束的新能量函数,从而保证了神经网络能够快速收敛到满足资源约束和顺序约束的可行优化调度解。为了更好地搜索到Job-shop调度问题的全局最优解,在DHNN算法中引入了模拟退火机制,提出了离散暂态混沌神经网络(TDNN)方法,标准实例的仿真结果表明TDNN方法具有优越的优化性能。最后用改进的Hopfield神经网络方法成功求解了一个来自某机械厂的Job-shop调度实例。(4)基于自适应疫苗提取与接种机制,提出了基于自适应免疫算法的作业车间调度方法,并对其优化性能、疫苗提取和接种方式、编码方式进行了仿真实验分析。其次为了更好地提高算法的整体性能,结合多智能体系统,构造了一种多智能体免疫算法。该方法通过智能体与其邻居间的竞争操作以及自学习操作,并结合自适应疫苗接种、交叉、变异和模拟退火操作,来更新每个智能体在解空间的位置,使其能够更精确地收敛到全局最优解。最后针对纸盆车间的实际生产特点,建立了批量可变的模糊柔性Job-shop调度问题模型,并对某纸盆车间的调度实例进行了求解,实验结果验证了算法的有效性。(5)针对生产环境经常发生变化的作业车间调度,建立了一种将蚂蚁智能与强化学习相结合的协商策略,并通过Agent的智能决策来实现实时作业任务的分配,示例仿真验证了该方法在订单、机器等生产环境变化的情况下仍然能取得较好的效果,而且减少了通信量。最后根据印染生产过程的工艺特点和约束条件,建立了染色车间作业调度问题模型,提出了基于多Agent的染色车间动态调度方法,通过实例求解验证了该方法对生产环境经常发生变化的自适应能力。(6)在上述理论工作的基础上,针对典型的按订单生产、多品种小批量离散性制造企业对生产调度管理软件的迫切需求,开发了基于多Agent的生产计划优化和车间智能调度系统。该系统可以处理并行车间的生产计划优化分配,以及加工时间模糊和交货日期模糊的不确定车间调度问题,提供遗传算法、神经网络方法、免疫算法等多种改进智能优化调度算法供用户使用。作为企业应用集成系统的一部分,该系统在浙江某电声企业中得到成功应用。最后,对全文研究工作进行了总结,展望了生产调度问题的进一步研究工作及应用前景。更多还原

【Abstract】 As the most weak and difficult chain in the production management, production scheduling has become the bottle-neck problem in the research on the computer integrated manufacturing system. Since 1950’s, many significant results have been presented in production scheduling problems widely studied on. However, there are still no systemic theories and methods used to solve the problems due to the difficulties. For many years, the researchers and personnel in the enterprises have fixed attention on the issue how to combine the classical scheduling theories with the actual production to improve the accuracy, validity, and real time performance of the production control for the enterprises. Because a multi-agent system is made up of the autonomous agents that collaborate and cooperate dynamically to solve the problem. The autonomous, distributed and dynamic features of the multi-agent system can fit the requirement of the complex, flexible, robust and dynamic manufacturing scheduling. Consequently, the multi-agent system is a good method to solve the above problem. The multi-agent production scheduling system model and everal job-shop scheduling methods were mainly investigated in the dissertation, such as the improved static methods based on Hopfield neural networks and the immune algorithm, and the multi-agent dynamic method. The main contributions of the paper are as follows:(1) The research background and significance of the thesis was introduced, and the description and categorization of production scheduling problem were given. Based on summing up a large number of domestic and foreign literatures, related research work on the problems was focused on summary, and the existing problems in the production scheduling research was analyzed.(2) Aiming at the complex production scheduling problems in the uncertain and dynamic manufacturing environment, and especially the short-term, agile and dynamic scheduling problems, the production planning and shop scheduling system model based on the multi agents was built, where the functions of management agent, resource agent, task agent and computation agent were given. The negotiation of the improved contract-net protocol among the agents was proposed in production planning optimization assignment for parallel shops of the enterprise. The realization of the multi-agent planning optimization model was given, and the simulation experiment approved the validity of the model.(3) Because the job-shop scheduling method based on Hopfield neural network is apt to search infeasible solutions, discrete Hopfield neural network (DHNN) method with the operation representation was presented, and the new energy function consisting of row inhibition, column inhibition, global inhibition and objective inhibition was given. So the neural network would rapidly convergence to a feasible solution satisfying with resource and sequence restrictions. In order to search the global solution, the discrete Hopfield neural network with transient chaos method for the job-shop scheduling was developed, where the simulated annealing mechanism was introduced into DHNN. The simulation results of benchmark problems show that its optimization performance was better than the other methods mentioned. In addition, the improved neural network optimization methods were applied to solve an actual scheduling problem from a machinery factory.(4) Based on the adaptive mechanism of bacterin extraction and vaccination, the adaptive immune algorithm for the job shop scheduling was presented. And then its optimization performance, bacterin extraction and vaccination methods, and coding modes were analyzed in the simulation experiments. In order to improve the performance of the algorithm, the immune evolution algorithm based on the multi-agent system was developed. It mainly consisted of several operators: competition operator among the agent and its neighbors, self-study operator of the optimal agent, adaptive bacterin extraction and vaccination operator, cross and mutation operator, and simulated annealing operator. The position of the agent was updated with those operators in the solution space, and thus it would accurately search the global optimal. Then, based on the actual production features of paper basin shops, the model of the fuzzy and flexible job-shop scheduling problem with various batches was given. Finally, the multi-agent immune algorithm was applied to solve a scheduling example from a certain paper basin shop, and the results showed its validity.(5) The coordination mechanism based on ant intelligence and reinforcement learning was developed for the dynamic manufacturing environment, where the adaptive agent was built to realize the dynamic scheduling of jobs. The example simulation showed that the method was effective in the changeable environment of orders and machines. Based on the techniques and restrictions of printing and dyeing production process, the dyeing shops scheduling problem model was built, and then the multi-agent dynamic scheduling method of dyeing shops scheduling was also presented. The scheduling example proved that the adaptability of the method for the changeable production environment.(6) Based on the above-mentioned academic research, an intelligent production planning and shop scheduling system based on the multi agents was developed to satisfy with the urgent requirement of the enterprise production management. The system was based on the classical production and management features of discrete manufacturing enterprises whose production mode was order-production, multi-varieties and small batch. The system supported the plan optimization assignment of parallel shops and the uncertain job shop scheduling with fuzzy processing time and fuzzy due date, and provided the intelligent scheduling methods, such as genetic algorithms, neural networks, immune algorithms, and so on. As a subsystem of the integrated application system for the enterprise, it was successfully applied to a certain electroacoustic enterprise in Zhejiang province.Finally, the whole research work of the dissertation was summarized, and the future of production scheduling problem research and its application was given.更多还原