基于遗传算法的作业车间调度问题研究.pdf

壤步太海硕士学位论文基于遗传算法的作业车间调度问题研究蔡宗琰教授分类号：导师姓名职称申请学位级别论文提交日期学位授予单位袁云龙答辩委员会主席学位论文评阅人摘要作业车间调度问题是许多实际生产调度问题的简化模型是一个典型的—问启发式算法等。遗传算法珿是应用最广泛的优化计算方法中之杂问题的优化比其他优化技术相比存在显著的优势正越来越激起人们的广泛研究与其研究现状、方法介绍了遗传算法的理论基础基于遗传算法的作业车间调度问题等。随着全球经济一体化和知识经济的到来企业间的竞争日趋激烈多工序、小批量的生产任务也成了生产厂家抢占市场的重点。为了增强企业核心竞争力厂家必须改善内部生产管理合理安排工序和利用资源减少工期降低生产成本。因此车间产鞫任侍庠嚼丛绞艿饺嗣堑墓刈ⅰ题近年来各种智能计算方法逐渐被引入到调度问题中如遗传算法、模拟退火算法、一适用于全局搜索等参数优化计算领域也适用于车间作业调度问题。它作为一种非确定性的拟生态随机优化算法得到了广泛的应用。由于其具有不依赖于问题模型的特性、全局最优性、随机转移性和非确定性、隐含并行性等特点因此遗传算法更适合复应用。本文应用遗传算法求解复杂的车间调度问题。首先论述了车间调度问题的重要性及其次针对遗传算法容易出现早熟收敛的问题提出一个评判遗传算法早熟程度的指标同时结合模拟退火算法提出一种改进的自适应遗传算法并将其运用于作业车间调度问题的求解。最后对基于单亲糯惴ń辛搜芯俊５デ滓糯惴ㄈ∠舜骋糯惴ǖ交叉算子采取单亲繁殖方式不要求初始群体具有多样性不存在“早熟”收敛问题计算效率高因此非常适合于求解作业车间调度问题。关键词：车问调度遗传算法自适应单亲糯琣瓵．琱．叩．琣瑂薬甅琲珿甪琫．．—琫．珿瓵．琫甌；”眔篔瑂钏獬：．静瑶衰戈也讲鬯年璋素文电≯多年『滤辍稳／庐＼矿∥写论文独创性声明论文知识产权权属声明孑年本人声明：本人所呈交的学位论文是在导师的指导下独立进行研究工作所取得的成果。除论文中已经注明引用的内容外对论文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表的成果。本声明的法律责任由本人承担。论文作者签名：本人在导师指导下所完成的论文及相关的职务作品知识产权归属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时署名单位仍然为长安大学。Ｃ艿穆畚脑诮饷芎笥ψ袷卮斯娑、第一章绪论车间调度问题概述进对资源的需求量急剧上升资源的有限性问题逐渐摆在了人们面前对资源的合理的某种处理性能指标的方案。所以所谓调度就是为了实现某一目的而对共同使用的资源实行时间分配【。度问题的研究一直在调度理论中占据主导地位。特别是多品种小批量生产车间优化调度是非常困难的课题。近十几年很多领域的研究人员各自用不同的技术和方法对这个问自从十八世纪六十年代在英国爆发工业革命后人类社会的生产力水平出现突飞猛配置与优化利用开始成为一个科学研究的新课题由此也产生了调度问题。调度问题的本质在于多项任务共享特定的资源而有限的资源却无法满足所有任务同时以最优状态独享资源的处理需求因此需要寻求一种优化其中一部分或者整批任务从二十世纪年代开始人们对调度问题进行了大量的研究工作而且对它的研究受到应用数学、运筹学、工程技术等领域科学家的重视。科学家们利用运筹学中的线性规划、整数规划、目标规划、动态规划及决策分析方法研究并解决了一系列有代表意义的调度和优化问题。世纪年代人们开始注意并重视调度复杂性问题的研究提出了用于研究算法有效性和问题难度的计算复杂度理论【许多调度问题被证明为完全问题【。由于企业车间的生产计划与控制问题在所有调度问题中最具典型性所以对车间调问题是生产调度中最为复杂的问题在数学上被归结为难题其理论和方法的研究题进行了为广泛、深入、细致的研究用智能化方法求得实际批量生产调度问题的优化解取得了丰硕的成果。这不仅推动了交叉学科和基础学科的发展而且在现代市场经济环境下对企业或行业提高生产效率和效益也起了很大