学位论文 > 优秀研究生学位论文题录展示

基于混合邻域搜索算法的分布式车间调度系统的研究与实现

作　者: 蓝萌
导　师: 徐汀荣
学　校: 苏州大学
专　业: 管理科学与工程
关键词: 邻域搜索遗传算法模拟退火算法免疫机制分布式模型
分类号: O224
类　型: 硕士论文
年　份: 2010年
下　载: 64次
引　用: 2次
阅　读: 论文下载

内容摘要

随着制造型企业生产规模的不断扩大,生产过程也变得日益复杂,企业需要借助计算机来辅助企业进行生产的安排,提高企业生产的效率。然而在现实生产调度过程中,面临着复杂的加工环境和资源约束,需要设计出一种有效地算法来解决生产调度问题。车间调度问题属于组合优化问题,解决这类问题的方法有很多,邻域搜索算法是目前应用最广泛的一类算法,而其中遗传算法又是应用最成功的一种算法。本文通过对多目标柔性车间调度问题的研究,针对传统遗传算法的缺陷进行了改进,并结合模拟退火算法和免疫机制,设计出一种基于改进混合邻域搜索算法的车间调度算法。该算法通过在初始阶段选择种群空间中的一部分染色体,通过判断染色体相似度来打散染色体分布,提高算法的全局搜索能力;并对剩下的染色体采用免疫机制,利用已知问题的一些特征信息来引导生成一些高质量的染色体,为后续的进化过程奠定良好的基础。同时针对算法进化速度不均匀的问题,提出了一种自适应的交叉变异概率,针对不同适应值的染色体给予不同的交叉变异概率,并且,概率会随着进化代数的增加而逐渐减小,在算法后期加快收敛速度。在选择阶段,引入模拟退火机制和免疫机制相结合的策略,避免算法搜索陷入局部极小而无法找到更优解,并保存每一代的最优染色体。最后证明了算法的有效性。接着围绕车间调度算法构建了分布式的车间调度系统,使其能在实际中得到应用。通过采用Web service+EJB的技术规范,面向服务的松耦合体系结构来设计系统。详细介绍了整个系统的结构和实现原理,并分别对服务器端、Web模块、客户端的设计进行了详细描述。最后对算法和分布式系统进行了性能测试和评估,通过对算法进行多次测试,并与标准遗传算法及其他一些混合算法的比较,证明了改进型混合邻域搜索算法具有更好的搜索性能。最后,在不同技术标准搭建的客户端中,对服务器端进行了远程调用的测试,并取得了预期的效果。

全文目录

中文摘要  4-5
Abstract  5-11
第一章前言  11-17
  1.1 课题研究背景  11-12
  1.2 国内外研究现状  12-15
    1.2.1 车间调度算法的研究现状  12-14
    1.2.2 分布式系统的研究与应用  14-15
  1.3 本文的研究意义及主要工作  15-16
  1.4 本文的组织结构  16-17
第二章调度优化算法与分布式技术概述  17-32
  2.1 调度优化算法概述  17-22
    2.1.1 邻域搜索算法概述  18-21
      2.1.1.1 遗传算法概述  18-19
      2.1.1.2 模拟退火算法概述  19-21
    2.1.2 免疫算法概述  21-22
  2.2 分布式计算概述  22-24
  2.3 分布式技术概述  24-31
    2.3.1 EJB 技术规范  24-25
    2.3.2 Web Service 技术框架  25-31
      2.3.2.1 XML 介绍  26-27
      2.3.2.2 SOAP 协议介绍  27-28
      2.3.2.3 WSDL 语言介绍  28-29
      2.3.2.4 UDDI 介绍  29-30
      2.3.2.5 AXIS 介绍  30-31
  2.4 本章小结  31-32
第三章车间调度算法设计  32-51
  3.1 多目标柔性 Job-Shop 调度问题描述  32-35
    3.1.1 传统 Job-Shop 调度问题描述  32-34
    3.1.2 多目标柔性车间调度问题描述  34-35
  3.2 标准遗传算法  35-39
    3.2.1 遗传算法的概念  35
    3.2.2 遗传算法的基本操作  35-38
    3.2.3 标准遗传算法的基本步骤  38
    3.2.4 标准遗传算法优缺点总结  38-39
  3.3 改进混合邻域搜索算法的设计  39-48
    3.3.1 构造初始解  39-41
    3.3.2 编码  41-42
    3.3.3 遗传算子的设计  42-46
      3.3.3.1 自适应交叉和变异概率  42-43
      3.3.3.2 交叉算子  43
      3.3.3.3 变异算子  43-44
      3.3.3.4 选择算子  44-46
    3.3.4 性能指标的选择  46
    3.3.5 混合邻域搜索算法流程  46-48
  3.4 算法有效性证明  48-50
    3.4.1 遗传算法与马尔科夫链  48
    3.4.2 有限离散状态空间上调度算法的收敛性分析  48-50
  3.5 本章小结  50-51
第四章分布式车间调度系统的实现  51-68
  4.1 面向服务的体系结构  51-52
  4.2 基于Web Service 的分布式系统构架  52-53
  4.3 Web Service 实现分布式服务的基本原理  53-54
  4.4 服务器端的详细设计  54-62
    4.4.1 业务逻辑功能的设计  56-58
    4.4.2 持久化存储管理设计  58-62
    4.4.3 EJB Session Bean 与EJB CMP 集成  62
  4.5 Web 模块设计  62-65
  4.6 客户端的详细设计  65-67
  4.7 本章小结  67-68
第五章性能测试与评估  68-80
  5.1 典型 Job-Shop 问题的研究和测试  68-69
  5.2 车间调度算法的测试和性能评估  69-73
  5.3 分布式车间调度系统的测试  73-79
  5.4 本章小结  79-80
第六章总结与展望  80-82
  6.1 本文总结  80-81
  6.2 工作展望  81-82
参考文献  82-86
攻读学位期间发表(录用)论文  86-87
致谢  87-88

基于混合邻域搜索算法的分布式车间调度系统的研究与实现

内容摘要

全文目录

相似论文