可重构物流系统设计与调度方法的研究

摘要

可重构制造系统(RMS)是一类构形可变的新型制造系统,能够根据生产需求,快速改变系统构形,以经济的方式准确地提供所需的功能和产能。可重构物流系统(RMHS)是RMS的重要组成部分,必须具有快速改变构形的能力,以适应RMS的要求。基于多自动导引车系统(AGVS)的RMHS运作中的关键问题是:为系统选择怎样的布局和路径网络,以及如何调度搬运任务,以使得物流成本最小化,即设计与调度问题。RMHS的设计与调度问题是复杂的组合优化问题,而且在RMS环境下,需要考虑系统构形频繁变化、工作站重构等复杂多变的问题,对于这个问题尚缺乏系统化的、行之有效的求解理论与方法。
　　 针对这一情况,在国家重点基础研究计划项目“复杂生产制造过程实时、智能控制与优化理论和方法研究”的资助下,围绕课题“生产制造系统重构过程的实时协调控制理论与方法研究”,本文展开基于AGVS的RMHS设计与调度方法的研究,提出了有效的设计方法和调度方法,本文主要研究内容如下:
　　 1.提出同时考虑布局和路径网络的更加符合实际情况的RMHS设计模型。根据基于AGVS的RMHS的特点,综合考虑布局和路径网络对物流成本的影响,考虑系统工作站布局重构的成本,提出集成考虑布局和路径网络的RMHS设计模型。该模型的目标是最小化系统总物流成本,包括AGV的负载路程和空载路程产生的成本,以及工作站重构的成本；主要决策变量是工作站布局变量和路径方向变量；需要满足路径长度、路径方向、流量等约束条件。
　　 2.提出改进类电磁机制算法的RMHS设计方法。类电磁机制算法是一种较新的启发式方法,具有较好的求解速度和求解质量。但是初始的类电磁机制算法针对连续系统问题,为了应用在离散系统中,需要进行离散化改进。变邻域搜索策略是较好的局部搜索策略,能系统地搜索各个邻域。针对RMHS的路径网络设计问题、布局设计问题以及集成设计问题,分别设计相应的改进类电磁机制算法。
　　 1)提出改进类电磁机制算法的路径网络设计方法。针对RMHS的路径网络设计问题,进行类电磁机制算法的设计。对路径网络进行预处理,以降低计算量,提高解的可行性。在改进的类电磁机制算法中,粒子采用离散的二进制编码,其编码长度等于预处理后边的数量。在局部搜索中,采用变邻域搜索策略,为了降低计算量,只对当前最优粒子进行局部搜索。根据粒子的总物流路程来计算带电量。在移动过程中,粒子根据合力的排序概率移动。对局部搜索和移动过程中产生的不可行解,进行有限修正,以提高可行解的比例。为了验证所提出算法的效果,提出基于遗传算法的路径网络设计方法作为对比方法,采用分支定界方法作为优化方法。通过多个计算实例,与其他方法比较来验证所提出方法的有效性。
　　 2)提出改进类电磁机制算法的布局设计与重构方法。针对RMHS的布局设计与重构问题,进行类电磁机制算法的设计。粒子采用按照排列顺序编码的方法,在局部搜索过程中,采用变邻域搜索策略,对所有粒子进行局部搜索。在移动过程中,根据合力的排序来确定粒子的移动。作为比较,提出基于遗传算法的布局设计与重构方法。在问题规模较小的时候,采用穷举法得到最优解。通过多个计算实例,与其他方法比较验证所提出方法的有效性。
　　 3)提出改进类电磁机制算法的集成布局和路径网络设计方法。布局与路径网络是密切相关的两个方面,可以通过集成设计来扩大可行解的空间,获得比单独设计更优的解,从而可能明显降低总的物流成本。针对RMHS的集成设计问题,进行类电磁机制算法的设计。粒子采用二段编码的方法,对布局和路径网络分别编码。在局部搜索过程中,采用变邻域搜索策略,对布局和路径网络分层次搜索。在合力计算过程中,分别计算布局和路径网络的合力。在移动过程中,根据布局和路径网络的合力,分别移动。为了验证所提出方法的效果,采用分步设计方法作为对比方法,采用分支定界方法作为优化方法。设计多个计算实例,通过与其他方法的比较,验证集成设计方法的有效性。
　　 3.提出避免死锁的多属性任务调度方法。任务调度是物流系统管理控制方面的重要问题。针对RMHS快速多变,需要较高成本经济效益的特点,提出避免死锁的多属性任务调度方法。为了综合系统多方面的影响,采用多属性的调度方法。选择距离、输入输出缓冲区状态作为调度的属性。根据系统的加工和搬运资源,确定各个属性的权值。为了确保系统无死锁,在多属性任务调度过程中,加入基于剩余容量的死锁避免策略。该方法能够综合考虑系统多方面因素的影响,确保系统无死锁运行。通过多个仿真实例,说明了死锁避免策略能确保系统无死锁,多属性调度方法优于几种常用的调度方法。
　　 4.结合多agent和离散事件仿真技术,设计并实现了RMHS的任务调度仿真系统。针对RMHS任务调度的特点,采用多agent技术和离散事件仿真技术,对搬运任务的分配过程以及系统运行过程进行仿真。该仿真系统可以适应不同的任务调度方法,在仿真过程中记录系统的运行状态。通过设计与调度的综合仿真实例设计,验证了本文提出的设计方法和任务调度方法的有效性。

