遗传算法的车间调度算法求解.ppt

《遗传算法的车间调度算法求解.ppt》由会员分享，可在线阅读，更多相关《遗传算法的车间调度算法求解.ppt（52页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、遗传算法的车间调度算法求解 安晶 主要内容vJobshop 调度问题v遗传算法理论v遗传算法在车间调度算法中的求解过程问题提出v车间作业调度(Job-Shop Scheduling),简称JSS,是一个典型的NP难问题，是CIMS领域中研究的重要课题。它的研究不仅具有重大的现实意义，而且具有深远的理论意义。长期以来，JSS研究的方法始终以启发式算法为主导，绝大部分的JSS研究工作也都围绕着启发式算法进行，如基于启发式算法的JSS仿真系统，基于启发式算法的并行JSS系统，基于启发式算法的JSS专家系统，等等，尽管这些研究取得了一定的应用效果，但是却存在着难以克服的弱点，如计算规模不可能较大，寻优

2、结果不具备全局特性等等。近年来，又有学者提出了基于神经网络的车间作业调度系统，但此种方法在JSS规模较大时，却存在着计算速度慢与结构参数难以确定的弱点。由此可见，要想进一步研究JSS,选择一种有效的方法极为必要。遗传算法的出现给这类问题带来了新的希望，并取得了较为满意的成果。在此，我们提出了基于遗传算法的车间作业调度的求解。Jobshop 调度问题的问题描述v在问题的描述中，“机器”可以指机床，有时也可以指操作工人。“工件”指一个零件，或一批零件，或是其他的什么含义，这可以根据具体的问题确定。“工序”是指工件需要经过一些机器，或所有机器的操作及其顺序。而“加工时间”是指完成一个操作所需要的时间

3、。由于有“机器”，“工件”等词语所处的实际背景，所有关于调度的术语及其所表达的概念和所描述的问题就比较直观和容易理解。问题描述v假设有 n个工件J1,J2,Jn要经过m台机器M1,M2,Mm加工。一个工件在一台机器上的加工称为一道“工序”。加工顺序要求表示工件加工在技术上的约束，即工件的加工工艺过程，这是事先给定的。用“加工顺序”表示各台机器上工件加工的先后次序。加工顺序是作业调度要解决的问题。当每个工件都有其独特的加工路线时，要确定工件的加工顺序，这属于单间车间（Job-Shop）的作业调度问题；当所有工件的加工路线都一致时，要确定工件的加工顺序，这属于流水车间（Flow-Shop）的作业调

4、度问题。完成一道工序的加工，需花费一定的加工时间。在讨论一般情况下的作业调度问题时，“加工时间”包括机器调整时间，实际加工时间和工序之间的转送时间。加工时间是已知的。问题描述v有M台机器及N个工件，由于工件的加工工艺的要求，每个工件使用M台机器的顺序以及每道工序所花费的时间已经给定。如何安排在每台机器上工件的加工顺序，使得某种指标（如总的完成时间）最小，此指标就是作业调度问题的优化目标。问题描述v用Conway等人提出的方法简单地表示作业调度问题，这种方法只用四个参数就可以表示大多数不同的作业调度问题，这四个参数是n/m/A/B,其中v n-工件数；vm-机器数；vA-车间类型 v B-目标函

5、数，通常是使其值最小。v有了这四个符号，就可以简明地表示不同的作业调度问题。例如，n/4/G/Cmax表示n个工件经4台机器加工的单件车间调度问题，目标函数是使最长完工时间Cmax最短。单件车间调度满足的约束条件1.一个工件不能同时在不同的机器上加工，尽管一个工件有时可能包括多个相同的零件，也不能将其分成几部分，同时在几台不同的机器上加工；2.对整个工件来说，在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工；3.不允许中断，当一个工件一旦开始加工，必须一直进行到完工，不允许中途停下来，插入其他工件；4.每道工序只在一台机器上完成，每台机器只完成一道工序；约束条件5.工件数

