共查询到19条相似文献,搜索用时 156 毫秒
1.
二维圆形排样问题是工业设计与生产中经常遇到的问题.常规下料问题主要针对矩形或圆形等规则板材,常用算法包括模拟退火、遗传算法等.本文在分析规则板材下料算法的基础上,针对实际生产应用中更为复杂的、具有不规则边界板材下料问题,提出了一种基于人工下料思维的仿生下料算法--邻居关系算法.该算法具有很好的利用率和时效性,较好地满足了实际应用的需要.实际板材下料结果表明,平均面积利用率为75.56%,平均计算时间为13.84s.所得排样利用率与模拟退火算法相当,但排样运算时间大大缩小,适应了实际下料需求,已应用于某跨国企业优化下料中. 相似文献
2.
橱柜及板式家具生产都涉及二维板材下料,材料利用率的最大化一直是该类企业追求的目标。本文提出了基于启发式规则的有限制二维板材下料算法。通过在橱柜生产过程中自动下料系统的实施和理论分析,该算法是实用有效的。 相似文献
3.
4.
研究二维板材切割下料问题,即使用最少板材切割出一定数量的若干种矩形件。
提出一种结合背包算法和线性规划算法的确定性求解算法。首先构造生成均匀条带四块排样方
式的背包算法;然后采用线性规划算法迭代调用上述背包算法,每次均根据生产成本最小原则
改善目标函数并修正各种矩形件的当前价值,按照当前价值生成新的排样方式;最后选择最优
的一组排样方式组成排样方案。采用基准测题,将该算法与著名的T 型下料算法进行比较,实
验结果表明,该算法比T 型下料算法更能节省板材,计算时间能够满足实际应用需要。 相似文献
5.
设计多目标启发式进化算法,研究了一种考虑批量问题的二维矩形件排样问题,建立了含有原材料成本最小化和零件库存成本最小化的多目标优化模型。先用启发式算法初始化下料方式,再用改进的快速非支配排序算法进行优化求解,确定下料方案。通过实验结果以及与其他算法的对比表明,在中等规模的矩形件排样问题中,该算法能够在较快的时间内既保证较高的原料利用率,又能降低该问题的总成本,证明了该算法的有效性。 相似文献
6.
玻璃板材按等级优选技术在全自动玻璃产线的下料工艺中起重要作用,优选的结果优劣直接影响玻璃板材出材率及综合利用率,而优选的结果优劣取决于玻璃板材考虑等级的下料优选算法。针对全自动玻璃板材下料设备优选算法实现的问题,提出适用于自动扫描的玻璃板材及矩形件规范化量化方法,并结合量化方法给出规范化矩形件订单定义,作为任务输入给优选算法;提出适用于下料设备自动下料的矩形件优选下料的三种矩形件优选方式,即加权优选方式、数量优选方式及价值优选方式,并结合等级优选以适应自动化生产线的要求,解决如何优选的问题。然后,建立数量优选系数及矩形件优选的数学模型;设计下料优选算法软件实现的智能化架构及编制相应优选实现软件。选取实例对所建立的数学模型进行综合评价,评价结果表明,运用所提优选算法的出材率提高约10%,能明显提高生产效率,能实现矩形件产品的精确统计。所建立的三种矩形件优选方式的数学模型能有效地提高玻璃板材出材率和综合利用率。 相似文献
7.
王石 《计算机技术与发展》2011,21(3)
针对二维矩形Packing问题,提出了一种沿阶梯线轮廓进行布局矩形的启发式算法.该算法基于"阶梯式堆码"的启发式规则,能够快速地对矩形块进行紧靠布局.为避免算法陷入局部最优,算法采用随机回溯策略在选择矩形和阶位上扩大搜索范围.结果表明,算法对于浪费面积为零的矩形全Packing问题,能够在极短的时间内找到最优解,同时它也可以很好地求解非零浪费问题.采用国际公认的两个算例进行测试,证明文中算法是非常高效的. 相似文献
8.
9.
一种基于四叉树结构的排料算法 总被引:5,自引:0,他引:5
提出了一种利用四叉树结构来描述矩形物体排料过程的算法。为了确保排料布局的合理性,满足工业上的一刀切要求,需采用组合规则和邻接规则来合成矩形块,这样做还可减少废料碎片、降低算法复杂度、提高板材利用率。 相似文献
10.
求解矩形条带装箱问题的动态匹配启发式算法 总被引:2,自引:0,他引:2
矩形条带装箱问(RSPP)是指将一组矩形装入在一个宽度固定高度不限的矩形容器中,以期获得最小装箱高度.RSPP理论上属于NP难问题,在新闻组版、布料下料以及金属切割等工业领域中有着广泛的应用.为解决该问题,采用了一种混合算法,即将一种新的启发式算法--动态匹配算法--与遗传算法结合起来.混合算法中,动态匹配算法能根据4类启发式规则动态选择与装填区域相匹配的下一个待装矩形,同时将装箱后所需容器高度用遗传算法的进化策略进行优化.时2组标准测试问题的计算结果表明,相对于文献中的已有算法,提出的算法更加有效. 相似文献
11.
12.
带预选搜索步深的二维一刀切矩形优化排料 总被引:4,自引:0,他引:4
黄继进 《计算机辅助设计与图形学学报》1994,6(4):313-316
排料问题是一种总体资源分配问题,其目标是将定量的资源划分为若干指定的份额。使剩余量极小。本文提出了一种新的二维一刀切矩形优化排料算法。实验结果表明,该算法效率高,灵活性强,可被广泛应用于许多相关排料领域。 相似文献
13.
This paper considers the constrained two-dimensional cutting stock problem. Some properties of the problem are derived leading to the development of a new algorithm, which uses a very efficient branching strategy for the solution of this problem. This strategy enables the early rejection of partial solutions that cannot lead to optimality. Computational results are given and compared with those produced by a leading alternative method. These results show that the new algorithm is far superior in terms of the computer time needed to solve such problems. 相似文献
14.
This paper addressed an important variant of two-dimensional cutting stock problem. The objective was not only to minimize trim loss, as in traditional cutting stock problems, but rather to minimize the number of machine setups. This additional objective is crucial for the life of the machines and affects both the time and the cost of cutting operations. Since cutting stock problems are well known to be NP-hard, we proposed an approximate method to solve this problem in a reasonable time. This approach differs from the previous works by generating a front with many interesting solutions. By this way, the decision maker or production manager can choose the best one from the set based on other additional constraints. This approach combined a genetic algorithm with a linear programming model to estimate the optimal Pareto front of these two objectives. The effectiveness of this approach was evaluated through a set of instances collected from the literature. The experimental results for different-size problems show that this algorithm provides Pareto fronts very near to the optimal ones. 相似文献
15.
The one-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems which
arises in many industrial applications. Although the primary objective of 1D-CSP is to minimize the total length of used stock
rolls, the efficiency of cutting processes has become more important in recent years. The crucial bottleneck of the cutting
process often occurs at handling operations in semiautomated manufacturers such as those in the paper tube industry. To reduce
interruptions and errors at handling operations in the paper tube industry, we consider a variant of 1D-CSP that minimizes
the total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination
of piece lengths occurring in open stacks simultaneously, and (C3) the number of open stacks. For this problem, we propose
a generalization of the cutting pattern called the “cutting group,” which is a sequence of cutting patterns that satisfies
the given upper bounds of setups of each stock roll type and open stacks. To generate good cutting groups, we decompose the
1D-CSP into a number of auxiliary bin packing problems. We develop a tabu search algorithm based on a shift neighborhood that
solves the auxiliary bin packing problems by the first-fit decreasing heuristic algorithm. Experimental results show that
our algorithm improves the quality of solutions compared to the existing algorithm used in a paper tube factory. 相似文献
16.
In this paper, we develop a new version of the algorithm proposed in Hifi (Computers and Operations Research 24/8 (1997) 727–736) for solving exactly some variants of (un)weighted constrained two-dimensional cutting stock problems. Performance of branch-and-bound procedure depends highly on particular implementation of that algorithm. Programs of this kind are often accelerated drastically by employing sophisticated techniques. In the new version of the algorithm, we start by enhancing the initial lower bound to limit initially the space search. This initial lower bound has already been used in Fayard et al. 1998 (Journal of the Operational Research Society, 49, 1270–1277), as a heuristic for solving the constrained and unconstrained cutting stock problems. Also, we try to improve the upper bound at each internal node of the developed tree, by applying some simple and effcient combinations. Finally, we introduce some new symmetric-strategies used for neglecting some unnecessary duplicate patterns . The performance of our algorithm is evaluated on some problem instances of the literature and other hard-randomly generated problem instances. 相似文献
17.
圆木二维下料问题是木材企业中常见问题,针对一些头部与尾部直径相差不大的木材,可以将这些木材看作是圆柱体,下料时将其切成和圆木长度相等的多个长方体毛坯,该问题可转化为二维下料问题。采用顺序价值校正框架和动态规划算法求解该下料问题。顺序生成排样图,每生成一个排样图便调整毛坯的价值,重复该过程直到满足毛坯需求为止。通过迭代生成多个下料方案以便优选。圆木下料的研究对减少木材企业的成本很有意义。 相似文献
18.
Francis J. Vasko Christopher L. Bartkowski 《International Transactions in Operational Research》2009,16(6):829-838
P. Y. Wang's classic bottom-up two-dimensional cutting stock algorithm generates cutting patterns by building rectangles both horizontally and vertically. This algorithm uses a parameter β 1 to tradeoff the number of rectangles generated by the algorithm and hence the quality of the cutting pattern solution obtained versus the amount of computer resources required. Several researchers have made relatively straightforward modifications to Wang's basic algorithm resulting in improved computational times. However, even with these modifications, Wang's approach tends to require large amounts of computer resources in order to optimally or near-optimally solve difficult two-dimensional guillotine cutting stock problems. In this paper, we present an iterative approach that judiciously uses Wang's basic algorithm (with some previously defined modifications) to obtain optimal cutting patterns to difficult two-dimensional cutting stock problems in reasonable computer run times. 相似文献
19.
Omar Ayadi Malek Masmoudi Mariem Ben Ameur Faouzi Masmoudi 《Applied Artificial Intelligence》2017,31(4):376-393
In this paper, a new algorithm is proposed for the two-dimensional non-guillotine non-oriented cutting stock problem. The considered problem consists of cutting small rectangular pieces of predetermined sizes from large but finite rectangular plates. The objective is to generate cutting patterns that minimize the unused area and fulfill customer orders. The proposed algorithm is a combination of a new particle swarm optimization approach with a heuristic criterion inspired from the literature. The algorithm is tested on twenty-two instances divided into two sets. Corresponding results show the algorithm efficiency in optimizing the trim loss that is comprised between 2.6% and 7.8% for all considered instances. 相似文献