目录

文摘

英文文摘

第一章 绪论

1.1 背景与意义

1.2 可重构物流系统设计与调度问题介绍

1.2.1 可重构制造系统与可重构物流系统

1.2.2 可重构物流系统的设计与调度问题

1.3 可重构物流系统设计与调度方法综述

1.3.1 可重构物流系统设计问题的研究现状及分析

1.3.2 可重构物流系统任务调度问题的研究现状及分析

1.4 主要问题与解决思路

1.5 主要工作与章节安排

第二章 可重构物流系统布局和路径网络设计问题的建模

2.1 问题描述

2.2 路径网络设计问题建模

2.3 布局设计问题建模

2.4 集成布局与路径网络设计问题建模

2.5 小结

第三章 基于改进类电磁机制算法的路径网络设计方法研究

3.1 问题描述

3.2 类电磁机制算法简介

3.3 基于改进类电磁机制算法的路径网络设计方法

3.3.1 粒子编码

3.3.2 改进类电磁机制算法的基本框架

3.3.3 基于改进类电磁机制算法的路径网络设计过程

3.4 其他方法研究

3.4.1 遗传算法

3.4.2 分支定界方法

3.5 实例比较研究

3.6 小结

第四章 基于改进类电磁机制算法的布局设计与重构方法研究

4.1 问题描述

4.2 基于改进类电磁机制算法的布局设计与重构方法

4.2.1 粒子编码与函数值计算

4.2.2 布局设计的算法框架

4.2.3 改进类电磁机制算法的布局设计与重构过程

4.3 其他方法研究

4.3.1 遗传算法

4.3.2 穷举法

4.4 实例比较研究

4.5 小结

第五章 基于改进类电磁机制算法的集成布局和路径网络设计方法研究

5.1 问题描述

5.2 基于改进类电磁机制算法的集成设计方法

5.2.1 粒子编码与函数值计算

5.2.2 改进类电磁机制算法的一般框架

5.2.3 基于改进类电磁机制算法的集成设计过程

5.3 其他方法

5.3.1 分步设计的方法

5.3.2 分支定界方法

5.4 实例比较研究

5.5 小结

第六章 可重构物流系统避免死锁的多属性任务调度方法研究

6.1 任务调度问题描述

6.2 任务调度问题建模

6.3 避免死锁的多属性任务调度方法

6.3.1 多属性效用值的计算

6.3.2 避免死锁的任务调度过程

6.4 实例比较研究

6.5 小结

第七章 任务调度仿真系统设计及综合仿真研究

7.1 任务调度仿真系统设计与实现

7.1.1 系统结构及功能分析

7.1.2 基于多agent的仿真建模

7.1.3 系统仿真基本流程

7.2 设计与调度方法的综合仿真实例

7.3 小结

第八章 结论与展望

8.1 本文主要工作和贡献

8.2 后续工作展望

参考文献

致谢

作者简介