6、、机器数、加工时间已知，且加工时间与加工顺序无关；6.允许工件在工序之间等待，允许机器在工件未到达是闲置；7.工件加工技术上的约束事先给定；8.每台机器同时只能加工一个工件。以上8项基本假设条件是可以放宽和改变的，由此可以构成不同类型的调度问题。遗传算法在解Job-shop调度问题方面的研究现状 v由于Job-Shop调度问题是一个NP难题，而遗传算法为求NP难度问题的近似解提供了一种有效手段，所以现在许多人都致力于用遗传算法解决Job-shop问题，各有特点。但就目前来看：(1)由于Job-Shop调度问题的特殊性，编码机制显得尤为重要，因为编码机制选择不当，遗传算法的杂交、变异算子很容易破

7、坏原加工顺序。(2)死锁问题也是一个重要问题，如果处理不当，死锁的出现是无法预料的。(3)收敛性及收敛速度问题，应用GA解Job-Shop调度问题时很少有人考虑这两个问题，所以得到的结果与最佳值的接近程度无理论保证。遗传算法理论遗传算法概述v遗传算法（Genetic Algorithms,GA）研究的历史比较短，20世纪60年代末期到70年代初期，主要由美国Michigan大学的John Holland与其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过20余年的发展，取得了丰硕的应用成果和理论研究的进展

8、，特别是近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗传算法受到广泛的关注。遗传算法概述v从1985年在美国卡耐基梅隆大学召开的第一届国际遗传算法会议(International Conference on Genetic Algorithms:ICGA85),到1997年5月IEEE的Transactions on Evolutionary Computation创刊,遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。生物进化的基础v生物进化的原因自古至今有着各种不同的解释，其中被人们广泛接受的是达尔文的自

9、然选择学说。v自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物与无机环境之间的斗争三个方面。在生存斗争中，具有有利变异（mutation）的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫做自然选择，达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间在性状上存在的相似现象。变异是指父代与子代之间以及子代的个体之间在性状上或多或少地存在的差异现象。在

10、生物群体内，遗传和变异的关系十分密切，一个生物体的遗传性状往往会发生变异，而变异的性状有的可遗传。遗传能使生物的性状不断地传送给后代，因此保持了物种的特性；变异能够使生物的性状发生改变，从而适应新的环境而不断的向前发展。遗传算法基本概念和术语v遗传算法是模拟前述生物进化过程的计算模型。下面先给出几个生物学的基本概念与术语，这对于理解遗传算法是非常重要的。v种群（population）染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。v进化（evolution）生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。

11、生物的进化是以种群的形式进行的。遗传算法基本概念和术语v适应度（fitness）在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝。v选择（selection）指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。v复制（reproduction）细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。遗传算法基本概念和术语v交叉（crossove

12、r）有性生殖生物在繁殖下一代时，两个同源染色体通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组（recombination），俗称“杂交”。v变异（mutation）在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。v编码（coding）DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。v解码（decoding）从遗传子型到表现型的映射。遗传算法的基本思想 v遗传算法采纳了自然进化模型，如

13、选择、交叉、变异、迁移、局域与邻域等。计算开始时，一定数目N个个体（父个体1、父个体2、父个体3、父个体4）即种群随机的初始化，并计算每个个体的适应度函数，第一代也即初始代就产生了。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体，父代要求基因重组（交叉）而产生子代。所有的子代按一定概率变异。然后子代的适应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代（子个体1、子个体2、子个体3、子个体4）。这一过程循环执行，直到满足优化准则为止。基本遗传算法的实现方法 v各种不同的遗传算法都有相同的的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，

14、来完成对问题最优解的自适应搜索过程。基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法基本遗传算法（Simple Genetic Algorithm,简称SGA）。SGA只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。因此为方便起见，本文在以后的应用中用此方法。基本遗传算法的构成要素（1）染色体编码方法 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集0，1所组成的。初始群体中各个个体的基因值可用均匀分布的

