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

基于自治与协商机制的柔性制造车间智能调度技术研究

作　者: 王世进
导　师: 奚立峰；周炳海
学　校: 上海交通大学
专　业: 机械工程
关键词: 柔性制造系统调度动态重调度自治与协商调度 Agent Holon pi-演算合同网协议强化学习 Q-学习过滤定向搜索
分类号: TH165
类　型: 博士论文
年　份: 2008年
下　载: 498次
引　用: 5次
阅　读: 论文下载

内容摘要

柔性制造环境下车间生产调度问题具有复杂性、不确定性、多目标、多约束、多资源相互协调等特点。鉴于其重要的理论和实际意义,一直以来是生产管理和组合优化领域的重点和难点课题。本论文在充分吸收近十余年间基于Agent或Holon的非集中式生产调度最新研究成果基础上,以具有生产加工柔性的、多单元、离散作业型(Job Shop)制造车间为研究对象,围绕基于Holon的协商与自治调度关键技术(实体封装、控制体系结构、协商机制和核心算法)展开研究,提出了基于Holon概念模型的、集成强化学习机制的合同网协议和改进过滤定向搜索算法的自治与协商智能调度技术,以提供实用有效的求解方法、改善柔性制造车间适应内部动态环境和外部市场快速变化的能力。具体地,本文的主要内容可概括为:1.首先从基于Agent或Holon的自治与协商调度的关键技术(实体封装、控制体系结构、协商机制和核心算法)角度详细综述了近些年间基于Agent或Holon的自治与协商生产调度、核心技术的研究现状和存在问题,引出本文研究的出发点和意义;2.针对可靠性、可扩展性和适应性等要求,提出了基于Holon的柔性制造车间控制体系结构,描述了组件Holon的结构模型、数据和功能关系、信息传递模型和通信语言基本规范,并从软件体系结构的观点出发,运用π演算对其进行了形式化描述和分析,为基于Holon的体系结构设计和分析奠定基础;3.针对传统制造合同网协议缺乏优化和动态学习能力这一问题,将强化学习工具之一的Q-学习算法与制造合同网协议集成,形成CNP-QL(Contract Net Protocol-Q Leaning)协商机制,以提高Holon适应动态环境的实时协调调度能力。详细定义了CNP-QL机制的消息描述、策略决策过程、学习迭代过程和CNP-QL机制中Q-学习算法的各个要素(包括状态确定准则、状态空间划分、奖惩函数设计和搜索策略定义等)。最后,单元Holon和产品Holon之间通过CNP-QL机制协商,用于解决具有柔性工艺路径的多单元间的任务动态协调分配问题,并通过仿真实例与纯CNP机制进行了比较分析,验证了该机制的有效性;4.调度算法是单元自治决策的引擎。在单元Holon任务协调分配后,提出了基于改进过滤定向搜索启发式算法HFBS(Heuristic based on Filtered-Beam-Search)的单元自治调度机制。构建了基于HFBS的单元自治调度决策模型。针对任务协调分配后形成的柔性Job Shop调度问题(Flexible Job-shop Scheduling Problem,FJSP),建立了面向多目标FJSP问题的数学规划模型并对模型进行分析讨论。为了有效解决FJSP问题,详细定义了HFBS四个搜索策略因素:(1)解空间的搜索树表述;(2)分枝策略;(3)定向搜索宽度和定向过滤宽度的确定;(4)评价函数的构造。最后,在分析策略因素对算法性能影响的基础上,就FJSP领域的标杆数据(Benchmark)和大量随机仿真数据,分别与现有的其它基于人工智能的启发式算法和调度规则进行了分析比较,说明了算法的有效性;5.为了使单元自治调度实现持续优化,提高自治调度对不可预见或随机的内外扰动事件(如机床故障、新订单进入等)的实时适应能力,在系统化阐述动态重调度整体理论框架体系(包括重调度环境、策略、方法和技术)的基础上,提出柔性制造车间单元内的动态重调度决策过程,对基于过滤定向搜索的启发式核心算法进行局部/全局评价函数和分枝策略两方面的扩展以更好地集成作业交货期和优先权重,并从动态重调度对算法响应能力方面考虑,分析了算法的时间复杂性。最后,通过一系列实例仿真说明了基于过滤定向搜索算法能实现面向典型扰动的动态重调度并确保调度性能和反应效率。6.最后,在JADE平台上,设计和开发了综合的原型仿真系统。以JADE Agent表述和实现了所定义的Holon之间交互和内部自治算法的控制技术,为将来基于自治与协商机制生产调度的工业化应用尝试可行的设计实现。本文的研究成果在一定程度上推进和丰富了基于Holon的协商与自治调度方法关键技术的研究,有利于改善企业的科学生产管理和控制水平,对提高生产绩效和综合市场竞争能力具有一定的指导作用。同时,在改进和深化的基础上,本文研究思路和成果对于其它组合优化问题和复杂调度问题具有良好的求解潜力和应用前景。本文在研究过程中得到了国家863项目(No.2003AA414120)、柔性制造系统技术国家重点实验室项目(No.51458060104JW0316)、2006教育部新世纪人才项目的大力支持和资助,在此表示衷心的感谢。

全文目录

摘要  3-5
ABSTRACT  5-12
第一章绪论  12-23
  1.1 课题的研究背景及意义  12-20
    1.1.1 新型制造模式哲理  12-13
    1.1.2 制造系统生产调度问题的复杂性  13-14
    1.1.3 制造系统车间生产调度面临新挑战  14-16
    1.1.4 基于自治与协商机制的调度技术  16-20
    1.1.5 课题的研究意义  20
  1.2 论文的研究目标与主要内容  20-22
  1.3 论文的组织结构  22-23
