车间作业调度(job_shop_scheduling)讲解VIP免费

车间调度算法(jobshopscheduling)彭博2012-11-21主要内容Job—shop调度问题遗传算法理论遗传算法在车间调度算法中的求解过程问题提出车间作业调度(Job-ShopScheduling),简称JSS,是一个典型的NP难问题，是OperationResearch领域中研究的重要课题。它的研究不仅具有重大的现实意义，而且具有深远的理论意义。长期以来，JSS研究的方法始终以启发式算法为主导，绝大部分的JSS研究工作也都围绕着启发式算法进行，如基于启发式算法的JSS仿真系统，基于启发式算法的并行JSS系统，基于启发式算法的JSS专家系统，等等，尽管这些研究取得了一定的应用效果，但是却存在着难以克服的弱点，如计算规模不可能较大，寻优结果不具备全局特性等等。近年来，又有学者提出了基于神经网络的车间作业调度系统，但此种方法在JSS规模较大时，却存在着计算速度慢与结构参数难以确定的弱点。由此可见，要想进一步研究JSS,选择一种有效的方法极为必要。问题描述：假设有n个工件{J1,J2,…,Jn}要在m台机器{M1,M2,…,Mm}上进行加工。每个工件以一定的次序在所有的机器上轮流加工。每个工件分成m个工序，而每个工序对应了相应的加工机器。其中，工序的加工时间给定。J1:M1M2M3J2:M3M1M2J3:M2M3M1工序1工序2工序3约束工件上约束：每个工件上的工序只能在上一个工序执行结束以后，才能开始执行下一个工序。机器上约束：每台机器每一个时刻最多只能执行一个工件，且该工序的执行时间是非抢占的。最大完工时间(Makespan)：完成所有工序所需要的总时间。J1:M1M2M3J2:M3M1M2J3:M2M3M1工序1工序2工序3目标有M台机器及N个工件，由于工件的加工工艺的要求，每个工件使用M台机器的次序以及每道工序所花费的时间已经给定。如何安排在每台机器上工件的加工顺序，使得总的完工时间(Makespan)最小。Job—shop调度问题的实际应用在解决实际问题的时候，“工件”和“机器”可以拓展成相应的问题描述。譬如：在生产车间当中，把一个零件或是一组零件看是需要加工的“工件”，而把加工用的车床看成是“机器”；在飞机调度问题中，可以将若干个不同的飞机看成“工件”，而将飞机需要进行的操作，看成是需要操作的“机器”。因而，jobshopscheduling问题的实际应用是非常广泛的。遗传算法在解Job-shop调度问题方面的研究现状由于Job-Shop调度问题是一个NP难题，而遗传算法为求NP难度问题的近似解提供了一种有效手段，所以现在许多人都致力于用遗传算法解决Job-shop问题，各有特点。但就目前来看：(1)由于Job-Shop调度问题的特殊性，编码机制显得尤为重要，因为编码机制选择不当，遗传算法的杂交、变异算子很容易破坏原加工顺序。(2)死锁问题也是一个重要问题，如果处理不当，死锁的出现是无法预料的。(3)收敛性及收敛速度问题，应用GA解Job-Shop调度问题时很少有人考虑这两个问题，所以得到的结果与最佳值的接近程度无理论保证。Job-shop的求解方法局部搜索（LocalSearch）禁忌搜索（TabuSearch）遗传算法（GeneticAlgorithm）混合进化算法(MemeticAlgorithm)局部搜索算法领域结构（Neighborhood）:将一个初始解进行微小变动以后，产生的解的集合。Neighborhood局部搜索算法从一个初始解开始，每次从领域结构中选择一个最好的邻居解作为下一个初始解，迭代搜索解空间的过程。局部搜索算法核心：领域结构的构造。在Job-shop中，对所有机器上的每个工件都考虑其领域结构，效率是非常低下的,也可能导致不可行解的产生。通常是考虑基于关键路劲的领域结构构造方法。关键路径：调度序列中的最长路径，它制约着整个调度的完工时间。局部搜索算法关键块•关键块：连续的一组关键工序，因而，可能存在多个关键块。•目前的领域结构都是基于关键块的，有多种领域操作，但都是基于移动关键块两端的工序。不产生不可行解，效率高。局部搜索算法的不足当遇到局部极值的时候，Localsearch的算法将遇到瓶颈，从而需要更多的策略或更好的算法跳出localoptima。跳坑策略以及ILS跳坑策略：对当前解进行大的改动（扰动）。迭代局部搜索算法：结合跳坑策略形成的算法。禁忌搜索(TabuSearch)提出:由美国工程院院士...