1、基于遗传算法的作业调度优化研究摘 要在现今的经济全球化制造时代，客户化的产品需求要求更短的产品生命周期。现代制造业与服务业呈现融合的状态。车间作业调度技术是生产管理技术的核心技术，直接关系到企业产品以及服务的质量。有效的车间作业调度技术，可以增强车间资源优、化配置能力、提高企业的生产效率、减少生产损耗，使企业在经济全球化的竞争中处于领先地位。现代制造业的生产特点是品种多、批量小(甚至是单件生产)，而车间资源的有限性制约着能否有效利用车间现有资源完成任务，以最快的速度响应市场需求。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统
2、的最优性、提高经济效益都有着极大的作用。作业车间调度问题是一个典型的NPhard问题，是最困难的组合优化问题之一。本文主要研究了制造车间作业调度问题。本文系统地介绍了车间作业调度理论及其发展状况、用于作业车间调度理论的优化算法及其特点；针对生产过程的作业调度，描述了调度的分类以及常规调度方法；建立了制造车间调度模型；利用染色体编码方法和遗传算子，用遗传算法解决该调度问题。此外，用Matlab强大的数值计算能力和众多库函数来编写算法，通过仿真实例对算法的求解效果进行了测试。实例证明，该程序算法结果较好，能充分利用设备资源组织生产，对于车间的实际生产具有较强的指导意义。关键词：作业调度，遗传算法，
3、MATLABJob Scheduling Optimization Based on Genetic AlgorithmABSTRACTIn the manufacturing era of economic globalization, demand for our products of customer requires shorter product life cycle. Modern manufacturing and service rendered to the state of integration. The job-shop scheduling technology i
4、s the core technology of the production and management technology, is directly related to the quality of enterprise products and services. Effective job shop scheduling techniques can enhance the workshop resources, optimal allocation of capacity, improve production efficiency, reduce production los
5、ses, so that enterprises can locate in the central position in the competition of economic globalization.The feature of modern manufacturing sector is variety, small batch (or even a single piece production). The limited resources of the workshop restricting the effective use of existing workshop re
6、sources to complete the task to meet market demand in the fastest pace. The scheduling task is to determine the specific processing route, time, machinery and operation according to production goals and constraints for each processing object. Good scheduling strategy has a great role for the optimal
7、 production system, improve economic efficiency. The job shop scheduling problem is a typical NP-hard problem,and is the most difficult combinatorial optimization problems.In this paper, we study manufacturing job shop scheduling problem. The paper systematically introduces the job shop scheduling t
8、heory and its development, optimization algorithm for job shop scheduling theory and its characteristics; contrary to job scheduling of the production process, we describes the classification of scheduling and conventional scheduling methods; we have established a manufacturing shop scheduling model
9、; we use chromosome coding, genetic operators and genetic algorithm to solve the scheduling problem. In addition, using the Matlab numerical computing power and number of library functions to write the algorithm to test the effects of algorithm by simulation examples. Examples show that The program
10、algorithm is better, equipment of organizing production resource utilization, The algorithm has a strong guiding significance for the actual production of the workshop.Keywords: Job Scheduling, Genetic Algorithm, MATLAB1 绪论1.1 课题研究背景及意义1.1.1 问题的提出随着科学技术、经济全球化和信息技术的迅猛发展，生产企业面临着多变的商业环境1。现代科学技术的快速发展和客户
11、对产品的个性化需求越来越高，这给传统制造加工业带来了巨大的挑战和机遇。原来简单的、局部的、常规的计划和仅凭经验的管理已经不能满足现代化的要求。当前的机械制造企业采用多元化、多品种、小批量、高柔性生产方式来适应激烈的市场竞争。制造业的经营重心已从企业规模和产品成本转移到用户需求和上市时间、产品质量、制造成本和售后服务。制造过程中的生产管理与调度是保证生产质量和生产效率的关键，先进的生产管理与调度技术能够快速响应顾客需求变化的多样性。为了保证生产的高效稳定运行，以获得最大的经济效益，企业管理者必须能根据市场上原料供应和产品需求的变化进行经营决策和组织生产，能利用现有的资源做出最有效的调度方案，使企
12、业生产获得最大的综合经济效益。21世纪企业的先进制造模式是完全面向顾客，敏捷制造是综合了JIT（Just In Time）、并行工程、精益生产的先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品。对于中小型企业来敏捷制造就是先进的生产模式，生产调度方案的优劣是敏捷制造的标志。在这种生产模式下如何进行组织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行调度是企业面临的主要问题。其中车间调度与控制技术是实现生产高效、高柔性和高可靠性的关键。有关资料表明，在制造过程中95的时间消耗在非切削过程中。因此，有效的调度方法和优化技术的研究和应用，是实现产品高质、低耗，进
13、而使企业赢得市场竞争的有力武器2。1.1.2 课题的现实与理论意义车间作业调度问题(Job-Shop Scheduling Problem，JSP)的求解目标是寻求某种最优策略，找到的调度方案能将加工作业安排到车间制造机器上，并且使加工作业能够最高效的完成。每个作业都由一些工序组成，而每个工序则必须由指定的机器加工处理。一个调度方案就是按照作业内在逻辑的先后顺序条件将所有工序安排到机器上的一种方案。以前大部分企业主要依靠经验丰富的工人手工安排调度计划，在调度问题比较简单的情况下还是可行的。然而，当前的产品的加工工艺复杂度相当高，在调度任务规模较大且动态多变的环境中，手工调度表现的非常低效甚至无
14、法实现调度。1973年harrington博士提出计算机制造集成制造CIM的概念，CIM是一种组织、管理与运行企业生产的新哲理，它借助计算机软件、硬件，综合运用现代管理技术、制造技术、信息技术、自动化技术、系统工程技术，将企业生产过程中有关人、技术、经营管理三要素及其信息流与物质流有机地集成并优化运行34。计算机集成制造系统(CIMS)能给企业带来巨大的综合经济效益，因此国内、外各大中型企业都研究与实施计算机集成制造系统。作为实施CIMS工程中的一个重要组成部分，生产计划与调度系统是计算机集成制造系统功能结构模型中不可缺少的一个层次。当前在自动化程度较高的生产系统中，使生产过程合理、高效运行的
15、调度问题变得非常复杂，需要建立有效的计算机调度控制策略、因此调度问题的研究具有重要的现实意义。由于大量的调度问题是NP完全问题13，近几年各种智能计算方法逐渐被引入到调度问题中，如遗传算法、模拟退火算法等，但是目前尚无有效的求解策略，因此调度问题的研究也具有重要的理论意义5。车间作业调度是一个交叉的研究领域，以数学为基础，涉及运筹学、计算机、控制工程和工业设计等多门学科。具体就是针对一项可分析的工作（如产品制造），探讨尽可能满足约束条件（如交货期、工艺路线、资源情况）的前提下，通过下达生产指令，安排其组成部分（操作哪些资源）、其加工时间及加工的先后顺序，以达到合理利用产品制造资源，获得产品制造
16、时间和成本的最优化14 ，提高企业经济效益的目的。制造系统生产管理的核心就是车间生产调度，生产管理任务顺利实施与完成，最终要靠合理的生产调度来保证。它研究的是如何合理地配置加工过程的各种资源，减少零件在加工过程中的各种浪费，从而提高设备利用率和生产率，降低生产成本。因此，合理的生产调度是生产系统的高效运行的前提，生产调度可以保证:生产计划的有效实施；高效低耗地使用生产资源；均衡生产，减少在制品的资金占用；缩短产品生产周期、确保产品交货期、降低生产成本，以适应多变的市场需求。生产调度对企业来说是至关重要的，在品种多、中小批量生产环境下的主生产调度问题更加复杂和重要12。1.2 国内外研究现状综述
17、车间作业调度问题是一个经典而又传统的问题，对于它的研究始于20世纪50年代。1954年，Johnson对两台机床Flow-Shop型调度问题进行了研究后，提出了解决车间调度部分特殊问题的优化算法，代表理论研究的开始。60-70年代都是利用混合或纯整数规划、动态规划和分枝定界法解决一些有代表性的问题，并开始重视调度复杂性的研究。由于车间调度问题的复杂性，各种不同的具体问题往往有不同的解决方法。大量的研究促使车间调度领域取得了丰硕的成果，产生了很多重要的调度方法。随着70年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出了许多新的车间调度理论与方法，如：基于运筹学（OR）方法6、基于控制的方
18、法、基于DEDS（离散事件动态系统）的解析模型方法、模拟退火法，启发式算法10，禁忌搜索法7以及拉格朗日约束松弛法8等，代表着经典调度理论趋向成熟。90年代至今，随着计算机应用技术的发展，各种方法在车间调度问题的研究中得到了充分的发挥，同时新的研究手段层出不穷，人工智能、人工神经网络、基因遗传算法的作业调度方法等被广泛用于Job-shop调度问题的研究。Davis是最早把遗传算法应用于车间调度问题的学者之一，他在使用GA求解车间调度的问题的研究中取得了近似最优解。遗传算法的优越性主要表现在搜索过程中不易陷入局部最优，即使在所定义的适应度函数不连续的情况下，也能以极大的概率找到最优解9。此后，很
19、多学者就遗传算法在车间调度问题方面的应用做了大量研究。1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了Genetic Programming(简称GP)的概念，Koza成功地将他提出的遗传编程方法应用到了人工智能、机器学习、符号处理等方面，进一步证明了遗传算法在解决NP问题方面的有效性11。国内对于车间调度问题的研究起步比较晚，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在作业调度方面的应用，国内也掀起了一股应用遗传算法研究车间作业调度问题的热潮。目前,研究工作主要集中在清华大学等CIMS(Computer Integrated Manufacturi
20、ng System)国家重点实验室，这些实验室的系统开发基本上还处于试用阶段，距离开发出成熟的软件系统还有很长一段距离，因此还需要投入大量的人力物力进行该方面的研究。1.3 本文的研究内容本文针对先进制造环境下车间管理与调度的特点，分析了车间作业调度的特点，给出了遗传算法求解车间作业调度的过程。通过研究与分析车间作业调度系统，给出了调度的数学模型，运用Matlab遗传算法工具箱进行了仿真调度，并分析了结果。本文主要分五章，具体安排如下：第一章说明了课题的提出背景和研究意义，讨论了车间调度的国内外研究现状，最后给出了本文的研究内容和文章的结构安排。第二章详细阐述了车间作业调度问题，分析了调度模型
21、及模型描述，总结了车间调度的求解方法。第三章简要说明了遗传算法的产生、发展、特点及操作流程。重点研究了遗传算法在车间作业调度优化中的操作过程，包括了编码方式、种群大小、交叉方式与概率、变异方法与概率等参数的选择。第四章将实际的车间作业问题抽象成数学模型，并且设计遗传算法的基本算子以及操作。第五章运用Matlab遗传算法工具箱，通过编码实现模拟作业调度。并且分析结果的可行性，运行时间以及目标值。2 车间作业调度算法2.1 调度问题特点与分类调度问题的主要特点有:(1)建模、计算复杂性。车间中工件、机器、操作人员和搬运系统之间相互影响、相互制约。每个工件又要考虑它的加工时间、安装时间和操作顺序等因
22、素，因而相当复杂，调度问题往往是通过等式或不等式等约束条件来计算的，属于典型的NP-hard问题。随着问题规模的加大，计算量也急剧加工，所以调度问题往往没有精确的解，通常是在解答过程中寻求其最优解。在现有计算条件下，一般优化方法对于车间调度问题是低效甚至是无能为力的。(2)动态随机性调度中存在很多随机性和不确定性。如机器故障、作业交货期的变更，如工件到达时间的不确定性，实际工件的加工时间也有一定的随机性。如机器故障、紧急任务插入、作业交货期的变更等一些突发事件也增加了调度的难度和随机性。(3)多约束性调度中受到很多约束条件的限制。车间的生产能力不仅会受到机床的制约，还会受到工人和辅助工具的制约
23、，各道工序的先后关系不能颠倒，如缓存容量、资源数量、工件到期时间与操作顺序等也是制约因素。此外，还有人为的附加因素，如机器负荷平衡等等约束条件。(4)多目标性调度的目标很多，目标之间往往又相互冲突。如基于作业交货期的目标、基于作业完成时间的目标、基于生产成本的目标等。按照不同的分类标准，可分为6种类型:(l)开环车间和闭环车间;(2)单台处理机、多台并行机、Jobshop和Flowshop;(3)基于调度费用和调度性能的指标;(4)确定性调度、随机性调度;(5)静态调度、动态事实调度;(6) 有序加工，无序加工。现代车间调度类型往往是Job-shop、Flow-shop型。2.2 车间作业调度
24、问题描述一般车间调度问题可以描述为:n个工件在m台机器上加工，每个工件分为k道工序，每道工序可在不同的机器上加工。每一台机器在每个时间只能加工某个工件的某道工序，只能在上道工序加工完成才能开始下一道工序的加工，前者称为占用约束，后者称为顺序约束。调度的结果就是确定决策方案，决策内容包括分配决策(工件的加工顺序)和时间决策(工件各工序的加工时间)以及路径决策(工件工序的加工设备的分配)。生产车间出现调度问题主要原因是生产资源受到了制约。车间调度的问题是多个工件在有限的机器上加工，每台机器在切换不同的工件加工时又需要一定的生产加工准备时间。切换加工的次数越多越有利于减少工件的库存，但导致生产率的下
25、降。如果车间有足够多的机床设备和其它生产资源分配给每个工件或每条工艺加工路线，那么一切都会井然有序，也就不存在调度问题。但是，对于企业主来说，这样必定会造成资源浪费和制造成本的增加，于是出现了工件和相应的工序数量多于生产资源的情况，也就出现了车间调度问题。因此，需要在库存成本与切换加工次数频率之间寻求一个动态的平衡。生产的柔性体现在设备的使用和设备的安排两个方面，设备使用的柔性是指设备可用于多个零件的多道工序加工，设备安排的柔性是指工件的设备加工路径，而不是固定或预先确定的。具有可选的路径，可以通过将若干设备组作为一条或者多条生产线加工一种工件，使得该工件的生产率最大。典型的车间调度问题包括一
26、个要完成的作业集(工件集)，每个作业由一个操作集(工序集)组成，各操作的加工需要生产资源(机器、人员、刀具和辅助资源)，并且必须按一些可行的工艺次序进行加工。车间调度就是对一个可用的加工机床集在时间和空间上进行加工任务集分配，以达到生产性能指标最优化。每台机床可加工工件的若干操作，并且在不同的机床上能加工的操作集可以不同。调度的目标是将作业合理地安排到各机床以及合理地使用其它生产资源，并合理安排作业的加工次序和加工时间，使约束条件被满足，同时优化其中的一些生产性能指标。2.3 调度问题优化算法目前的车间调度问题的算法研究有很多，归纳起来主要有:（1）确定性最优化方法该方法主要通过对车间调度问题
27、建立一个数学模型，采用基于枚举思想的分枝定界或动态规划法进行求解，分枝定界法有很多，其主要不同点在于分枝规则、定界机制和上界的产生等三个方面的差异。这类方法从理论上来说是能求得最优解，但通常由于计算复杂性原因，不能获得真正的实用。采用数学规划的方法，表达清晰，易于在计算机上求解，但生产环境具有很多不确定的因素，存在建模不确定性和求解空间太大，造成计算困难，特别是不能反映特定调度领域的自然结构，所以很难应用经验知识去处理调度问题。采用数学规划的方法大致可以分为三类：简单规则、复合规则、启发式规则。（2）基于启发式规则的调度方法最早的近似算法便是基于启发式规则的调度算法(也称调度规则)，其本质是给
28、每一个生产任务和操作，并赋予优先级，优先级高的生产任务和操作优先考虑。这类方法因调度规则易于实现，计算复杂度低，能够用于动态实时调度系统中，许多年来一直受到广泛关注和研究，并不断涌现许多新的调度规则。如作业的平均等待时间、机床的平均利用率、作业总加工时间等。（3）基于知识的调度方法近年来受实际需要的推动，基于知识的智能调度系统和方法的研究取得了很大的进展，基于只是的调度方法是用专家系统自动产生调度或辅助人去调度，它是传统的调度方法与基于知识的调度评价相结合的方法。在八十年代后期，几位学者先后开展了基于调度系统处于不同状态，采用不同的调度规则策略的动态调度方法的研究，其共同特点是:在支持某些活动
29、发生的资源条件具备时(称为决策点)，根据系统当时所处的属性转台，决定采取何种规则(策略)，确定或选择活动发生的顺序和时间，即所谓的状态指导的智能调度方法。（4）仿真调度方法由于制造系统的复杂性，很难用一个精确的解析模型来进行描述分析，而通过对仿真模型的运行收集数据，就能对实际系统进行性能，状态方面的分析，从而能对系统采用合适的控制调度方法。Alis.Kiran等回顾和总结过在动态环境下基于纯仿真模型的Job-shop调度问题的研究状况。该方法不可避免存在以下问题:a)缺乏理论意义;b)应用仿真进行生产调度的费用很高;c)仿真的准确性很大程度受编程人员的判断和技巧的限制。（5）基于DEDS的解析
30、模型方法现实中的制造系统往往是离散事件系统，因此可以用研究离散事件系统解析模型和方法探讨车间调度问题，诸如排队论、极大极小代数模型、Petri网等，。比如，Petri网作为一种图形建模工具可以形象地表示和分析FMS（柔性制造系统）中加工过程的并发和分布本质，以及多项作业共享资源时的冲突现象。Petri网具有很强地建模能力，对于描述系统的不确定性和随机性也具有一定地优越性，目前Petri网已经用于FMS建模和调度，但尚存在下列问题:l)节点语义的单义性，使得所携带的系统信息量不够丰富。2)重用性差。Petri网是基于FMS中作业的加工流程建模，当作业需求或工艺稍微变动，必须改模型结构。3)很难对
31、高级的调度规则建模。（6）启发式图搜索法在人工智能中启发式图搜索法是图搜索的重要策略之一，在启发式图搜索法中最引人注目的A*算法，在图搜索过程中A*算法能够通过选择合适的评价函数寻找达到目标结点的最佳路径。在调度问题的离散图模型基础上，启发式图搜索法在调度领域得到应用。对于表述为整数规划的调度问题，最初采用分枝界定法，而后其他的启发式图搜索法也被应用于解决调度问题。该方法主要需要解决搜索效率和降低内存使用问题，对大规模的问题需进一步探讨。（7）模拟退火模拟退火法（SA）是将组合优化问题与统计力学的热平衡问题类比，通过模拟退火过程，可找到全局(或近似)最优解。模拟退火法的改进算法有加温退火法、记
32、忆退火法。模拟退火法可以用于具有最小MakesPan指标的FlowShop排序问题。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的收敛速度较慢，很难用于实时动态调度环境。（8）禁忌搜索法对于复杂的组合优化问题，禁忌搜索也是一种通过领域搜索以获取最优解的方法，Gfover首次叙述了它的基本原理。该方法已经用于解决now-shop调度问题。（9）神经网络优化人工神经网络(ANNs)是一种模拟人脑神经系统的结构和功能，运用大量的处理部件，经广泛互连而组成的网络系统。搜索网络（Hopfield）模型可以求解各种有约束的优化问题，随机Hopfield也可以用于解决job-shop的调度问题。（10）拉格朗日(LR)松弛算法LR算法由于其在可行的时间里能对复杂的规划问题提供较好的次优解，并能对解的次优性进行定量评估，近年来已成为解决复杂生产调度问题的一种重要方法。但同时LR算法的对偶问题存在搜索效率低，可行调度的构造有待于进一步研究等问题。由于调度问题的复杂性，其研究策略主要形成了以下几种：分解与成组策略：利用分解生产计划或GT的调度策略可以大大降低问题的计算复杂性和规模，求得调度问题的较优解，同时优化系统的一些性能指标。实
