车间作业调度(job-shop-scheduling)讲解课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,车间调度算法,(job shop scheduling),彭博,2012-11-21,车间调度算法(job shop scheduling),主要内容,Jobshop,调度问题,遗传算法理论,遗传算法在车间调度算法中的求解过程,主要内容Jobshop 调度问题,问题提出,车间作业调度,(Job-Shop Scheduling),简称,JSS,是一个典型的,NP,难问题，是,Operation Research,领域中研究的重要课题它的研究不仅具有重大的现实意义，而且具有深远的理论意义长期以来，,JSS,研究的方法始终以启发式算法为主导，绝大部分的,JSS,研究工作也都围绕着启发式算法进行，如基于启发式算法的,JSS,仿真系统，基于启发式算法的并行,JSS,系统，基于启发式算法的,JSS,专家系统，等等，尽管这些研究取得了一定的应用效果，但是却存在着难以克服的弱点，如计算规模不可能较大，寻优结果不具备全局特性等等近年来，又有学者提出了基于神经网络的车间作业调度系统，但此种方法在,JSS,规模较大时，却存在着计算速度慢与结构参数难以确定的弱点。

由此可见，要想进一步研究,JSS,选择一种有效的方法极为必要问题提出车间作业调度(Job-Shop Scheduling,问题描述：,假设有,n,个工件,J1,J2,Jn,要在,m,台机器,M1,M2,Mm,上进行加工每个工件以一定的,次序,在所有的机器上轮流加工每个工件分成,m,个工序，而每个工序对应了相应的加工机器其中，工序的加工时间给定J1,:M1 M2 M3,J2,:M3 M1 M2,J3,:M2 M3 M1,工序,1,工序,2,工序,3,问题描述：假设有 n个工件J1,J2,Jn 要在m台,约束,工件上约束：每个工件上的工序只能在上一个工序执行结束以后，才能开始执行下一个工序机器上约束：每台机器每一个时刻最多只能执行一个工件，且该工序的执行时间是非抢占的最大完工时间,(Makespan),：完成所有工序所需要的总时间J1,:M1 M2 M3,J2,:M3 M1 M2,J3,:M2 M3 M1,工序,1,工序,2,工序,3,约束工件上约束：每个工件上的工序只能在上一个工序执行结束以后,目标,有,M,台机器及,N,个工件，由于工件的加工工艺的要求，每个工件使用,M,台机器的,次序,以及每道工序所花费的,时间,已经给定。

如何安排在每台机器上工件的加工顺序，使得总的完工时间,(Makespan),最小目标有M台机器及N个工件，由于工件的加工工艺的要求，每个工件,Jobshop,调度问题的实际应用,在解决实际问题的时候，“工件”和“机器”可以拓展成相应的问题描述譬如：在生产车间当中，把一个零件或是一组零件看是需要加工的“工件”，而把加工用的车床看成是“机器”；在飞机调度问题中，可以将若干个不同的飞机看成“工件”，而将飞机需要进行的操作，看成是需要操作的“机器”因而，,job shop scheduling,问题的实际应用是非常广泛的Jobshop 调度问题的实际应用在解决实际问题的时候，“,遗传算法在解,Job-shop,调度问题方面的研究现状,由于,Job-Shop,调度问题是一个,NP,难题，而遗传算法为求,NP,难度问题的近似解提供了一种有效手段，所以现在许多人都致力于用遗传算法解决,Job-shop,问题，各有特点但就目前来看：,(1),由于,Job-Shop,调度问题的特殊性，编码机制显得尤为重要，因为编码机制选择不当，遗传算法的杂交、变异算子很容易破坏原加工顺序2),死锁问题也是一个重要问题，如果处理不当，死锁的出现是无法预料的。

3),收敛性及收敛速度问题，应用,GA,解,Job-Shop,调度问题时很少有人考虑这两个问题，所以得到的结果与最佳值的接近程度无理论保证遗传算法在解Job-shop调度问题方面的研究现状 由于Jo,Job-shop,的求解方法,局部搜索（,Local Search,）禁忌搜索（,Tabu Search,）遗传算法（,Genetic Algorithm,）混合进化算法,(Memetic Algorithm),Job-shop的求解方法局部搜索（Local Searc,局部搜索算法,领域结构（,Neighborhood,）,:,将一个初始解进行微小变动以后，产生的解的集合Neighborhood,局部搜索算法领域结构（Neighborhood）:将一个初始,局部搜索算法,从一个初始解开始，每次从领域结构中选择一个最好的,邻居解,作为下一个初始解，迭代搜索解空间的过程局部搜索算法从一个初始解开始，每次从领域结构中选择一个最好的,局部搜索算法,核心：领域结构的构造在,Job-shop,中，对所有机器上的每个工件都考虑其领域结构，效率是非常低下的,也可能导致不可行解的产生通常是考虑基于关键路劲的领域结构构造方法。

