1 / 48
文档名称:

模型建立与求解问题一贪心算法.ppt

格式:ppt   大小:3,568KB   页数:48页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

模型建立与求解问题一贪心算法.ppt

上传人:sunhongz9 2018/2/8 文件大小:3.48 MB

下载得到文件列表

模型建立与求解问题一贪心算法.ppt

文档介绍

文档介绍:打孔机生产效能的提高
队员:李伦王旭查姗
指导教师:屠良平
学校:辽宁科技大学
1 问题提出
2 问题分析
3 模型假设
4 模型的建立与求解
5 模型评价及改进
目录
问题关键
印刷线路板过孔加工费用占制版费用30%到40%,打孔机主要用于线路板打孔作业,提高打孔机生产效能可以降低制版费用,时间。
钻头上安有八种刀具,有些过孔需要多个工序且有次序要求。
分别给出单钻头和双钻头最优加工作业线路,时间,成本,
研究双钻头合作间距对加工路线和效率影响
问题重述
某些孔需多把刀具加工;
某些孔加工时刀具有次序限制;
钻头上有八把刀具,可顺逆旋转;
共十种孔型,但孔数量大;
不仅要研究单钻头打孔,还要研究双钻头打孔;
综上分析可知:这道题与TSP问题类似,但不同之处是某些孔
需多把刀具加工且加工有次序限制。因此我们要想办法把本
题转化为TSP问题求解。
问题分析
问题特点
本文框架
双钻头
单钻头
最优路径
最优路径、
换刀方案
换刀方案
单钻头最优路径
开始
双刀最优路径、
换刀方案
双刀换刀方案
双钻头最优路径
方案二
方案三
遗传算法结合
贪心算法
分块
方案二
方案二
贪心算法
贪心算法
最优路径
遗传算法结合
贪心算法
聚类
分块
分析合作间距影响
结束
对比分析生产效能
对比
对比
成本
矩阵
方案一
蚁群
算法
流程图:
成本
矩阵
蚁群
算法
方案一
不考虑单个过孔钻孔作业成本。
不考虑单个过孔钻孔作业时间。
钻头无损耗,不损坏。
钻头移动速度恒定。
钻头视为质点。
模型假设
孔型
A
B
C
D
E
F
G
H
I
J
所需刀具
a
b
a, c
d, e*
c, f
g, h*
d, g, f
h
e, c
f, c
已知线路板上各类孔型如表所示:
我们对题目中所给的原始数据进行处理,对需要多种刀具的孔型进行拆分,把需多孔型的一点拆分成只需一刀具的多个孔,拆分成的多个孔的坐标相同,但所需刀具不一样,这样一旦确定了一种加工次序,就把换刀方案确定了。
模型建立与求解
过孔转换
上述10种孔型可转化为:
处理后孔的数量由2124个变为2814个单孔,分别对2814个孔坐标
进行编号,即每一个孔都对应一个确切编号,坐标和所需刀具,
这样的话,我们转换成TSP问题进行求解。
模型建立与求解
转换后的孔型
对刀具进行编号,1—8
每个空为三维坐标,前两维是位置,第三维是刀具编号。
模型建立与求解
孔型三维坐标
总加工花费
从i孔到j孔换刀次数
总加工时间
模型建立与求解
符号约定、公式
刀具编号:1,2,3……8