【作者】 万芳；

【导师】 陈炼；

【作者基本信息】 南昌大学 ， 计算机软件与理论， 2005， 硕士

【摘要】 随着市场竞争的日趋激烈,每个企业都在寻求更好的生产与运作管理方案,以提高企业的生产、经营和管理效率,从而提高企业的核心竞争优势。生产与运作管理的核心是车间作业调度问题能否高效地获得优化解,因此,研究车间作业调度问题具有很大的理论意义和现实价值。 论文给出了车间作业调度问题的定义,分析了车间作业调度问题的特点及意义,探讨了车间作业调度问题的可计算性和复杂度,回顾了研究求解车间作业调度问题的主要历程及其方法。 详细介绍了车间调度问题的目标、类型及研究现状,就两类调度问题—流水型调度问题与非流水调度问题分别讨论了解决方案。先讨论了两种调度问题的数学模型与相关算法,包括传统单一的启发式算法和遗传算法。着重研究了非流水型作业调度问题的现状和该类问题的数学模型,并对相关算法,如启发式方法、进化算法、领域搜索方法等进行了讨论。 本文在车间调度领域中其他学者的研究成果的基础上,改进了基于标准遗传算法的结合启发式规则的混合算法,分别就编码方式、交叉算子、变异算子的不同形式对优化结果产生的影响,进行了分析与研究。 本文结合作业排序中的启发式规则(SPT优先选择最短加工时间的工序,MWR优先选择剩余总加工时间最长的工件的工序)和遗传算法提出一种新的混合遗传算法。分析了基于遗传算法的调度优化策略和相应的结构流程。算法先利用启发式作业调度规则将问题的解空间缩小至某个包含高性能解的子空间,再进行遗传搜索,寻找最优解。 最后给出了启发式遗传算法的JSP调度算法设计与软件实现,并对算法复杂性和收敛性进行了分析。更多还原

【Abstract】 With the increasing keen market competition, each enterprise looks for better solutions to production and operation management aiming at improve the core competitive advantage.The key to the management of production and operation management is to achieve the optimal solutions.Therefore, the study of Job shop scheduling is of great significance.The paper presents the definition of Job shop scheduling problem and analyzes the characteristics and discusses the computational complexity. Meanwhile, it reviews the main procedure and research ways of Job shop scheduling problem.Based on the previous research by scientists in JSP field,the paper also introduces the object to Job shop scheduling problem of its kind and research status quo. It deals with the mathmatical models and relevant algorithms respectively: heuristic and genetic algorithms. First, it focuses on the study of relevant algorithms such as evolutional algorithms and researching. Secondly, the research of adjusted algorithm based on standard genetic algorithm is studied.The paper proposes a hybrid algorithm based on standard genetic algorithm with heuristic rules (shorest processing time and most work remaining) and discusses the effect on optimal results by making use of the various coding, crossover operators and mutation operators. Then we make an introduction to scheduling optimal strategies and procedures.The algorithm diminishes the searching space by using heuristic rules remarkablely. It is easier and quicker to find the optimal results than the standard one.Finally, the paper offers the design and realization of JSP algorithm and discusses its complexity and convergence.更多还原