基于微粒群算法的车间调度问题研究

【作者】 常桂娟；

【导师】 张纪会；

【作者基本信息】 青岛大学 ， 系统理论， 2008， 博士

【摘要】 随着社会经济的飞速发展,市场竞争日趋激烈,顾客需求的多样化、个性化增加了企业生产计划运行的不确定性和动态性因素,使得现代企业面临着严峻的挑战,对供应链的管理也提出了更高的要求。进入20世纪90年代以来,供应链管理成为当今国际上企业管理理论研究和实践应用的一个热点。在此环境下,为了提高盈利水平和核心竞争力,企业开始注重合理配置和高效利用自己的内外资源。基于供应链的调度模型将供应链管理和生产调度问题紧密结合起来,研究在供应链管理的环境下如何更有效地解决分布环境下车间生产调度与协调问题,最终实现节点企业供应链管理与车间调度的双重优化,从而具有一定的理论价值和实际意义。微粒群优化算法是一种新型的群体智能算法,源于对鸟群捕食行为的研究,是一种基于迭代的优化技术。系统初始化为一组随机解,通过迭代搜寻最优值。目前,微粒群算法已广泛应用于函数优化、神经网络训练、数据挖掘及其它应用领域。本文围绕着微粒群算法及其应用,就如何改进传统微粒群算法性能及该算法在车间调度、供应链调度领域的应用展开了深入研究。首先介绍了本文的研究背景及目的意义,给出了车间调度问题的分类、特点以及近年来研究车间调度问题的主要方法。其次介绍了遗传算法及其在车间调度问题中的应用,并引入正交试验来确定算子,提出了基于正交试验的免疫遗传算法并用该算法求解作业车间(Job-Shop)调度问题,通过比较得到了令人满意的仿真结果。然后对微粒群优化算法的现状及未来研究方向进行了描述,给出了微粒群算法在车间调度问题中的应用,使用了基于粒子坐标值排列编码,通过与遗传算法比较,仿真实验表明了微粒群算法在求解作业车间调度问题的优越性和有效性。接下来介绍了供应链和供应链管理的概念及特征,给出了在供应链环境下生产系统的协调控制及车间调度问题。文章最后描述了无等待供应链在线调度问题,提出了基于最小位置值排列编码方法,在不改变已有工件调度的情况下,对顾客下达的紧急订单尽早制定生产方案。在流水车间(Flow-sbop)及作业车间调度问题背景下,给出了求解在资源可用时间区间上在线调度紧急订单的算法,使用该算法可以迅速求出订单完工时间并通过电话或互联网将交货期反馈给顾客,对制造商的实际生产供应链管理具有一定的指导意义。更多还原

【Abstract】 With the fast development of social economy,competition in the market becomes increasingly intense.The diversification and customization of the customers’ need increase the uncertainty and dynamism in the production plan of the enterprise,making the modern enterprise face severe challenges and making greater demands of the supply chain management.After entering the 1990s,the supply chain management already becomes one of the focuses in the study and practice of the enterprise management theory and practice in the international society.In the circumstances,in order to improve the profit level and the core competitive ability,the enterprise begins to focus on rationally allocating and efficiently utilizing its inner and outer resources.The scheduling model study based on the supply chain combines the problem of the supply chain management and the problem of the production scheduling to study how to more effectively solve the job-shop scheduling and coordination problem in the distributed environment,and ultimately realize the double optimization of the node enterprise’s supply chain management and the job-shop scheduling,boasting certain theoretical and practical significance.Particle Swarm Optimization,a new swarm intelligence algorithm,originates from the investigation of the bird swarm preying behavior.It is an optimization technology based on iteration.System is initialized into a group of random solutions and optimization value is searched by iteration.Now,particle swarm optimization is applied into function optimization,neural network training,data mining and other application field.The paper focuses on the algorithm and application of the particle swarm and makes deep study on improving the property of the traditional particle swarm algorithm and on the application of the algorithm in the fields of the job shop scheduling and the supply chain scheduling.The background,aim and significance of the paper are introduced first, followed by the classification and characteristics of the job shop scheduling,as well as the major ways of studying the job shop scheduling problem.Then,the paper describes the genetic algorithm’s application in the job shop scheduling problem.The orthogonal experiment is introduced to identify the operators,and the immune genetic algorithm is put forward on the basis of the orthogonal experiment to solve the job shop scheduling problem with the algorithm,achieving a satisfactory simulation result by comparison. After it,the paper describes the present status and the future trend for study of the particle swarm optimization algorithm.The application of the particle swarm algorithm is given, using the coding method based on particle position.Through the comparison with the genetic algorithm,the simulation results show the superiority and effectiveness of the particle swarm algorithm in solving the job shop scheduling problem,followed by the introduction of the definition and characteristics of the supply chain and the supply chain management.Coordinated control and shop scheduling problem in supply chain are given. At last,the on-line no-wait scheduling in the supply chain is studied.The coding method of the smallest position value is used in this thesis.The production plan will be made to the customer’s urgent order without changing the scheduled jobs’ processing orders.In the background of flow shop and job shop scheduling,the paper gives the algorithm to on-line schedule the urgent order in a certain time interval when resources are available. Making use of this algorithm will obtain the completion time of the order in no time,and propose a delivery time on the phone or on the Internet.It is of certain guiding significance to the manufacturer’s practical production supply chain management.更多还原