基于.遗传算法求解作业车间调度问题-生产运作实践

《基于.遗传算法求解作业车间调度问题-生产运作实践》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、生产运作实践大作业24目录目录0问题一：基于遗传算法求解作业车间调度问题21．问题介绍21.1作业车间调度问题表述21.2作业车间调度问题研究的假设条件21.3车间作业调度问题的数学模型32.基本遗传算法42.1遗传算法的基本思路42.2基本遗传算法参数说明43.用遗传算法对具体问题的解决53.1参数编码53.2初始种群的生成63.3个体的适应度函数63.4遗传算子的设计73.5遗传算法终止条件84．模型的求解85．结论总结106.附录10问题二：邮政运输网络中的邮路规划和邮车调度181.问题描述182.

2、模型建立182.1模型的基本假设182.2符号说明192.3模型分析202.4模型的建立203.模型的求解213.1求解思路213.2求解算法2224问题一：基于遗传算法求解作业车间调度问题1．问题介绍1.1作业车间调度问题表述作业车间是指利用车间资源完成的某项任务，在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对作业车间调度问题进行一般性的描述:假定有N个工件，要经过M台机器加工,一个工件在一台机器上的加工程序称为一道

3、“工序”，相应的加工时间称为该工序的“加工时间”,用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程,用“加工顺序”表示各台机器上各个工件加工的先后顺序。在车间作业调度问题中，每个工件都有独特的加工路线，我们要解决的问题就是如何分配N个零件在M个机器上的加工顺序以使得总的加工时间最短。1.2作业车间调度问题研究的假设条件在研究一般的作业车间调度问题中往往需要明确两类重要假设条件:1.工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反

4、映了工件不同工序间的时序关系;2.资源独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。根据上面以及求解方便，我们做出以下具体假设：1.每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。2.不同工件的加工工序可以不同；3.所有工件的工序数不大于设备数；4.每道工序必须在指定的某种设备上加工，所有机器处理的加工类型均不同；5.在作业优化过程中既没有新的工件加入也没有取消的工件；6.不考虑工件加工的优先权，即工件之间没有优先约束关系限制的

5、；7.工序允许等待，即前一个工序未完成，则后面工序需要等待；8.工件的加工时间事先给定，且在整个加工过程中保持不变。1.3车间作业调度问题的数学模型24建立车间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了基础。假设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。我们定义以下基本数学符号［6］：J:所有工件的集合，；M:所有机器的集合，；：工件Ji的工序集合，；P:所有工序的集合，此为矩阵。P（i，j）表示i工件的第j道工序。，表示i工件的

6、所有工序按优先顺序的排列。不足，那么其空余的位置用0填满。（1.1）:机器顺序阵，此为矩阵。（i，j）表示i工件的第j道工序的机器号，表示i工件的所有工序按优先顺序加工的各机器号的排列。注意:如果某工件的工序数不足，那么其空余的位置用0填满。（1.2）T:加工时间阵，此为矩阵。T(i,j)表示工件i的第j道工序在（i，j）上的加工时间。同样地，如果某工件的工序数不足，那么其空余的位置用0填满。（1.3）：工件排列阵，此为矩阵。表示在i机器上排在第j位24加工的工件号，表示i机器上依次加工的各工件的排列。同

7、上，如果某工件的工序数不足，那么其空余的位置用0填满。事实上，工件排列阵就是调度的一种表示形式。由此，我们可以给出一般性的车间作业调度数学模型的定义:如果对应于一个确定的，满足或。即使得目标函数取值最小(或最大)，且与相容，则称为车间作业调度问题在此目标函数下的最优解。2.基本遗传算法遗传算法是一种基于自然群体遗传演化机制的高效探索算法，由美国学者Holland于1975年首先提出来的，通过模拟达尔文的遗传选择和自然淘汰的生物进化过程来求解。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编

8、码成符号串形式，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。2.1遗传算法的基本思路1.首先确定问题的求解空间；2.将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；3.计算当前群体中每个个体的适应度函数值，然后运用选择、交叉、变异