第二章基于自治与协商调度的核心技术现状研究  23-46
  2.1 引言  23
  2.2 Agent和Holon  23-28
  2.3 基于Agent或Holon的制造控制系统体系结构模型  28-33
    2.3.1 体系结构模型  28-31
    2.3.2 基于Agent 或Holon 的制造控制系统体系结构模型的定量评价  31-33
  2.4 协商机制  33-38
    2.4.1 协商机制分类  33-37
    2.4.2 协商协议形式化描述方法  37-38
  2.5 调度算法  38-41
    2.5.1 典型调度算法  38-41
    2.5.2 过滤定向搜索方法在车间调度中的应用  41
  2.6 强化学习及其在生产调度中的应用综述  41-43
    2.6.1 强化学习典型算法简介  42-43
    2.6.2 强化学习的生产调度应用综述  43
  2.7 基于Agent或Holon的自治与协商调度发展趋势  43-44
  2.8 基于自治与协商调度的核心技术现状研究小结  44-46
第三章柔性制造车间混合式控制体系结构模型及其形式化规范  46-67
  3.1 引言  46-47
  3.2 基于Holon的柔性制造车间混合式体系结构模型  47-57
    3.2.1 基于Holon 的混合式体系结构理论  47-49
    3.2.2 构建基于Holon 的柔性制造车间混合式控制体系结构模型  49-55
    3.2.3 Holon 间通信语言规范  55-57
  3.3 体系结构模型的形式化规范的必要性和方法  57-58
    3.3.1 形式化规范的必要性  57-58
    3.3.2 形式化规范描述方法  58
  3.4 基于一阶多元π 演算的控制体系结构模型形式化规范  58-66
  3.5 本章小结  66-67
第四章集成合同网和Q-学习的柔性制造单元任务动态协调分配机制  67-83
  4.1 引言  67
  4.2 强化学习与Q-学习算法  67-72
    4.2.1 马尔可夫决策过程（MDP, Markov Decision Process）  68-69
    4.2.2 强化学习原理和基本要素  69-70
    4.2.3 Q-学习算法  70-72
  4.3 集成合同网和Q-学习的单元任务动态协调分配机制（CNP-QL）  72-80
    4.3.1 CNP-QL 协商机制模型  73-74
    4.3.2 基于FIPA ACL 的CNP-QL 机制的消息表述  74-75
    4.3.3 CNP-QL 机制的策略决策过程和学习过程  75-76
    4.3.4 CNP-QL 机制中Q-学习算法各因素的具体定义  76-80
  4.4 基于CNP-QL 机制的作业动态分配仿真实验和分析  80-82
  4.5 本章小结  82-83
第五章基于过滤定向搜索算法的单元自治调度方法  83-119
  5.1 引言  83-84
  5.2 基于过滤定向搜索的单元自治调度决策模型  84-85
  5.3 问题域—多目标柔性Job-shop调度问题模型  85-96
    5.3.1 柔性Job-shop 调度问题描述  85-86
    5.3.2 作业调度多目标因素  86-87
    5.3.3 多目标调度优化问题及解决方法  87-89
    5.3.4 选定三种目标的原因及目标间相互冲突性论证  89-91
    5.3.5 基于选定三目标的柔性Job-shop 调度问题建模及模型分析  91-96
  5.4 核心算法—基于过滤定向搜索的启发式算法（HFBS）  96-103
    5.4.1 过滤定向搜索算法  96-97
    5.4.2 搜索策略定义  97-99
    5.4.3 算法描述  99-101
    5.4.4 算法说明实例描述  101-103
  5.5 算法性能评价  103-117
    5.5.1 局部评价函数和全局评价函数性能分析  103-106
    5.5.2 典型FJSP Benchmark 实例的仿真及比较分析  106-110
    5.5.3 与调度规则的仿真比较分析  110-117
  5.6 本章小结  117-119
第六章基于过滤定向搜索算法的单元自治动态重调度优化  119-141
  6.1 引言  119-120
  6.2 动态重调度理论框架体系  120-125
    6.2.1 重调度环境和动态事件  121-122
    6.2.2 重调度策略  122-124
    6.2.3 重调度方法  124-125
  6.3 基于过滤定向搜索的单元动态重调度策略  125-131
    6.3.1 动态重调度问题描述  125-126
    6.3.2 动态重调度决策过程  126-128
    6.3.3 过滤定向搜索算法的改进  128-130
    6.3.4 算法的时间复杂性分析  130-131
  6.4 动态重调度算例仿真  131-140
    6.4.1 算法评价  131-136
    6.4.2 动态重调度算例仿真  136-140
  6.5 本章小结  140-141
第七章原型仿真系统设计与开发  141-156
  7.1 引言  141
  7.2 JADE 平台  141-144
  7.3 原型系统设计方法与运行环境  144-146
    7.3.1 面向智能实体设计方法  144-145
    7.3.2 硬件环境  145
    7.3.3 软件体系架构  145-146
  7.4 原型系统设计与仿真界面  146-155
    7.4.1 辅助功能描述  146-148
    7.4.2 系统包图和类图  148-149
    7.4.3 原型系统功能界面  149-155
  7.5 本章小结  155-156
第八章结论与展望  156-160
  8.1 引言  156
  8.2 本论文的主要工作及成果  156-158
  8.3 展望  158-160
参考文献  160-169
附录A CNP-QL 算法和仿真源代码  169-180
附录B 基于过滤定向搜索算法的核心源代码及部分操作界面  180-192
致谢  192-193
作者攻读博士学位期间所做的工作和所发表录用的学术论文  193-195

基于自治与协商机制的柔性制造车间智能调度技术研究

内容摘要

全文目录

相似论文