1、基于遗传算法求解作业车间调度问题基于遗传算法求解作业车间调度问题摘 要作业车间调度问题(JSP)简单来说就是设备资源优化配置问题。作业车间调度问题是计算机集成制造系统(CIMS)工程中的一个重要组成部分，它对企业的生产管理和控制系统有着重要的影响。在当今的竞争环境下，如何利用计算机技术实现生产调度计划优化，快速调整资源配置，统筹安排生产进度，提高设备利用率已成为许多加工企业面临的重大课题。近年来遗传算法得到了很大的发展，应用遗传算法来解决车间调度问题早有研究。本文在已有算法基础上详细讨论了染色体编码方法并对其进行了改进。在研究了作业车间调度问题数学模型和优化算法的基础上，将一种改进的自适应遗传
2、算法应用在作业车间调度中。该算法是将sigmoid函数的变形函数应用到自适应遗传算法中，并将作业车间调度问题中的完工时间大小作为算法的评价指标，实现了交叉率和变异率随着完工时间的非线性自适应调整，较好地克服了标准遗传算法在解决作业车间调度问题时的“早熟”和稳定性差的缺点，以及传统的线性自适应遗传算法收敛速度慢的缺点。以改进的自适应遗传算法和混合遗传算法为调度算法，设计并实现了作业车间调度系统，详细介绍了各个模块的功能与操作。最后根据改进的编码进行遗传算法的设计，本文提出了一种求解车间作业调度问题的改进的遗传算法，并给出仿真算例表明了该算法的有效性。关键词：作业车间调度；遗传算法；改进染色体编码
3、；生产周期Solving jopshop scheduling problem based on genetic algorithmAbstractSimply speaking, the job shop scheduling problem(JSP) is the equipment resources optimization question. Job Shop Scheduling Problem as an important part of Computer IntegratedManufacturing System (CIMS) engineering is indispen
4、sable, and has vital effect onproduction management and control system. In the competion ecvironment nowadays, how touse the assignments quickly and to plan production with due consideration for all concernedhas become a great subject for many manufactory.In recent years,the genetic algorithms obtai
5、ned great development it was used to solve the job shop scheduling problem early.This paper discusses the chromosome code method in detail based on the genetic algorithms and make the improvement on it. Through the research on mathematics model of JSP and optimized algorithm, theimproved adaptive ge
6、netic algorithm (IAGA) obtained by applying the improved sigmoidfunction to adaptive genetic algorithm is proposed. And in IAGA for JSP, the fitness ofalgorithm is represented by completion time of jobs. Therefore, this algorithm making thecrossover and mutation probability adjusted adaptively and n
7、onlinearly with the completiontime, can avoid such disadvantages as premature convergence, low convergence speed andlow stability. Experimental results demonstrate that the proposed genetic algorithm does notget stuck at a local optimum easily, and it is fast in convergence, simple to be implemented
8、. the job shop scheduling system based on IAGA and GASH is designed andrealized, and the functions and operations of the system modules are introduced detailedly. In the end ,according to the code with improved carries on the genetic algorithms desing, this paper offer one improved genetic algorithm
9、s about soloving to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid.Keywords: jop shop scheduling; genetic algorithm; improvement chromosome code; production cycl摘 要 IAbstract II1 绪论 11.1 课题来源 11.2 作业车间调度问题表述 11.3 车间作业调度问题研究的假设条件及数学模型 21.3.1 车间作业
10、调度问题研究的假设条件 21.3.2 车间作业调度问题的数学模型 31.4 课题研究内容及结构安排 42 遗传算法相关理论与实现技术 62.1 自然进化与遗传算法 62.2 基本遗传算法 72.2.1 遗传算法的基本思路 72.2.2 遗传算法的模式定理 72.2.3 遗传算法的收敛性分析 92.2.4 基本遗传算法参数说明 102.3 遗传算法的优缺点 112.3.1 遗传算法的优点 112.3.2 遗传算法的缺点 112.4 遗传算法的进展 122.5 小结 153 用遗传算法对具体问题的解决与探讨 163.1 研究过程中的几个关键问题 163.1.1 设备死锁现象 163.1.2 参数编
11、码 163.1.3 初始种群的生成 193.1.4 个体的适应度函数 203.1.5 算法参数 203.1.6 遗传算子的设计 213.2 遗传算法终止条件 243.3 遗传算法解决车间调度问题的改进 243.4 系统仿真 243.5 小结 29结 论 30致 谢 31参考文献 32附 录 331 绪论1.1 课题来源随着加入WTO，市场竞争越来越激烈，对制造企业来说，为了能够在竞争中立于不败，降低成本是不得不面临的问题，而确保生产车间较高的生产能力和效率，是当务之急。此外，有效的调度方法已经成为先进制造技术实践的基础和关键，所以对它的研究具有重要的理论和实用价值。当前科学技术正进入多学科互相
12、交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。虽然对其研究已有几十年的历史但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着较大距离。目前的调度算法大多只关心工件的调度问题，而对其它资源分配问题则研究相对不多，将二者结合起来研
13、究应该是值得注意的问题，目前已有不少学者开始关注该问题。由于一般车间调度问题的复杂性，各种不同的具体问题往往有许多不同的算法来解决，例如经典的启发式算法，传统的搜索方法等。由于遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法1。它特别适合于处理传统搜索算法解决不好的复杂和非线性问题。一些学者们经过大量的实践证明了遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式2。1.2 作业车间调度问题表述作业车间调度（job-shop）问题可以表述为：设有N个工件在M台
14、机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。前提假设3：1. 每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。2. 不同工件的加工工序可以不同；3. 所有工件的工序数不大于设备数；4. 每道工序必须在指定的某种设备上加工；5. 任何作业没有抢先加工的优先权；6. 在作业优化过程中既没有新的工件加入也没有取消的工件；调度问题具有相当的难度，目前调度问题的理论研究成果主要在job-shop问题为代表的基于最小完工时间的调度问题上。求解调度问题的方法称为调度优化算法。它可分为
15、精确求解方法和近视求解方法。其中精确求解方法包括解析方法、穷举方法（包括分支定界）等；近似求解方法包括基于规则的构造性方法、邻域搜索算法（如进化遗传算法，模拟退火算法）以及人工智能方法（如神经网络）4等。而传统的运筹学方法，即便在较大规模的基于单目标优化的静态调度问题中也难以有效应用。本文从实际和理论两方面进行研究和深入，重点研究了现代进化算法中有代表性发展优势的遗传算法。车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问
16、题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线5。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。 1.3 车间作业调度问题研究的假设条件及数学模型1.3.1 车间作业调度问题研究的假设条件在研究一般的车间作业调度问题中往往需要明确两类重要假设条件:1.工艺路径约
17、束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系;2.资源(机器)独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。此外，还有一些辅助假设条件，如下:1. 各工件经过其准备时间后可开始加工;2. 不考虑工件加工的优先权，即工件之间没有优先约束关系限制的;3. 工序允许等待，即前一个工序未完成，则后面工序需要等待;4. 所有机器处理的加工类型均不同;5. 工件的加工时间事先给定，且在整个加工过程中保持不变;6. 缓冲区容量为无穷大。1.3.2 车间作业调度问题的数学模型建立车
18、间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了基础。假设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。我们定义以下基本数学符号6：J:所有工件的集合，； M:所有机器的集合，；：工件Ji的工序集合，；P:所有工序的集合，此为矩阵。P（i，j）表示i工件的第j道工序。，表示i工件的所有工序按优先顺序的排列。不足，那么其空余的位置用0填满。（1.1）:机器顺序阵，此为矩阵。（i，j）表示i工件的第j道工序的机器号，表示i工件的所有工序按优先顺序加工的各机器号的排列。注意:如果某工件的工序数不足，那么其空余的位置用0填满。（1.2
19、）T:加工时间阵，此为矩阵。T(i, j)表示工件i的第j道工序在（i，j）上的加工时间。同样地，如果某工件的工序数不足，那么其空余的位置用0填满。（1.3） ：工件排列阵，此为矩阵。表示在i机器上排在第j位加工的工件号，表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数不足，那么其空余的位置用0填满。事实上，工件排列阵就是调度的一种表示形式。由此，我们可以给出一般性的车间作业调度数学模型的定义:如果对应于一个确定的，满足或。即使得目标函数取值最小(或最大)，且与相容，则称为车间作业调度问题在此目标函数下的最优解。生产调度问题存在多种优化目标或者综合优化目标，调度问题的优化目标通常从
20、两个方面来考虑:生产成本和生产时间。调度问题从生产成本方面来考虑，其优化目标有:库存最少、在制品最少、设备利用率最高等;从生产时间方面来考虑，其优化目标有:最大程度满足交货期、最小完成时间、最小流动时间和最小等待时间等。两个方向的优化目标之间彼此不是相互孤立的，其中的许多具体目标之间的联系很密切，有的相互促进，有的相互冲突，也有的毫无联系。1.4 课题研究内容及结构安排本文共分为三章。第一章简要介绍了车间调度问题和求解调度问题的基本方法；第二章介绍了遗传算法的基本理论；第三章用遗传算法来解决车间调度问题,其中介绍了常用的几种编码方式,在比较的情况下提出本文主要用基于操作的编码方式.还有提出了几
21、种主要的遗传算子。并且以四个工件四个机器问题进行举例,说明了用遗传算法解决车间调度问题的可行性。2 遗传算法相关理论与实现技术遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的7。它摒弃了传统的搜索方式，模拟达尔文的遗传选择和自然淘汰的生物进化过程8。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索
22、方式来搜索优化群体中的最优个体，求得满足要求的最优解。2.1 自然进化与遗传算法自从达尔文的进化论得到人们的接受之后，生物学家们就对进化机制产生了极大的兴趣。化石记录表明我们所观察的复杂结构的生命是在相对短的时间进化而来的，对这一点包括生物学家在内的许多人都感到惊奇。虽然目前人们对进化机制在一些方面还没有弄清楚，但它们的一些特征已为人所知。进化是发生在编码染色体上，通过对染色体的译码部分生成生物体，但下面几个关于进化理论的一般特性已被广大人们所接受。1.进化过程发生在染色体上，而不是发生在它们所编码地生物个体上。2.自然选择把染色体以及由它们所译成的结构表现联系在一起，哪些适应性好地个体的染色
23、体经常比差的个体的染色体有更多的繁殖机会。3.繁殖过程是进化发生的那一刻，变异可以使生物体子代的染色体不同于它们父代的染色体，通过结合两个父代染色体的物质，重组过程可以在子代中产生有很大差异的染色体。4.生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构之中，这些个体会很好的适应它们的环境。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择的原则是适应者生存，不适者淘汰。自然选择决定了群体中那些个个体能存活并繁殖，有性生殖保证了后代基因中的混合与重组。比起那些仅包含单个亲本的基因拷贝和依靠偶然变异来改进的后代，这种由基因重组产生的后代进化
24、要快得多。2.2 基本遗传算法2.2.1 遗传算法的基本思路1.首先确定问题的求解空间；2.其次将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；3.计算当前群体中每个个体的适应度函数值。运用选择、交叉、变异算子产生新一代群体；4.对新一代群体中的个体进行评价，若找到满足问题的最优解，结束；否则，转步骤3。2.2.2 遗传算法的模式定理1.选择操作对模式的影响选择操作是遗传算法中体现“适者生存”的关键一环，它能控制高适应度的模式成指数级增长。最常用的选择方式是“轮盘赌”法。其传统实现建立在逐项比较的基础上，算法复杂度为O（n2）。通过把各码链适应值转换为一组具有线性序的区间
25、，从而可利用二分查找法实现“轮盘赌”选择操作的递归算法，使时间复杂度下降到O（nlog2n）。2.交换操作对模式的影响交换操作是有规则的信息交换，它能创建新的模式结构，但又最低限度地破坏选择操作过程所选择的高适应度的模式。假设交换操作是采用的单点随机杂交方式，随机选取杂交的起始位置，交叉概率为Pc，两个具有相同模式H的个体发生交换，即杂交操作，不会改变模式H。但是如果其中一方个体不具有模式H，则有可能会引起另一个个体模式的改变。其中一方不具有模式H的概率为1- p(H, t)，当两个个体发生交换时，如果引起模式H的改变，只可能将交换的起始位置选择在第一个模式位到最后一个模式位之间的任何一个位置
26、上，此时，使模式H生存的概率Ps，为:(2.1)在交换过程中，可能使两个都不具备模式H的个体经交换后产生模式H，故生存概率（）只是一个下界，则有：(2.2)综合考虑选择操作，模式H在下一代中的数量可以用下式来综合估计:(2.3)从上式可以看出，模式的平均适应度高于群体平均适应度，并且具有短定义距的模式，将在下一代中成指数级的增长。3.变异操作对模式的影响通过变异操作对个体串中单个位置进行代码替换，替换的概率为变异概率Pm，则该位置不发生变异的概率为1-Pm。要使一个模式H在变异操作过程中不被破坏，就要保证模式H中确定位必须保证不变，因此，模式H保持不变的概率为:(2.4)上式中O(H)为该模式
27、的阶数。综合上面所述，考虑到选择操作、交换操作和变异操作对模式的影响，则第t代种群P(t)经过遗传操作后下一代种群P(t+1)具有模式H的个体总数为:(2.5)该式表示了下述的模式定理。模式定理:在遗传算子选择、交换、变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将得以指数级增长。模式定理保证了较优的模式(遗传算法的较优解)的数目呈指数增长，为解释遗传算法机理提供了数学基础。由模式定理可知，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在后代中呈指数级增长。这些模式在遗传中很重要，称为基因块。基因块假设:遗传算法通过短定义距、低阶以及高平均适应度的模
28、式(基因块)，在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在;而基因块假设则指出了在遗传算子的作用下，算法具有生成全局最优解的能力，即能生成高阶、长定义距、高平均适应度的模式，最终生成全局最优解。上述结论并没有得到证明，因而被称为假设。目前已经有大量的实践证据支持这一假设，尽管大量的证据并不等于理论证明，但是至少可以肯定的是对很多经常碰到的问题，遗传算法都是适用的。2.2.3 遗传算法的收敛性分析遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收
29、敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。通常，种群太小则不能提供足够的采样点，以致算法性能很差;种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。1.选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。2.交叉概率对收敛性的影响交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很
30、快，会造成高适应度值的个体很快被破坏掉;概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。3.变异概率对收敛性的影响变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。遗传操作对收敛性的影响，可利用马尔可夫链对遗传算法进行分析，从而论证了遗传算法在收敛性方面的一些重要性质，有力地支持了遗传算法的理论基础。由马尔可夫链推导出来的一些结论:基本遗传算法收敛于最优解的概率为1,使用保留最优个体策略的遗传算法收敛于最优解的概率为1。4.隐含并行性隐含并行性定理:遗传算法所处理的模式总数与其群体规模N的立
31、方成正比，即:m=O(N3) （2.6）由该定理可知，虽然表面上每代处理的个体数目都是一定的，但是由于每个个体都隐含着多种不同的模式，所以每次参与遗传算子操作的个体却不仅仅是两个。从总体上来说，每代之间所处理的个体要远大于其表面的数目，这就是遗传算法独特的隐含并行性。由隐含并行性定理可知，虽然表面上每代仅对N个个体处理操作，而事实上处理了O(N3)个模式，且无需额外存储。隐含并行性为遗传算法的高效性提供了理论依据。2.2.4 基本遗传算法参数说明对遗传算法性能有影响的参数主要有:种群数目N、交换概率Pc、变异概率Pm、代沟G、尺度窗口W、和选择策略S等。1.种群数目(population size)种群数目的多少直接影响到遗传算法的优化性能和效率，种群选择太小时，不能提供足够多的个体，致使算法性能较差，易产生早熟收敛，甚至不能得到可行解。种群选择
