车间作业调度(job_shop_scheduling)讲解

《车间作业调度(job_shop_scheduling)讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、车间调度算法(jobshopscheduling)彭博2012-11-21主要内容Job—shop调度问题遗传算法理论遗传算法在车间调度算法中的求解过程问题提出车间作业调度(Job-ShopScheduling),简称JSS,是一个典型的NP难问题，是OperationResearch领域中研究的重要课题。它的研究不仅具有重大的现实意义，而且具有深远的理论意义。长期以来，JSS研究的方法始终以启发式算法为主导，绝大部分的JSS研究工作也都围绕着启发式算法进行，如基于启发式算法的JSS仿真系统，基于启发式算法的并行JSS系统，基

2、于启发式算法的JSS专家系统，等等，尽管这些研究取得了一定的应用效果，但是却存在着难以克服的弱点，如计算规模不可能较大，寻优结果不具备全局特性等等。近年来，又有学者提出了基于神经网络的车间作业调度系统，但此种方法在JSS规模较大时，却存在着计算速度慢与结构参数难以确定的弱点。由此可见，要想进一步研究JSS,选择一种有效的方法极为必要。问题描述：假设有n个工件{J1,J2,…,Jn}要在m台机器{M1,M2,…,Mm}上进行加工。每个工件以一定的次序在所有的机器上轮流加工。每个工件分成m个工序，而每个工序对应了相应的加工机器。其

3、中，工序的加工时间给定。J1:M1M2M3J2:M3M1M2J3:M2M3M1工序1工序2工序3约束工件上约束：每个工件上的工序只能在上一个工序执行结束以后，才能开始执行下一个工序。机器上约束：每台机器每一个时刻最多只能执行一个工件，且该工序的执行时间是非抢占的。最大完工时间(Makespan)：完成所有工序所需要的总时间。J1:M1M2M3J2:M3M1M2J3:M2M3M1工序1工序2工序3目标有M台机器及N个工件，由于工件的加工工艺的要求，每个工件使用M台机器的次序以及每道工序所花费的时间已经给定。如何安排在每台机器上工

4、件的加工顺序，使得总的完工时间(Makespan)最小。Job—shop调度问题的实际应用在解决实际问题的时候，“工件”和“机器”可以拓展成相应的问题描述。譬如：在生产车间当中，把一个零件或是一组零件看是需要加工的“工件”，而把加工用的车床看成是“机器”；在飞机调度问题中，可以将若干个不同的飞机看成“工件”，而将飞机需要进行的操作，看成是需要操作的“机器”。因而，jobshopscheduling问题的实际应用是非常广泛的。遗传算法在解Job-shop调度问题方面的研究现状由于Job-Shop调度问题是一个NP难题，而遗传算法

5、为求NP难度问题的近似解提供了一种有效手段，所以现在许多人都致力于用遗传算法解决Job-shop问题，各有特点。但就目前来看：(1)由于Job-Shop调度问题的特殊性，编码机制显得尤为重要，因为编码机制选择不当，遗传算法的杂交、变异算子很容易破坏原加工顺序。(2)死锁问题也是一个重要问题，如果处理不当，死锁的出现是无法预料的。(3)收敛性及收敛速度问题，应用GA解Job-Shop调度问题时很少有人考虑这两个问题，所以得到的结果与最佳值的接近程度无理论保证。Job-shop的求解方法局部搜索（LocalSearch）禁忌搜索

6、（TabuSearch）遗传算法（GeneticAlgorithm）混合进化算法(MemeticAlgorithm)局部搜索算法领域结构（Neighborhood）:将一个初始解进行微小变动以后，产生的解的集合。Neighborhood局部搜索算法从一个初始解开始，每次从领域结构中选择一个最好的邻居解作为下一个初始解，迭代搜索解空间的过程。局部搜索算法核心：领域结构的构造。在Job-shop中，对所有机器上的每个工件都考虑其领域结构，效率是非常低下的,也可能导致不可行解的产生。通常是考虑基于关键路劲的领域结构构造方法。关键

7、路径：调度序列中的最长路径，它制约着整个调度的完工时间。局部搜索算法关键块关键块：连续的一组关键工序，因而，可能存在多个关键块。目前的领域结构都是基于关键块的，有多种领域操作，但都是基于移动关键块两端的工序。不产生不可行解，效率高。局部搜索算法的不足当遇到局部极值的时候，Localsearch的算法将遇到瓶颈，从而需要更多的策略或更好的算法跳出localoptima。跳坑策略以及ILS跳坑策略：对当前解进行大的改动（扰动）。迭代局部搜索算法：结合跳坑策略形成的算法。禁忌搜索(TabuSearch)提出:由美国工程院院士，冯若依

8、曼理论奖获得者FredGlover最先在1986年提出TabuSearch算法。TabuSearch:将之前搜索过的解禁忌，每次只选择没被禁忌的解或满足解禁策略的解。因而，它可以接受比自身差的解，从而跳出局部极值点，去搜索新的解空间。解禁策略：遇到一个虽被禁忌，但却比历史最优