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

遗传算法的车间调度算法求解安晶2006.4.4主要内容Job—shop调度问题遗传算法理论遗传算法在车间调度算法中的求解过程问题提出车间作业调度(Job-ShopScheduling),简称JSS,是一个典型的NP难问题，是CIMS领域中研究的重要课题。它的研究不仅具有重大的现实意义，而且具有深远的理论意义。长期以来，JSS研究的方法始终以启发式算法为主导，绝大部分的JSS研究工作也都围绕着启发式算法进行，如基于启发式算法的JSS仿真系统，基于启发式算法的并行JSS系统，基于启发式算法的JSS专家系统，等等，尽管这些研究取得了一定的应用效果，但是却存在着难以克服的弱点，如计算规模不可能较大，寻优结果不具备全局特性等等。近年来，又有学者提出了基于神经网络的车间作业调度系统，但此种方法在JSS规模较大时，却存在着计算速度慢与结构参数难以确定的弱点。由此可见，要想进一步研究JSS,选择一种有效的方法极为必要。遗传算法的出现给这类问题带来了新的希望，并取得了较为满意的成果。在此，我们提出了基于遗传算法的车间作业调度的求解。Job—shop调度问题的问题描述在问题的描述中，“机器”可以指机床，有时也可以指操作工人。“工件”指一个零件，或一批零件，或是其他的什么含义，这可以根据具体的问题确定。“工序”是指工件需要经过一些机器，或所有机器的操作及其顺序。而“加工时间”是指完成一个操作所需要的时间。由于有“机器”，“工件”等词语所处的实际背景，所有关于调度的术语及其所表达的概念和所描述的问题就比较直观和容易理解。问题描述假设有n个工件{J1,J2,…,Jn}要经过m台机器{M1,M2,…,Mm}加工。一个工件在一台机器上的加工称为一道“工序”。加工顺序要求表示工件加工在技术上的约束，即工件的加工工艺过程，这是事先给定的。用“加工顺序”表示各台机器上工件加工的先后次序。加工顺序是作业调度要解决的问题。当每个工件都有其独特的加工路线时，要确定工件的加工顺序，这属于单间车间（Job-Shop）的作业调度问题；当所有工件的加工路线都一致时，要确定工件的加工顺序，这属于流水车间（Flow-Shop）的作业调度问题。完成一道工序的加工，需花费一定的加工时间。在讨论一般情况下的作业调度问题时，“加工时间”包括机器调整时间，实际加工时间和工序之间的转送时间。加工时间是已知的。问题描述有M台机器及N个工件，由于工件的加工工艺的要求，每个工件使用M台机器的顺序以及每道工序所花费的时间已经给定。如何安排在每台机器上工件的加工顺序，使得某种指标（如总的完成时间）最小，此指标就是作业调度问题的优化目标。问题描述用Conway等人提出的方法简单地表示作业调度问题，这种方法只用四个参数就可以表示大多数不同的作业调度问题，这四个参数是n/m/A/B,其中n---工件数；m---机器数；A---车间类型B---目标函数，通常是使其值最小。有了这四个符号，就可以简明地表示不同的作业调度问题。例如，n/4/G/Cmax表示n个工件经4台机器加工的单件车间调度问题，目标函数是使最长完工时间Cmax最短。单件车间调度满足的约束条件1.一个工件不能同时在不同的机器上加工，尽管一个工件有时可能包括多个相同的零件，也不能将其分成几部分，同时在几台不同的机器上加工；2.对整个工件来说，在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工；3.不允许中断，当一个工件一旦开始加工，必须一直进行到完工，不允许中途停下来，插入其他工件；4.每道工序只在一台机器上完成，每台机器只完成一道工序；约束条件5.工件数、机器数、加工时间已知，且加工时间与加工顺序无关；6.允许工件在工序之间等待，允许机器在工件未到达是闲置；7.工件加工技术上的约束事先给定；8.每台机器同时只能加工一个工件。以上8项基本假设条件是可以放宽和改变的，由此可以构成不同类型的调度问题。遗传算法在解Job-shop调度问题方面的研究现状由于Job-Shop调度问题是一个NP难题，而遗传算法为求NP难度问题的近似解提供了一种有效手段，所以现在许多人都致力于用遗传算法解决Job-shop问题，各有特点。但就目前来看：(1)由于Job-Shop调度问题的特殊性，编码机制显得尤为重要，因为编码机制选择不当，遗传算法的杂交、变异算子很容易破坏原加工顺序。(2)死锁问题也是一个重要问题，如果处理不当，死锁的出现是无法预料的。(3)收敛性及收敛速度问题，应用GA解Job-Shop调度问题时很少有人考虑这两个问题，所以得到的结果与最佳值的接近程度无理论保证。遗传算法理论遗传算法概述遗传算法（GeneticAlgorithms,GA）研究的历史比较短，20世纪60年代末期到70年代初期，主要由美国Michigan大学的JohnHolland与其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过20余年的发展，取得了丰硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗传算法受到广泛的关注。遗传算法概述从1985年在美国卡耐基·梅隆大学召开的第一届国际遗传算法会议(InternationalConferenceonGeneticAlgorithms:ICGA’85),到1997年5月IEEE的TransactionsonEvolutionaryComputation创刊,遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。生物进化的基础生物进化的原因自古至今有着各种不同的解释，其中被人们广泛接受的是达尔文的自然选择学说。自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物与无机环境之间的斗争三个方面。在生存斗争中，具有有利变异（mutation）的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫做自然选择，达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间在性状上存在的相似现象。变异是指父代与子代之间以及子代的个体之间在性状上或多或少地存在的差异现象。在生物群体内，遗传和变异的关系十分密切，一个生物体的遗传性状往往会发生变异，而变异的性状有的可遗传。遗传能使生物的性状不断地传送给后代，因此保持了物种的特性；变异能够使生物的性状发生改变，从而适应新的环境而不断的向前发展。遗传算法基本概念和术语遗传算法是模拟前述生物进化过程的计算模型。下面先给出几个生物学的基本概念与术语，这对于理解遗传算法是非常重要的。种群（population）染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。进化（evolution）生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。遗传算法基本概念和术语适应度（fitness）在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝。选择（selection）指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。复制（reproduction）细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。遗传算法基本概念和术语交叉（crossover）有性生殖生物在繁殖下一代时，两个同源染色体通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组（recombination），俗称“杂交”。变异（mutation）在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。编码（coding）DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。解码（decoding）从遗传子型到表现型的映射。遗传算法的基本思想遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与邻域等。计算开始时，一定数目N个个体（父个体1、父个体2、父个体3、父个体4…）即种群随机的初始化，并计算每个个体的适应度函数，第一代也即初始代就产生了。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体，父代要求基因重组（交叉）而产生子代。所有的子代按一定概率变异。然后子代的适应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代（子个体1、子个体2、子个体3、子个体4…）。这一过程循环执行，直到满足优化准则为止。基本遗传算法的实现方法各种不同的遗传算法都有相同的的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法（SimpleGeneticAlgorithm,简称SGA）。SGA只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。因此为方便起见，本文在以后的应用中用此方法。基本遗传算法的构成要素（1）染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成，如x=10011001101110010100就可以表示一个个体，该个体的染色体长度是n=18。（2）个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零，这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。基本遗传算法的构成要素（3）遗传算子基本遗传算法使用下述三种遗传算子：选择运算使用比例选择（也叫轮盘赌选择）算子交叉运算使用单点交叉算子变异运算使用基本位变异算子或均匀变异算子（4）基本遗传算法的运行参数SGA有下述四个运行参数需要提前设定M：群体规模影响遗传优化的最终结果以及遗传算法的执行效率。当群体规模M太小时，遗传算法的优化性能一般不会太好，而采用较大的群体规模则可以减少遗传算法陷入局部最优解的机会，但是较大的群体规模意味着计算复杂度高，一般M取10到120之间。基本遗传算法的构成要素Pc：Pc控制着交叉操作被使用的频度，较大的交叉概率可增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭到破坏的可能性增大；若交叉概率太低，遗传算法搜索可能陷入迟钝状态。一般Pc取0.25到1.00之间。Pm：变异在遗传算法中属于辅助性的搜索操作，它的主要目的是维持群体的多样性。一般的低频度的变异可防止群体中重要的单一基因的可能丢失，高频度的变异将使遗传算法趋于纯粹的随机搜索，通常取变异概率Pm为0.001到0.1之间。T：遗传算法的终止进化代数，一般取为100到500之间。算法示例现详细介绍一下二进制编码的轮盘赌选择、单点交叉和基本位变异操作。图2.1所示的是一组二进制基因码构成的个体组成的初始种群，个体的适应度评价值经计算由括号内的数值表示