基于遗传算法的车间调度方法

《基于遗传算法的车间调度方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法的车间调度方法工学院：黄颂志指导教师：胡燕海摘要：本文针对通用作业计划（USP）问题，在该数学模型的基础上，讨论了遗传算法在解决USP问题中的应用过程。论文涉及到数学模型建立、遗传编码、遗传操作等多方面的问题，提出了一种二层次编码方案，然后针对这种编码方式实现具体的遗传操作，使变异操作过程中尽量实现种群多样性，而交叉操作不失继承性，最后利用Matlab6.5进行程序实现，通过与启发式算法结果的比较验证了该算法的可行性和有效性。关键词：通用作业计划遗传算法死锁启发式算法生产调度，即对生产过程

2、进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机发展的核心。传统的作业计划一般分为开放作业计划（OpenShopschedulingProblem,OSP）[1]、异顺序作业计划（JobShopschedulingProblem,JSP）[2]、流水作业计划（PermutationFlowShopschedulingProblem,FSP）[3]和混合流水作业计划（HybridFlowShopschedulingProblem,HFSP）[4]。以

3、往对作业计划的研究一般都按以上四种基本作业方式独立的进行，而在生产实践中，制造系统往往包括多种作业方式，因此单独研究的应用价值受到很大的限制。一．通用作业计划模型由于单一作业计划模型应用价值的有限性，因此本文旨在建立用于上述四种基本作业方式及其组合系统构成的通用作业计划模型[5]（UniversalShopschedulingProblem,USP）。模型描述如下：N个工件在具有M台机器的加工环境中加工，这里的每个工件可以分为I道工序，对于任一道工序i（i∈（1,2,…I）），分别对应有台并行机可以完

4、成该道工序（这里我们称由台加工功能相同的并行机组成的机器集合为一个作业单元），显然=M。其中这里的可以是一台也可以是多台并行机器。每个工件均有多种可以选择的作业单元路径，每个作业单元路径可包含不同的加工操作工序，而且对于任一个作业单元，每台并行机都有可能被选择为加工机器。要求为每个工件确定合适的加工工艺路径，即由加工计划限定的作业单元路径以及每一作业单元中的加工机器选择，使得最大流程时间最小化。以上描述的通用作业计划模型的通用性主要表现为以下三点：首先它可以解决传统的单一作业计划；其次它可以解决包含所

5、有作业计划的混合作业计划；再次它的最一般模型就是含并行机的开放式作业计划。二．遗传算法通用作业计划的最一般模型其约束比传统的单一作业计划模型要弱的多，因此其搜索空间也比传统单一作业计划模型要大的多。遗传算法正是针对这种搜索规模十分庞大，而传统纯数学方法无法解决的问题而提出来的一种概率搜索算法。标准遗传算法的主要步骤[5]如下：步骤1：令k=0，随机产生N个初始种群P（0）。步骤2：评价P（k）中各个体的适配值。步骤3：判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行以下步骤。步骤4：令m=0。

6、步骤5：根据适配值的大小以一定的方式执行复制操作来从P（k）中选取两个个体。步骤6：若交叉概率Pc>ξ∈[0，1]，则对选中的个体执行交叉操作来产生两个临时个体；否则将所选中父代个体作为临时个体。步骤7：按变异操作Pm对临时个体执行变异操作产生两个新个体放入P（k+1），并令m=m+2。步骤8：若m

7、体的适配值；交叉操作通常交换两父代个体的部分信息构成后后代个体，使得后代继承父代的有效模式，从而有助于产生优良个体；变异操作通过随机改变个体中某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。三．遗传算法在通用作业计划问题中的应用由于通用作业计划模型过于复杂，解空间过于庞大，因此用纯规划方法来解决通用作业计划似乎很难求得最优解。介于遗传算法的特点，本文提出用GA来解决通用作业计划，具体实现过程如下。1．遗传编码由于本文提出的通用作业计划（USP）包含了四种基本作业方式及其组合系统，因此其编码

8、与单独的基本作业方式相比要复杂。本文提出一种基于作业单元的矩阵编码，利用矩阵的元素和位置信息，清楚的表达了（USP）模型。其基本思想是把调度过程分成两次：第一、首先给每一个工件的每道工序分配作业单元（其是由一组加工功能相同的机器组成）；第二、一旦确定了作业单元的归属，那么就可以再对选择该作业单元的工件分配并行机；其实第一步实现的是OSP调度，而第二步则是实现了HFSP调度，而其它两种情况都是以上两种调度的特例，因此也被以上的模型所囊括。因此本文采用两层次