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

遗传算法的车间调度算法求解 安晶 2006.4.4 主要内容 Job—shop 调度问题 遗传算法理论 遗传算法在车间调度算法中的求解过程 问题提出 车间作业调度(Job-Shop Scheduling),简称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