15、随机数来生成，如就可以表示一个个体，该个体的染色体长度是n=18。（2）个体适应度评价 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零，这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。基本遗传算法的构成要素（3）遗传算子 基本遗传算法使用下述三种遗传算子：v选择运算使用比例选择（也叫轮盘赌选择）算子v交叉运算使用单点交叉算子v变异运算使用基本位变异算子或均匀变异算子（4）基本遗传算法的运行参数 SGA有下述四个

16、运行参数需要提前设定vM：群体规模影响遗传优化的最终结果以及遗传算法的执行效率。当群体规模M太小时，遗传算法的优化性能一般不会太好，而采用较大的群体规模则可以减少遗传算法陷入局部最优解的机会，但是较大的群体规模意味着计算复杂度高，一般M取10到120之间。基本遗传算法的构成要素vPc：Pc控制着交叉操作被使用的频度，较大的交叉概率可增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭到破坏的可能性增大；若交叉概率太低，遗传算法搜索可能陷入迟钝状态。一般Pc取0.25到1.00之间。vPm：变异在遗传算法中属于辅助性的搜索操作，它的主要目的是维持群体的多样性。一般的低频度的变异可防止群体中重要的

17、单一基因的可能丢失，高频度的变异将使遗传算法趋于纯粹的随机搜索，通常取变异概率Pm为0.001到0.1之间。vT：遗传算法的终止进化代数，一般取为100到500之间。算法示例v现详细介绍一下二进制编码的轮盘赌选择、单点交叉和基本位变异操作。v图2.1所示的是一组二进制基因码构成的个体组成的初始种群，个体的适应度评价值经计算由括号内的数值表示，适应度越大代表这个个体越好。v0001100000(8)0101111001(5)0000000101(2)1001110100(10)1010101010(7)1110010110(12)1001011011(5)1100000001(19)100111

18、0100(10)0001010011 (14)图2.1 初始种群的分布v轮盘赌选择方法类似于博彩游戏中的轮盘赌。个体适应度按比例转化为选中概率，将轮盘分成10个扇区，因为要进行10个选择，所以产生10个0，1之间的随机数，相当于转动10次轮盘，获得10次转盘停止时指针位置，指针停止在某一扇区，该扇区代表的个体即被选中。v个体 染色体 适应度 选择概率 累积概率 1 0001100000 8 0.086957 0.086957 2 0101111001 5 0.054348 0.141306 3 0000000101 2 0.021739 0.163043 4 1001110100 10 0.1

19、08696 0.271739 5 1010101010 7 0.076087 0.347826 6 1110010110 12 0.130435 0.478261 7 1001011011 5 0.054348 0.532609 8 1100000001 19 0.206552 0.739130 9 1001110100 10 0.108696 0.847826 1 00001010011 14 0.152174 1.000000算法示例v假设产生随机数序列为0.070221，0.545929，0.784567，0.44693，0.507893，0.291198，0.71634，0.27090

20、1，0.371435，0.854641，将该随机序列与计算获得的累积概率比较，则依次序号为1，8，9，6，7，5，8，4，6，10个体被选中。显然适应度高的个体被选中的概率大，而且可能被选中；而适应度低的个体则很有可能被淘汰。在第一次生存竞争考验中，序号为2的个体（0101111001）和3的个体（000000101）被淘汰，代之以适应度较高的个体8和6，这个过程被称之为再生(reproduction)。单点交叉算子v任意挑选经过选择操作后种群中两个个体作为交叉对象，即两个父个体经过染色体交换重组产生两个子个体。随机产生一个交叉点位置，父个体1和父个体2在交叉点位置之右的部分基因码互换，形成子

21、个体1和子个体2。A:10110110 00 A:10110110 11 单交叉点 B:00101101 11 B:00101101 00 交叉点 基本位变异算子v基本位变异算子是最简单和最基本的变异操作算子。对于SGA中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为1，则变异操作将其变为0。v基本位变异运算的示意如下所示：v1010101001 基本位变异 A:1010001001遗传算法在车间调度算法中的求解过程 Job-Shop调度问题的数学模型v对于一般单件车间的排序问题，要描述一道工序，需要3个参数i

