遗传算法在作业车间调度问题中的应用

发布时间：2017-12-06 07:24

本文关键词：遗传算法在作业车间调度问题中的应用

【摘要】：生产调度问题的研究有助于完善产品的加工线路的优化,提高设备的利用率,减少工序的等待时间,从而能够降低企业的生产成本,为企业管理者做出正确决策提供借鉴.作为生产调度问题之一的车间作业调度问题(Job Shop Scheduling Problem, JSP)的研究开始于上世纪五十年代,Johnson对两台机床的生产调度进行了研究并提出了解决车间调度部分特殊问题的优化算法.由于随着问题规模的扩大,该问题求解的复杂性呈指数增长,导致传统的分支定界法、动态规划法等并不适用对其进行求解.随着近年来模拟退火、禁忌搜索、遗传算法等群体优化算法的出现,为有效解决这一问题提供了契机.自从Davis于1985年利用遗传算法成功解决调度问题以来,遗传算法就因其智能性、全局性的特点被学者们大量应用于生产调度领域.车间作业调度就是解决n个工件如何在m台机器上加工的问题.其中已知每一个工件的具体加工顺序、每道工序加工所需的时间以及每个工件所包含的工序,在满足相应约束条件的前提下,目标是确定每台机器上各个工件的加工顺序,以保证某项性能指标最优,一般都是要求使加工时间达到最短.采用遗传算法对作业车间调度进行处理,根据作业车间调度问题的特点,对作业车间调度问题选择了一种能够适用且较为简单的编码方式,展示出作业车间调度问题的特有性质,使染色体当中的每一个数字即表示了工件的编号又可以确定这是这个工件的第几道工序.根据这种编码方法的特点,提出了不破坏稳定性交叉和变异算子,从而保证得到的都是作业车问调度问题的可行解.适应度函数使用时间的倒数,目标函数选择加工时间最短,并将每代中最优的个体保存下来.之后通过程序实现,并应用其解决ft-0和ft-0标准问题,对所采用的算法进行可行性的检验,证明了该算法的有效性.最后分析算法中存在不足和介绍了作业车间调度问题在实际中可能遇到的各种问题.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TB497;TP18

【共引文献】

中国期刊全文数据库前10条

1 陈武谨;陈代良;金李;;遗传算法在隧洞开挖爆破参数优化中的应用[J];湖北水力发电;2008年03期

2 孙亮;于雷;李战武;冯国强;;威胁条件下机载纯方位定位的观测器优化轨迹[J];中北大学学报(自然科学版);2010年05期

3 杨策平;;单交叉路口交通分布的一个优化模型及其算法[J];湖北工业大学学报;2007年06期

4 王志良;陈海涛;;水资源管理多属性决策分析研究综述[J];华北水利水电学院学报;2007年05期

5 凌雄娟;;基于遗传算法的函数学习[J];信息通信;2008年03期

6 王何舟;顾洁;张颖;肖金星;;基于集对分析的中压配电网网架优化规划[J];华东电力;2008年08期

7 葛折圣;刘柱;黄晓明;;基于神经网络理论的沥青混合料疲劳性能的预测模型[J];华东公路;2004年Z1期

8 刘红梅;;遗传算法求解TSP问题[J];信息技术;2007年08期

9 李小华;熊禾根;;基于粒子群算法的车间作业调度问题[J];信息技术;2009年07期

10 苏仰娜;基于遗传算法的优化排课系统[J];河南大学学报(自然科学版);2005年01期