并行遗传算法在车间作业调度问题上的应用

【作者】 檀壮；

【导师】 刘希玉；

【作者基本信息】 山东师范大学 ， 管理科学与工程， 2007， 硕士

【摘要】 车间作业调度(JSSP)在企业生产经营活动中占有十分重要的地位。生产调度系统也是CIMS、ERP等系统中的重要组成部分。生产调度位于CIMS体系结构中的中间层,是控制与管理一体化的接合部。向上要给企业经营战略决策层提供决策依据,向下要安排生产加工任务,指导监督控制层的动作。因些,生产调度是实施CIMS的关键。由于车间作业调度问题是一个典型的NP-hard问题,因此受到学术界和工业界的广泛关注。对它的研究具有很高的理论意义和实际意义。迄今为止,已有很多关于车间作业调度问题的研究方法,如分枝定界法、基于优先规则的启发式方法,但是常见的JSSP的困难性和复杂性使传统的搜索方法很难在合理的时间内找到最优解。近年来,已经引进了一些人工智领域的新技术来解决这些问题,如模拟退火(SA)、禁忌搜索(TA)、人工神经网络(ANN)、遗传算法(GA)等等。遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法,其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法的这些性质,已被人门广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。并行遗传算法(PGA)是过去十几年以来GA研究的热点之一,无论是理论还是应用上都取得一些成熟的成果。因此本文将PGA用于求解JSSP调度问题,本文主要有以下几项内容:(1)介绍分析了车间作业调度的问题描述、模型表示、特点以及对它的研究方法和研究现状。本文将JSSP的研究方法分为两大类,最优化方法和近似/启发式方法;(2)作为并行遗传算法的基础,介绍了标准遗传算法的来源,生物学方面的背景,编码方式,适应度函数,基本遗传操作(选择、交叉、变异),基本参数的设置原则;(3)介绍了并行遗传算法的分类,以及他们各自发展的历史现状,粗粒度并行遗传算法的迁移策略,分为两种同步迁移和异步迁移;(4)详细介绍了针对JSSP的特点设计的新的粗粒度并行遗传算法,主要包括算法流程,编码方式,遗传操作,迁移策略。最后,对两个经典的JSSP的实例即FT6×6、LA01,进行了仿真实验。通过对结果的分析,得出设计的新算法比普通的遗法效率高的结论。更多还原

【Abstract】 Job-shop scheduling plays a great role in the production activity of an enterprise, job-shop scheduling system is also a great part of CIMS or ERP. Production scheduling is at the middle layer in the CIMS system structure, which is the joint of control and management. On one hand, it will supply decisions for the enterprise; on the other hand, it will arrange production tasks and supervise the control layer. So the production scheduling is the key of the CIMS. JSSP is a typical NP-hard problem, so it attracts great attention from both the academia and industry. Therefore, the study of job shop schedule is of great theoretical and practical importance.So far there have been many research methods to deal with JSSP, such as branch-bound method and some heuristic procedures based on priority rules, but the difficulty and complexity of general JSSP makes it very hard for the conventional search-based methods to find an optimal solution in reasonable time. New techniques emerging from the field of artificial intelligence have been introduced to address these problems in recent years, such as simulated annealing, tabu search, artificial neural network and genetic algorithm , and so on .The Genetic Algorithm (GA) is a random search method imitating the rules of the organic world. The main distinguishing feature are as following: operating on the composition target, requesting no guide and function continuance; having conceal concurrence and splendid capability with the better situation as a whole; adopting approximately the guiding of the most splendid means of leading, being able to gain voluntarily and the searching room the direction optimizes, self-adopting the regulation direction of search, not needing certain regulation. The features of GA have been widely used applied in territories such as optimization, machine learning, treatment of signal, self-adoption control, artificial existence and so on.Parallel Genetic Algorithm (PGA) is one of the research focuses of GA from past 10 years, and has improved a lot both in theory and application. This paper use PGA to solve JSSP scheduling problem, and the main content is as following:(1) Introduce and analyze some aspects about Job-shop scheduling problem, such as description of the problem, expression of the model, features and main research methods on JSSP. This paper divide all the methods into two classification, optimization method and heuristic procedures;(2)Introduce the Simple Genetic Algorithm as the foundation of PGA, such as following aspects: SGA’s origin, background about biology, encoding methods, function, basic genetic operation(selection、crossover、mutation), and the regulation about the initialization of the basic parameters;(3)Introduce and analyze Parallel Genetic Algorithm, classification and status quo on research, transferring methods of CPGA, synchronous and asynchronic;(4)Introduce detailedly the new algorithm of CPGA aim at the features of the JSSP, include encoding methods, genetic operations, transferring methods. At last, implement the emulational experiment on the two typical examples of JSSP, FT6×6、LA01. The result prove that the new algorithm is better than the general GA.更多还原