22、，j和k。i表示工件代号，j表示工序序号，k则表示完成i工件第j道工序加工的机器的代号。因此，可以用(i,j,k)来表示工件i的第j道工序是在机器k上进行的。我们可以用加工描述矩阵D来描述一般单件车间的排序问题。v加工描述矩阵D=vD=此时矩阵的第i行第j列隐含着v工件号为i工序号为j。v加工时间矩阵T与加工描述矩阵D相对应。例如T=排序问题中的符号说明 v(i,j,k)工件 的第j道工序，这道工序是在机器 上进行的。v 工件 在机器 上的加工时间,工件 的总加工时间为v 工件 的到达时间，或称准备就绪时间。这个时间指的是工件从外部进入车间，可以开始进行加工的最早时间。v 工件 的完工期限。排

23、序问题中的符号说明v 工件 在车间的允许停留时间，即从工件 进入车间到预定完工时间之间的时间间隔。=-v 工件Ji在进行第j道工序之前的等待时间。工件Ji的总等待时间 =v 工件Ji的完工时间，即在该时刻，工件Ji的最后一道工序完成，所以，如下关系成立：=+(3-1)排序问题中的符号说明v 最长完工时间，=v 某个调度k的所有工件完工时间的总和，即总加工时间 =v 最短总加工时间，=v我们选择最短总加工时间作为目标函数，即选用n/m/G/模型。数学模型 v 设有m台机器M1、M2、Mm和n个工件J1、J2、Jn，工件Ji的第j道工序的加工时间为Tij。满足如下条件:v 1)一台机器一次只加工一

24、个工件。v 2)每个工件不能同时在多台机器上加工。v 3)每个工件的加工顺序预先确定，工件按序加工。v 4)每个工件在每台机器上只加工一次。v 5)工件在加工时不允许中断。数学模型v设C(i,j)(i=1,2,n；j=1,2,m)表示工件Ji的第j道工序的加工机器号，表示C(i,j)机器上工件Ji的第j道工序的完工时间，表示C(i,j)机器上工件Ji的第j道工序的开工时间。则有：v 0 (3-2)v 0 (3-3)v =+(3-4)数学模型v =(3-5)v其中 为机器C(i,j)上加工工件Ji之前所加工工件Jk的第l道工序的完工时间。v我们选择机器的最长完工时间最小为目标函数，则目标函数可具

25、体表示为：minE i,m,c(i,m)i=1n (3-6)工件序编码法v一个66的加工描述矩阵、加工时间矩阵如下vM v该问题的一个调度结果如下：N=编码方法 v遗传算法主要是对群体中个体施加操作，从而完成优化的。遗传算法不能直接处理问题空间的参数，而只能处理以基因链码形式表示的个体。因此，要使用遗传算法，就必须把优化问题的解的参数形式转化成基因链码的表示形式。这一转化操作就叫做编码。v Job-Shop调度问题就是在不破坏加工顺序的前提下，怎样在机器上安排工件以达到目标函数式(3-6)的要求，即各工件在机器上的最佳排列组合，而这种排列组合关系有其内在的序关系，如果假定工件号按由小到大的自然

26、顺序排列，则各台机器上任意两个不同工件之间只有两种序关系（顺序或逆序），这种序关系用二进制表示，顺序为1，逆序为0。例如对第k台机器上的工件Ji和Jj工件（设im成立吗？若成立则结束，否则转3）v3)i1，Point1v4)in吗？若是则转2)，否则转5)v5)从 Point开始取串长为n-i的子串，统计其中0的个数r,则Ji应排在第r+1个空白处，若r+1位被占用，则向后移位直至未被占用的位置。v6）ii+1，PointPoint+n-i转4)v为处理起来更加直观，我们把Job-Shop调度问题的工时工序表用两个矩阵表示 (i=1，2，n；j，k=1，2，m)，工件Ji的第j道工序在机器k上