关键路径：调度序列中的最长路径，它制约着整个调度的完工时间局部搜索算法核心：领域结构的构造在Job-shop中，对所,局部搜索算法,关键块,关键块：连续的一组关键工序，因而，可能存在多个关键块目前的领域结构都是基于关键块的，有多种领域操作，但都是基于移动关键块两端的工序不产生不可行解，效率高局部搜索算法关键块关键块：连续的一组关键工序，因而，可能存在,局部搜索算法的不足,当遇到局部极值的时候，,Local search,的算法将遇到瓶颈，从而需要更多的策略或更好的算法跳出,local optima,局部搜索算法的不足当遇到局部极值的时候，Local sear,跳坑策略以及,ILS,跳坑策略：对当前解进行大的改动（扰动）迭代局部搜索算法：结合跳坑策略形成的算法跳坑策略以及ILS跳坑策略：对当前解进行大的改动（扰动）禁忌搜索,(Tabu Search),提出,:,由美国工程院院士，冯若依曼理论奖获得者,Fred Glover,最先在,1986,年提出,Tabu Search,算法Tabu Search:,将之前搜索过的解 禁忌，每次只选择没被禁忌的解或满足解禁策略的解因而，它可以接受比自身差的解，从而跳出局部极值点，去搜索新的解空间。

解禁策略：遇到一个虽被禁忌，但却比历史最优解还要好的解时，解禁，选择此解禁忌长度,:,每个解 被禁忌的时间长度禁忌对象：可以禁忌 完整的解，也可以禁忌 部分解 或是 领域动作禁忌搜索(Tabu Search)提出:由美国工程院院士,禁忌搜索,(Tabu Search),禁忌对象的选择一般与相应的领域结构对应起来，效果会比较好Job-shop,中常用的禁忌对象：若,JA,插入,JB,之后，则将,JA,和,JB,之间的所有工序的排列和在机器上的位置禁忌住，标记在禁忌列表,(Tabu_List),里禁忌搜索(Tabu Search)禁忌对象的选择一般与相应的,遗传算法概述,遗传算法（,Genetic Algorithms,GA,）研究的历史比较短，,20,世纪,60,年代末期到,70,年代初期，主要由美国,Michigan,大学的,John Holland,与其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型随后经过,20,余年的发展，取得了丰硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗传算法受到广泛的关注。

遗传算法概述遗传算法（Genetic Algorithms,遗传算法概述,从,1985,年在美国卡耐基,梅隆大学召开的第一届国际遗传算法会议,(International Conference on Genetic Algorithms:ICGA85),到,1997,年,5,月,IEEE Transactions on Evolutionary Computation,创刊,遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟遗传算法概述从1985年在美国卡耐基梅隆大学召开的第一届国,遗传算法基本概念和术语,遗传算法是模拟前述生物进化过程的计算模型下面先给出几个生物学的基本概念与术语，这对于理解遗传算法是非常重要的染色体,(chromosome),：具有遗传性质基因序列种群（,population,）染色体带有特征的个体的集合称为种群该集合内个体数称为群体的大小遗传算法基本概念和术语遗传算法是模拟前述生物进化过程的计算模,遗传算法基本概念和术语,适应度（,fitness,）在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。

对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝选择（,selection,）指决定以一定的概率从种群中选择若干个体的操作一般而言，选择的过程是一种基于适应度的优胜劣汰的过程遗传算法基本概念和术语适应度（fitness）在研究自然,遗传算法基本概念和术语,交叉（,crossover,）有性生殖生物在繁殖下一代时，两个同源染色体通过交叉而重组，亦即在两个染色体的某一相同位置处,DNA,被切断，其前后两串分别交叉组合形成两个新的染色体这个过程又称基因重组（,recombination,），俗称“杂交”变异（,mutation,）在细胞进行复制时可能以很小的概率产生某些复制差错，从而使,DNA,发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状遗传算法基本概念和术语交叉（crossover）有性生殖,基本遗传算法的实现方法,各种不同的遗传算法都有相同的的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程基于这个共同特点，,Goldberg,总结出了一种统一的最基本的遗传算法,基本遗传算法（,Simple Genetic Algorithm,简称,SGA,）。

SGA,只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值因此为方便起见，本文在以后的应用中用此方法基本遗传算法的实现方法 各种不同的遗传算法都有相同的的特点，,遗传算法解决,Job shop,的几个重要构成要素,（,1,）染色体编码方法,1 2 3,；,3 1 2,；,2 3 1,遗传算法解决Job shop的几个重要构成要素（1）染色体编,基本遗传算法的构成要素,（,2,）交叉过程,下面是一种基于最长公共子序列的交叉算符，对两个父亲个体的每个机器都进行如下操作，产生两个子代个体：,基本遗传算法的构成要素（2）交叉过程,遗传算法的几个重要构成要素,（,3,）适应度评价函数,函数的主要部分是基于最大完工时间,(Makespan),可以附加上个体之间的距离，保持交叉的两个个体的分散性，避免近亲的后果特例：两个解相同个体的后代和父代的解也相同遗传算法的几个重要构成要素（3）适应度评价函数,遗传算法流程,Step1.,初始化种群（采用随机策略）,Step2.,随机选择两个个体交叉，产生新个体加 入到种群。

Step3.,根据适应度函数，对种群进行维护，淘汰掉适应度低的个体Step4.,没有到达终止条件，就,Goto Step 2.,遗传算法流程Step1.初始化种群（采用随机策略）,Hybrid Evolution Algorithm-Memetic,Memetic Algorit。