遗传算法在作业车间调度问题中的应用——先进制造管理作业详解.docx

先进制造管理 报告 遗传算法在作业车间调度问题中的应用 专业：管理科学与工程 时间：2015年1月 遗传算法在作业车间调度问题中的应用 1 作业车间调度问题 所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。 作业车间调度（job-shop）问题可以表述为：设有N个工件在M台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。 前提假设： 1. 每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。 2. 不同工件的加工工序可以不同； 3. 所有工件的工序数不大于设备数； 4. 每道工序必须在指定的某种设备上加工； 5. 任何作业没有抢先加工的优先权； 6. 在作业优化过程中既没有新的工件加入也没有取消的工件； 车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。然而，车间调度是一个 NP-Hard 问题，运用穷举法又会大大增加计算量，所以考虑利用遗传算法求解。 1.1 车间作业调度问题研究的假设条件 在研究一般的车间作业调度问题中往往需要明确两类重要假设条件: 1.工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系; 2.资源(机器)独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。 此外，还有一些辅助假设条件，如下: 1. 各工件经过其准备时间后可开始加工; 2. 不考虑工件加工的优先权，即工件之间没有优先约束关系限制的; 3. 工序允许等待，即前一个工序未完成，则后面工序需要等待; 4. 所有机器处理的加工类型均不同; 5. 工件的加工时间事先给定，且在整个加工过程中保持不变; 6. 缓冲区容量为无穷大。 1.2 车间作业调度问题的数学模型 设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。定义如下： J:所有工件的集合，； M:所有机器的集合，； ：工件Ji的工序集合，； P:所有工序的集合，此为矩阵。P（i，j）表示i工件的第j道工序。，表示i工件的所有工序按优先顺序的排列。不足则置零。 （1.1） :机器顺序阵，此为矩阵。（i，j）表示i工件的第j道工序的机器号，表示i工件的所有工序按优先顺序加工的各机器号的排列。若某工件的工序数不足则置零。 （1.2） T:加工时间阵，此为矩阵。T(i, j)表示工件i的第j道工序在（i，j）上的加工时间。同样地，如果某工件的工序数不足则置零。 （1.3） ：工件排列阵，此为矩阵。表示在i机器上排在第j位加工的工件号，表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数不足则置零。事实上，工件排列阵就是调度的一种表示形式。 由此，我们可以给出一般性的车间作业调度数学模型的定义: 如果对应于一个确定的，满足或。即使得目标函数取值最小(或最大)，且与相容，则称为车间作业调度问题在此目标函数下的最优解。 生产调度问题存在多种优化目标或者综合优化目标，调度问题的优化目标通常从两个方面来考虑:生产成本和生产时间。调度问题从生产成本方面来考虑，其优化目标有:库存最少、在制品最少、设备利用率最高等;从生产时间方面来考虑，其优化目标有:最大程度满足交货期、最小完成时间、最小流动时间和最小等待时间等。 2 遗传算法 遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的。它摒弃了传统的有哪些信誉好的足球投注网站方式，模拟达尔文的遗传选择和自然淘汰的生