27、加工；(i=1，2，m；j=1，2，n)表示加工时间矩阵。另外 (i，j=1，2，n；k=1，2，m)表示机器k上各工件的加工顺序，机器k上第j个加工的工件是Ji。例如有一个66的M、N矩阵如下：车间作业调度遗传算法的具体实现初始群体的产生 v初始群体产生时，将N矩阵各行列的元素值初始化为(0,0)mn，我们假定某工件i的第j道工序已加工完毕，则M矩阵的第i行第j列对应元素设为(0,0)。从M矩阵某行随机产生左边第一个不为(0,0)的元素(i,k)，得到一个将加工的工件Ji及所在机器k，加工完成后将该元素的变为(0,0)，同时将N矩阵中的第k行第一个为0的元素变为(i,k)，直到所有工件都加工

28、完毕为止。便得到一个个体。v（初始群体产生算法）v 1)种群已满吗？若是则结束，否则转2)v 2)初始化N(i,j)=(0,0)mnv 3)随机产生一个工件号i，在M矩阵第i行找出第1个不为 (0,0)的元素(i,k)及所在的列j1v 4)找出N(k,j)的第k行的第一个为（0，0）的列号j2，并将 N(k,j2)(i,k)v 5)将M矩阵中相应的(i,j1)变为（0，0）v 6)循环执行了mn次吗?若是则转7)，否则转3)v7)对N矩阵中各行进行编码，并计算目标函数值vv选择算子 采用轮盘赌选择法，目标函数值小的个体复制概率大的原则进行选择，逐步淘汰目标函数值大的的个体。其具体实现方法同第二

29、章例子。v杂交算子 采用单点杂交算子，以概率任意选择两个个体，随机产生一杂交点w（w1，mn(n-1)/2-1）,交换从w开始的后半部分染色体子串。v变异算子 为增加种群的多样性，采用基本位变异算子，以概率随机选择一个体x，再随机产生一变异点w(w1，mn(n-1)/2-1)，将该位基因加1模2。约束问题 死锁的判断 v由M、N两矩阵可以判断死锁是否发生。两个指针数组pointern(n)、pointerm(m)分别指向M、N矩阵中第1列各元素，pointerm(i)(i=1,2，,n)指向的是当前要加工的各工件及其所在的机器，pointern(j)(j=1,2，,m)指向的是当前各台机器可以

30、加工的工件。如果pointerm(i)指向的所有元素和pointern(j)指向的所有元素有相同的(i,j)，则表明该工件Ji的下一道工序可以在机器k上加工，机器k上下一个可以加工的工件是Ji，加工可以继续下去，否则就会产生死锁。加工完(i,j)后，pointern(i)pointerm(i)+1，pointern(j)pointern(j)+1，直到所有元素都判断完毕。v1)k1，pointerm(i)0，pointern(j)0v 2)knm成立吗?若是则无死锁并转5)，否则转3)v 3)查询pointerm(i)指向的所有元素和pointern(j)指向的所有元素是否有相同的(i,j)，

31、若这样的元素不存在则死锁并结束，否则转4)v 4)在机器j上加工工件，根据式(3)、(4)求各台机器上当前的最早完工时间，kk+1，pointerm(i)pointerm(i)+1，pointern(j)pointern(j)+1，转2)v 5)由式(5)求目标函数值，结束结 论v二进制的病毒遗传算法解Job-Shop调度问题的测试用例 v我们给出二组工时工序表和加工时间矩阵，每组按参数不同又分为2组不同的例子，选取群体规模为100，遗传代数为500。其中，m为工时工序表矩阵，t为加工时间矩阵，为方便起见，我们采用行输入法。vm=(231045 325410 214503 425130 235104 120354)vt=(236541 589565 478595 632545 563254 478596)v测试用例：(pc=0.75,pm=0.15)v相应的甘特图和迭代曲线如下图：甘特图迭代曲线 谢谢大家