基于改进蛙跳算法和AGA的flow shop调度问题研究

基于改进蛙跳算法和AGA的flow shop调度问题研究

论文摘要

生产计划和调度处于计算机集成制造系统的核心位置,它向上对企业的经营战略决策层负责,向下对监控控制层发出控制指令,确保生产的有序进行,是CIMS成功实施与否的关键。生产调度问题关系着企业成本的控制和利益的最大化,对于促进我国的制造业走向全球化、信息化、集成化有着深远的影响。Flowshop调度是一个典型的调度问题,本文着重研究通过设计和改进智能优化算法来解决flow shop调度问题,并通过大量的仿真实验,验证了所提算法的可行性和有效性。对于以Makespan为目标的置换flow shop问题,引入了一种新的智能优化算法蛙跳算法,蛙跳算法融合了SCE (Shuffled Complex Evolution)算法和离散粒子群算法的优良思想,实现了全局的信息共享。针对蛙跳算法容易产生非法调度的问题,设计了一种新青蛙跳跃规则来改善基本蛙跳算法的算法性能,仿真实验表明改进的蛙跳算法比基本的蛙跳算法和遗传算法更加有效。对于加工时间不确定的flow shop调度问题,通过模糊数学的方法来描述加工时间的不确定性,在基本蛙跳算法的基础上,借鉴交换子和交换序的概念,提出了“交换序构造的初始位置随机机制”和“交换子的随机插入机制”这两种追踪策略。通过与遗传算法比较,仿真实验结果验证了改进蛙跳算法在解决具有不确定性加工时间的flow shop问题上的有效性。对于以总流经时间为目标的置换flow shop问题,提出了一种全新的遗传算法,异步遗传局部搜索算法AGA (Asynchronous Genetic Local Search Algorithm)。AGA包含三个阶段:在第一个阶段产生随机的初始种群,其中的一个解由构造型的启发式算法产生;在第二个阶段,种群内的个体两两配对,进行异步进化操作,其中运用了一个简单的交叉算子和一个加强的邻域搜索策略;在最后一个阶段,采用一个重启策略来防止算法陷入局部极小。仿真实验表明,AGA比一些经典的算法和两个最近提出的后启发式算法更加有效,同时对于90个Benchmark问题,AGA得到了89个目前已知的最优解,其中54个是由AGA最新得到的。

论文目录

  • 摘要
  • Abstract
  • 第1章 绪论
  • 1.1 生产调度问题的研究背景及意义
  • 1.2 生产调度问题概述
  • 1.2.1 生产调度问题的定义及特点
  • 1.2.2 生产调度问题的分类及研究现状
  • 1.3 本文的主要创新
  • 1.4 论文的主要研究内容和框架
  • 第2章 生产调度问题的研究方法
  • 2.1 基于规则的调度方法
  • 2.2 基于仿真的方法
  • 2.3 基于控制理论的方法
  • 2.4 基于人工智能的方法
  • 2.4.1 智能专家系统
  • 2.4.2 计算智能
  • 2.4.3 人工神经网络
  • 2.5 本章小结
  • 第3章 基于改进蛙跳算法的flow shop调度问题的研究
  • 3.1 置换flow shop调度问题
  • 3.2 基本的蛙跳算法
  • 3.3 改进的蛙跳算法ISFLA
  • 3.4 仿真实验
  • 3.4.1 仿真实例
  • 3.4.2 参数选择
  • 3.4.3 算法比较与分析
  • 3.5 本章小结
  • 第4章 基于改进蛙跳算法的模糊flow shop调度问题的研究
  • 4.1 模糊flow shop调度问题
  • 4.2 模糊flow shop调度问题的数学模型
  • 4.3 改进的蛙跳算法NSFLA
  • 4.4 仿真实验
  • 4.4.1 仿真实例
  • 4.4.2 参数选择
  • 4.4.3 算法比较与分析
  • 4.5 本章小结
  • 第5章 基于AGA的以TFT为目标的调度问题的研究
  • 5.1 以TFT为目标的flow shop问题的研究现状
  • 5.2 以TFT为目标的flow shop问题的数学模型
  • 5.3 异步遗传局部搜索算法AGA
  • 5.3.1 编码方式和种群的初始化
  • 5.3.2 异步进化机制AE
  • 5.3.3 交叉算子
  • 5.3.4 加强的变邻域搜索
  • 5.3.5 重启机制和收敛准则
  • 5.3.6 AGA算法流程
  • 5.4 仿真实验
  • 5.4.1 AGA参数校正
  • 5.4.2 算法比较与分析
  • 5.5 本章小结
  • 第6章 总结与展望
  • 致谢
  • 参考文献
  • 作者在学期间取得的学术成果
  • 相关论文文献

    标签:;  ;  ;  ;  

    基于改进蛙跳算法和AGA的flow shop调度问题研究
    下载Doc文档

    猜你喜欢