一种混合流水车间调度方法

摘要

本发明涉及一种混合流水车间调度方法，包括以下步骤：将部件按照所需工件所在工件族的不同分成多个部件集；为每个部件集创建新的批次并根据热处理炉的容量组批；在分批之后，为每个批次和所有机器编号，并为每个阶段编码，每个阶段均包含两段染色体，第一段染色体为批次号，第二段染色体为批次对应的机器编号；用户在满足机器限制的条件下随机生成染色体；选出N个染色体，对选出的N个染色体两两进行交叉操作，并对产生的每个染色体执行变异操作，之后对染色体进行修复；重复选择、交叉、变异、修复的步骤直至达到最大迭代次数。本发明能够处理存在装配对并行批处理阶段分批影响的混合流水车间问题，并能保证算法运行效率。

主权项

一种混合流水车间调度方法，包括以下步骤：第1步：将部件按照所需工件所在工件族的不同进行分类，形成多个部件集；第2步：选择一个未扫描的部件集；若所有部件集已扫描，则结束分批，转第6步开始编码；第3步：为该部件集创建新的批次，批次数为包含的工件族数；批次的容量即热处理炉的容量；同一个部件集中的部件分为多个组，每个组包含满足某种装配关系的最少数量的工件；第4步：若在该部件集中还有工件未分批，则选择放入各批后剩余容量平均差值最小的一组工件，将该组工件放入相应的批次中，并从部件集中删除该组工件；循环执行此步骤，直到剩余的任何工件组都无法同时满足每个批次的容量限制；如果所有部件均已分批，标记该部件集为已扫描，转第2步；第5步：若还有工件未分批且没有工件组可以同时满足每个批次的容量限制，则锁定这些批，转第3步。第6步：在分批之后，为每个批次和所有机器编号，并为每个阶段编码，每个阶段均包含两段染色体，第一段染色体为批次号，第二段染色体为批次对应的机器编号；对于装配阶段，将可装配的若干批次视为一个批次集，并使用分隔符分隔相邻批次集，在进行后续操作时将批次集视为一个整体考虑；所有阶段的编码按照阶段顺序组合在一起便构成了整体的染色体编码组；第7步：用户设置种群数量，然后在满足机器限制的条件下随机生成染色体，生成的数量与种群数量相同；第8步：选择：进行选择操作要遍历种群中的每一个染色体，计算每个染色体rk相应的完工时间J(rk)，然后计算得到染色体的适值即所有染色体J(rk)的最大值减去当前染色体J(rk)得到的差值；染色体的选择采用概率选择法，用线性排序的方法来确定个体被选中的概率，在计算每个个体的适应度值后，根据适应度值对群体中的个体按从大到小的顺序进行排序，然后根据排序得到被选中的概率，第i个个体被选中的概率和其适值成正比，染色体被选择的概率为： p i = 2 ( N - i + 1 ) N ( N + 1 ) 其中i=1，2，…，N，N为种群的大小，i为染色体在适值排序中的序号；每代选出N个染色体，首先按照之前排序的顺序选出排在第一和第二位的两个染色体作为优质染色体直接保留到下一代，然后对剩下的染色体按照轮盘赌的方法选出其余N‑2个染色体；第9步：交叉：对选出的N个染色体两两进行交叉操作，一次交叉操作的步 骤如下：Step 1：用户设置交叉概率，产生一个随机数，若小于交叉概率则转Step2，否则不进行交叉操作；Step 2：在每个阶段的批调度顺序染色体中分别随机选择两个不同的点，在装配阶段只能选择起止点和分割符；Step 3：交换两个父代染色体中选中的基因块，产生两个子代；Step 4：找出缺少和重复的基因值；Step 5：根据映射关系修正两个子代染色体，将重复的基因值换成缺少的基因值；Step 6：在step5产生的两个子代染色体每个阶段的机器顺序染色体中分别随机选择两个不同的点，交换选中的基因块，产生两个新的子代；第10步：用户设置变异概率，对第9步产生的每个染色体执行变异操作：产生一个随机数，当产生的随机数小于变异概率时对一个父代染色体每段批调度顺序染色体进行两点变异，即随机指定两个位置并互换对应位置染色体；对每段机器顺序染色体进行单点变异，通过随机指定一个位置并在满足机加阶段机器约束的条件下将该值换为随机数；第11步：由于机加阶段存在机器约束，工件只能在阶段内的某些机器上进行加工，并非所有机器均可加工，因此在进行交叉和变异操作时，会产生机器和工件不相符的染色体，有必要对这种染色体进行修复，采用的修复策略是找到不符合机器限制的染色体，并找出具体的位置，之后任意选出一个符合机器限制的机器号，并用这个选中的数字替换原来的数字；第12步：判断是否超过最大迭代次数，规模越大迭代次数越大；若没有超过，转第8步，若超过，结束，输出最后一代的最优解，根据最优解确定组批和调度策略。