基于改进遗传算法的柔性作业车间调度问题研究

《基于改进遗传算法的柔性作业车间调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Vol.8No.22Nov.2008©2008Sci.Tech.Engng.第8卷第22期2008年M月1671.1819(2008)22-6135-04科学技术与工程ScienceTechnology*andEngineering基于改进遗传算法的柔性作业车间调度问题研究韩文民范吉文•(江苏科技大学经济管理学院.镇江212003)摘要针对柔性作业车间凋度问题的特点•以产品的加工周期最短为目标，提出了一种改进的遗传算法，采用双子串的方式来进行编码，并且基于此给出了独特的交叉和变异法則=同时通过具

2、体的实例仿真分析说明该算法的衣效性。关键词柔性作业车间调度遗传算法交叉算子中图法分类号TP391.73；文献标志码A作业车间调度问题是一类最具一般性的生产调度问题，它是指山m个不同的机器加工n个具有特定加T.路线的丁件•不同的作业具有不同的加工操作和加工顺序，调度的目标是获得菜种生产指标的最优化;而具中的柔性作业车间调度问题是指工件的设备如工路径不是固定的，而是具有可选的路径,这样起加符合实际中的牛产情况。有效的调度方法与优化技术的研究和应用，已经成为先进制造技术实践的基础和关键，所以对它的研究

3、与应用具有重要的理论和使用价值“。柔性作业车间调度问题已经被证明是NP・hard问题⑵，因此很难求得其最优解。近年来，遗传算法在各个优化领域的广泛应用，使得人们开始考虑利用遗传算法求解作业车间调度问题。遗传算法在算法实现方面具备结构上的隐含并行性、计算原理上的随机性和自适应性•对非线性复杂问题具有全局搜索能力，简单通用，鲁棒性强，已经成为学术界和工程界研究的重点⑶。2008年X月7B收到江苏省船舶先进制是技术军事实验室开放星金项目(CJ0708)资助第一作者简介：舛文民(1963—).男，江苏南

4、京人•江苏科技大学教授•研究方向：现代工业工程与生产符理。•通信作K•简介:范吉文(1982—)•男.湖南益阳人.江苏科技大学企业竹理研究生.研究方向:生产卄理亠E-mail：伽jil220@163.com.,1柔性作业车间调度问题的描述及模型建立柔性作业车间调度问题是指:一个加工系统有皿台机器，要加工“种工件。每个工件包含一道或多道工序，工件的工序顺序是预先确定的；每道工序可以在多台不同的机床上加工，工序的加工时间随机床的性能不同而变化。调度目标是为每道工序选择最合适的机器、确定每台机器上各

5、工件工序的最佳加工顺序及开工时间，使系统的某些性能指标达到最优。此外，在加工过程中还需满足如下假设和约束条件。(1)同一时刻同一台机器只能加工一个零件。(2)每道工序在不同机器上的加工时间已知。(3)每个工件在某一时刻只能在一台机器上加工,不能中途中断每一个操作。(4)同一工件的工序之问有先后约束，不同工件的工序之问没有先后约束。(5)不同工件具有相同的优先级。(6)不考虑机器故障等随机因索。作业车间调度的主要任务是寻找到一个基于某种指标意义的最优或次优调度。最常用的指标是最大流程时间Cg的最小

6、化•即完成所有工厚的时间最短。上述柔性作业车间调度问题可以描述为以下模型：目标函数：min

7、maxC.,1=1约束条件：%一T心gM1恤丿H1且X#=1(1)陰-%~S溯M0(2)T'jm~TpsmM伽,Yfuijm=>且X溯=1,X严=1(3)溯=l,(me%)(4)m机器数量;％:工件i的第j道工序的可选机器集;s溯:工件i的第j道工序在机器m上的开始加工时间;/孙:工件i的第j道工序在机器m上的加工时间；丁溯:工件i的第j道工序在机器m上的加工完工时间；y^n:机器尬加工工序J和s的顺序判

8、别条件，当工序丿和5都在机器m上被加工时，如果工件i的第j道工序先于工件P的第5道工序被加工，则Y阿=1,否则岭„肿0；唇：工件i的第j道工序在机器m上加工的判别条件，如果工件i的第j道工序在机器m上加工，则X濟=1,否则X溯=0。其中，式(1)表示工件i的第j道工序必须在第道工序完成后才能开始;式(2)表示工件i的第j道工序在机器皿上的加工时间不为负;式(3)表示任一确定时刻，机器m不能同时加工任意两个不同的工件，也不能同时加工任意两道不同的工序;式(4)表示工件i的第j道工序只能选择在可选机

9、器集中的一台机器上加工。3改进遗传算法的柔性作业车间调度问53.1染色体的编码方式遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体，这一转换操作称为编码。它是染色体和调度解之间进行相互转换，是遗传算法成功实施优化的首要和关键问题*。由于柔性作业车间调度问题不仅需要确定工序的加工顺序，还需要为每道工序选择合适的加工机器。为此本文设计了一种双子串的基因编码方式，第一子串编码表示工序所选加工机器，第二子串编码表示调度次序,用工序加工优先权值标示。具体的编