论文研究-自适应半监督模糊谱聚类算法.pdf
需积分: 4 102 浏览量
2019-09-08
10:21:34
上传
评论
收藏 558KB PDF 举报
2010，46（33）
1 引言
矩形件排样问题广泛存在于汽车、机械、家电和家具等制
造行业，解决好该问题可以节省原材料，简化生产工艺，降低
生产成本，增加企业效益。在生产实践中，往往会碰到矩形件
带填充问题（Rectangular Stri p Pac king Problem，RSPP）
[1]
：把
一些给定尺寸和需求的小矩形件摆放在一个定宽无限长的大
矩形带上，在满足需求的同时要求占用长度最小。
RSPP 是 NP 难问题
[1]
，至今人们仍没有找到一种多项式算
法来精确求解。如果用穷举法求解，随着问题规模的增大，计
算量将爆炸性增长。为了避免这种在时间和空间上的巨大开
销，许多学者模拟生物的进化规律引入遗传算法求解这类问
题，以得到近似最优解。
2 矩形件带排样问题的描述及三阶段排样方案
RSPP 问题可定义为：有 n 个不同尺寸的矩形毛坯，其长和
宽分别为 l
i
和 w
i
，需求量为 d
i
，i=1，2，…，n，把它们放置在一个
宽为 W 长度无限的条带上，使得占用的条带总长度最小。如
果按如下方式叙述，则可称为带切割问题（Rectangul ar Strip
Cut ting Problem，RSCP）：将条带切成上述 n 个矩形，使占用的
条带总长度最小。
全部小矩形在条带上的一种排列方式称为排样方案。在
实际应用中，往往会对排样方案提出一些约束条件和目标。
例如，物品在货架上的摆放是 RSPP 的一个典型应用。通常要
求分层摆放，且各层中物品的高度不大于相应层高度，小物品
应当放在大物品上等。又例如，用剪床将条带切成小矩形零
件是 RSCP 的一个典型应用，为简化下料过程，通常需要采用
较为简单的排样方案。采用的 3 阶段（排样）方案可以满足这
两类典型应用的要求。
在 3 个阶段内将排样方案切成毛坯
[1]
。同一阶段的剪切
线相互平行，相邻两个阶段的剪切线相互垂直。例如，对于图 1
所示 3 阶段方案，第一阶段用竖直剪切线将矩形带分成多个
段（图 1（a）中箭头指示），第二阶段用水平剪切线将各段分成
条带（以第一段为例，如图 1（b）所示），第三阶段用竖直剪切线
将条带切成毛坯（图 1（c））。讨论的是特殊类型的 3 阶段排样
矩形件三阶段带排样问题的遗传算法
刘 睿
1
，严 玄
2
，崔耀东
2
LIU Rui
1
，YAN Xuan
2
，CUI Yao- dong
2
1.聊城大学 计算机学院，山东 聊城 252000
2.广西师范大学 计算机科学与信息工程学院，广西 桂林 541004
1.School of Computer Science，Liaocheng University，Liaocheng ，S handong 252000，China
2.C ollege of Computer Science & Information Technology，Guangxi Norm al University，Guilin，Guangxi 541004，China
LIU Rui ，YA N Xuan，CUI Yao-dong.Genet ic algorithm for rectangular three-stage st rip packing problem.Computer Engi-
nee ring and Applicatio ns，2010，46（33）：221-224.
Abstract：A hybrid gen etic algorith m to solve the rectangular strip packing problem is proposed.Consi deri ng some special
con straints and simplifying the cutting pr ocess，the idea of three-stage is adopted to design the improved algorithm.The genet-
ic operation is improved and an adjustment operation is used to optimize the cutting plan after the mutation operation.In ini-
tial population construction some simple methods are used to make the results converge more quickly.The experiment results
indicate the validity of the presented algorithm.
Key words：genetic algorithm；three-stage；rectangular strip pac king prob lem
摘 要：采用混合遗传算法求解矩形件带排样问题，采用三阶段排样方式以满足特定的约束或简化切割工艺。改进遗传算子，在
变异操作之后使用调整操作，以进一步简化得到的排样方案。在初始种群构造时，根据矩形件的特性采用一些简单有效的方法，
使结果更好更快地收敛。实验结果表明方法对解决这类问题是有效的。
关键词：遗传算法；三阶段；矩形件带排样问题
DOI：10.3778/j.issn.1002-8331.2010.33.063 文章编号：1002-8331（2010）33-0221-04 文献标识码：Ａ 中图分类号：TP391.72
基金项目：国家自然科学基金（th e National Natural Science Foundation of China under Grant No.60763011）；广西科学基金项目（No.桂科自
0728100）；贵州省高层次人才科研条件特助基金项目。
作者简介：刘睿（1984-），女，硕士，主要研究方向为优化计算技术与 CAD；严玄（1982-），男，硕士，主要研究方向为优化计算技术与 CAD；崔耀东
（1957-），男，博士，教授，研究生导师，主要研究方向为优化计算技术与 CAD。
收稿日期：2010-03-12 修回日期：2010-05-10
Compu ter Engineerin g a nd Applications 计算机工程与应用
221
资源评论
