基于遗传算法的车间调度问题.pdf

《基于遗传算法的车间调度问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第32卷第1期计算机工程2006年1月VoL32尬JComputerEngineeringJanuary2006·人工智能及识别技术·文章编号：l00o_3428(2006)0l—l93—2文献标识码：A中图分类号：TP18基于遗传算法的车间调度问题庄新村，卢字灏，李从心(上海交通大学模具CAD国家工程研究中心一七海200030)摘要：基于遗传算法对车问调度问题进行了优化，给出了自适应的遗传算子，进行了遗传算法参数设置。采用这种编码方案、遗传算子和参数使得遗传操

2、作大大简化，能达到有效的调度作用。最后，使用标准实例对算法有效性收敛速度进行了验征，并作了简要分析。关健诃：车间调度；遗传算法；比例选择方法SolvingJobShopSchedulingProblembyGeneticAlgorithmZHUANGXincun，LUYuhao，LICongxin(NationalDie&MouldCADEng．ResearchCenter，ShanghaiJiaotongUniversity，Shanghai200030)[Abstract

3、Thispaperpresent

4、sanintelligentschedulingoptimizationofJob—Shopbyusinggeneticalgorithm，providestheself-adaptivegeneanddefinestheparameterofgeneticalgorithm．ThetlSeofsuchacodingschedule，geneandp~ametersmakethegeneticoperationsquitesimpleFinally，itvalidatestheefectivenesswith

5、standardsamplesandanalyzesitbriefly．[KeywordsIJobshopschedule；Geneticalgorithm；Propertionalmodel车间调度⋯问题是一个历史悠久的问题，对应于生产管理即加工时间最少。图1就是一个以有向图表示的可行调度。系统的短期计划的安排，即实施层次，调度主要解决车间资在图1中3台机器上加工顺序为{(1，5,9)(8,4，2)(7,6，3)}。源的最优安排，优化计划安排，为计划的执行和控制提供指2解JobShop的遗传算法分析导。良好

6、的车间调度能够预先解决生产中的干扰，能够缩短本文求解JobShop调度问题遗传算法的具体设计，主要产品在车间的流动时间，减少在制品库存，保证准时交货。包括染色体编码设计、目标函数选择、遗传算子设计、参数遗传算法利用生物进化机制，在一个较大的初始解空间选择等。中通过优胜劣汰的方法进行优化求解，和其它优化方法相比(1)遗传算法染色体编码不仅寻优能力强而且计算速度快。本文在研究经典JSP问题在解JobShop问题时，如果编码方式选择不当，容易出的基础上，提出一种用遗传算法优化JSP过程的算法，通过现死锁现象。有向图

7、中如果有环的出现就代表死锁现象。仿真可以得到较为令人满意的结果。在产生初始染色体或交叉、变异时都有可能产生死锁染色体，lJobShop问题描述难以避免。产生这样的染色体，在解码时就会遇到困难。JobShop问题可以描述为：设有N个工件在M台机器上设计一个合适的表达解的方法和基于特定问题的遗传算加工，由于工件的加工工艺的要求，每个工件使用机器的顺子，使得不管在初期还是在进化过程中产生的所有染色体都序及其每道工序所花时间已给定，调度问题就是如何安排在将产生可行调度，将是影响遗传算法的各个子阶段的关键步每台机器上工

8、件的加工顺序，使得某种指标最优。具体满足骤。本文中采用的是基于工序的表达方法。这种表达法将调下面条件：度编码为工序的序列，给所有同一工件的工序指定相同的符(1)每一工件在机器上的加工顺序一定。号，然后根据它们在给定染色体中出现的顺序加以解释。由(2)每一台机器每次只能加工一个工件。于这种编码方式在编码的时候就考虑了工件的顺序约束，因(3)每一工件在机器上的加工被称为一道工序，工序加工时间此再解码时就不会出现死锁现象。是固定的。(2)JobShop问题的目标函数(4)工件在机器上被加工时不允许披打断。遗传算法中

9、使用适应度这个概念来度量群体中各个个体(5)机器与工件可能开始时间都为0。在优化计算中有可能达到、接近或有助于找到最优解的优良程度。一般来说，在运行的初期阶段，适应度差距比较大，有可能导致在选择过程中几个个体占有很高比例，从而使遗传算法产生早熟现象。而在运行的后期阶段，群体的个体适应度可能非常接近，大部分个体的竞争力和最佳个体相差无几，可能进入随机选择过程。由此，本文采用线性尺度变换，图13×3的J