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

由天下分享时间：2024/6/8 14:51:58 加入收藏我要投稿点赞

先进制造管理

报告

遗传算法在作业车间调度问题中的应用

专业：管理科学与工程

时间：2015年1月

第1页

遗传算法在作业车间调度问题中的应用

1作业车间调度问题

所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。

作业车间调度（job-shop）问题可以表述为：设有N个工件在M台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。前提假设：

1. 每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。

2. 不同工件的加工工序可以不同； 3. 所有工件的工序数不大于设备数； 4. 每道工序必须在指定的某种设备上加工； 5. 任何作业没有抢先加工的优先权；

6. 在作业优化过程中既没有新的工件加入也没有取消的工件；

车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。然而，车间调度是一个 NP-Hard 问题，运用穷举法又会大大增加计算量，所以考虑利用遗传算法求解。

第2页

1.1 车间作业调度问题研究的假设条件

在研究一般的车间作业调度问题中往往需要明确两类重要假设条件:

1.工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系;

2.资源(机器)独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。

此外，还有一些辅助假设条件，如下: 1. 各工件经过其准备时间后可开始加工;

2. 不考虑工件加工的优先权，即工件之间没有优先约束关系限制的; 3. 工序允许等待，即前一个工序未完成，则后面工序需要等待; 4. 所有机器处理的加工类型均不同;

5. 工件的加工时间事先给定，且在整个加工过程中保持不变; 6. 缓冲区容量为无穷大。 1.2 车间作业调度问题的数学模型

设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。定义如下：

J:所有工件的集合，J?{J1,J2,?Jn}； M:所有机器的集合，M?{M1,M2,?Mm}；

Pji：工件Ji的工序集合，Pji?{Pji1,Pji2,?Pjipi}；

P:所有工序的集合，此为n?max{P1,P2,?Pn}矩阵。P（i，j）表示i工件的第j道工序。P(i,?)?Pji，表示i工件的所有工序按优先顺序的排列。不足max{P1,P2,?Pn}则置零。