求解矩形和圆形装填问题的最大穴度算法

在超大规模集成电路设计，裁缝裁剪布料，玻璃切割等工作中提出了矩形和圆形装填问题，即把不同大小的矩形块和圆饼装入一个矩形容器中，以最大化容器的面积利用率为优化目标。对这一问题，可采用模拟退火，遗传算法等国际流行算法进行求解，但这些方法计算时间较长，计算结果的优度也不甚理想。利用人类的智慧和经验，提出了一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试。所得结果的平均面积利用率为90．80％，平均计算时阊为8．38s。测试结果表明，算法对求解矩形和圆形装填问题是行之有效的。     

求解矩形packing问题的贪心算法

在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题，国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验，提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试，所得结果的平均面积未利用率为0.28%，平均计算时间为17.86s，并且还得到了其中8个实例的最优解。测试结果表明，该算法对求解矩形packing问题相当有效。     

一种求解矩形块布局问题的拟物拟人算法

在VLSI工作中提出了矩形块布局问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法等求解算法。本文以人类上万年以来形成的经验为基础,利用“占角”和“聚类”两个拟物拟人的思想策略,提出了基于最大穴度优先的拟物拟人布局算法。甩本文提出的算法,对MCNC、GSRC两个典型测试算例的所有实例进行了实算测试,测试结果表明：计算所得布局结果的优度高,计算时间短。对MCNC和GSRC测试算例,除apte实例外,其它所有实例均得到了最优解,而计算时间都在10秒以内。与CBL算法、遗传算法和号称当今最好的CompaSS算法相比,本文算法所得结果的优度更高,计算时间更短。进一步的测试表明,本文提出的拟物拟人布局算法为当今的一种高效算法。     

一种求解多维0-1背包问题的拟人算法

在项目决策与规划,资源分配,货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法,蚁群算法及其它一些启发式算法等求解算法。该文提出了一种新的启发式求解算法。该算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品并对其进行标记的策略和拟人跳坑策略。用本文提出的算法,对55个测试算例进行了实算测试,得到了其中54个算例的最优解。测试结果表明,用该文提出的拟人算法求解多维0-1背包问题,计算结果的优度高,计算时间短,是求解此问题的有效算法。     

带静不平衡约束的矩形装填问题的启发式算法

卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau（WL）抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。     

基于穴度的三维时空优化问题的贪心调度算法

研究了基于二维矩形Packing的三维时空优化问题,即对给定的一个任意宽、高的大矩形框和有限个有连续加工时间要求的任意宽、高的小矩形块,如何安排每个小矩形块的入框时刻及其出框前每一时刻的位置和方向,使得所有小矩形块的总加工时间即总调度长度makespan最短。与经典布局问题的不同之处在于,各矩形块在框内可随时间的绵延而改变其位置和方向,从而能更充分地利用矩形框的空间。基于实角与实占角动作的定义,设计了求解其子问题二维矩形Packing问题的增强穴度算法。然后,每步迭代优先考虑剩余加工时间长的矩形块,提出了求解此问题的贪心穴度调度算法(caving-degree based greedy scheduling algorithm,CGSA)。作为比较,同时设计了矩形块在框内不可随时间移动的将时间简单类比为空间的对应Packing问题的调度算法CGSA′。对于实验中提出的满足非闸断模式的4个小型算例,它们在原问题上的最优调度长度为2,但若将时间简单地类比为空间,即矩形块放入框内后不可随时间移动其方位,则其最优调度长度为3。实验表明,算法CGSA在这4个非闸断算例上均得到了最优调度。进一步地研究出满足闸断模式的21组共210个自动生成算例,通过实验验证了算法CGSA的最优解的数目明显多于CGSA′,且CGSA的平均调度长度明显短于CGSA′。     

一种解决矩形布局问题的启发式快速算法

针对二维矩形Packing问题,提出了一种沿阶梯线轮廓进行布局矩形的启发式算法.该算法基于"阶梯式堆码"的启发式规则,能够快速地对矩形块进行紧靠布局.为避免算法陷入局部最优,算法采用随机回溯策略在选择矩形和阶位上扩大搜索范围.结果表明,算法对于浪费面积为零的矩形全Packing问题,能够在极短的时间内找到最优解,同时它也可以很好地求解非零浪费问题.采用国际公认的两个算例进行测试,证明文中算法是非常高效的.     

基于五块模式的单一矩形件排样算法

如何在一个大矩形里排入尽可能多的单一规格小矩形件是广泛出现在制造业领域 的板材分割、物流业领域的集装箱装载中的问题。采用五块模式将大矩形划分为五个块,求解 每个块里面矩形件的排样方式。首先,采用动态规划算法一次性生成所有块中矩形件排样方式, 然后,采用隐式枚举法考虑所有可能的五块组合,选择包含矩形件个数最多的五块组合作为最 终的排样方案。使用算例对算法进行了测试,并与另外4 种单一排样算法进行了比较。实验结 果表明,该算法在排样利用率和切割工艺两方面都有效,而且计算时间合理。     

一种求解集装箱装载问题的启发式算法

所谓集装箱装载问题,就是将若干大小不同的长方体盒子装进一个大小已知的长方体容器,其目标是最大化容器的积裁率.对这一问题,国内外学者利用不同的哲学思想,提出了诸如遗传算法、模拟退火算法等求解算法.本文提出一种求解此问题的基于最大穴度优先原则的启发式算法.算法中使用了两个重要的策略:最大穴度原则和最小边度原则.用一些公开的算例对算法性能进行了实算测试,测试结果表明:算法所得结果的容器积载率高,是求解集装箱装载问题的有效算法.     

一种求解圆形Packing问题的模拟退火算法?

为求解矩形区域内的圆形Packing问题,提出一种启发式模拟退火算法。寻求多个圆在一个矩形区域内的优良布局,使这些圆两两互不嵌入地放置。算法从任一初始构形出发,采用模拟退火(SA)算法进行全局寻优,在SA执行过程中,应用基于自适应步长的梯度法进行局部搜索,同时介绍一些启发式策略。对2组共20个算例进行实算测试,计算结果证明了该算法的有效性。     

A new heuristic algorithm for rectangle packing

The rectangle packing problem often appears in encasement and cutting as well as very large-scale integration design. To solve this problem, many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms have been proposed. In this paper, a new heuristic algorithm is recommended based on two important concepts, namely, the corner-occupying action and caving degree. Twenty-one rectangle-packing instances are tested by the algorithm developed, 16 of which having achieved optimum solutions within reasonable runtime. Experimental results demonstrate that the algorithm developed is fairly efficient for solving the rectangle packing problem.     

An efficient heuristic algorithm for arbitrary shaped rectilinear block packing problem

Arbitrary shaped rectilinear block packing problem is a problem of packing a series of rectilinear blocks into a larger rectangular container, where arbitrary shaped rectilinear block is a polygonal block whose interior angle is either 90° or 270°. This problem involves many industrial applications, such as VLSI design, timber cutting, textile industry and layout of newspaper. Many algorithms based on different strategies have been presented to solve it. In this paper, we proposed an efficient heuristic algorithm which is based on principles of corner-occupying action and caving degree describing the quality of packing action. The proposed algorithm is tested on six instances from literatures and the results are rather satisfying. The computational results demonstrate that the proposed algorithm is rather efficient for solving the arbitrary shaped rectilinear block packing problem.     

An efficient heuristic algorithm for rectangle-packing problem

Rectangle-packing problem involves many industrial applications, such as shipping, timber cutting, very large scale integration (VLSI) floor planning, and so on. This problem has shown to be NP hard, and many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms are presented to solve it. Based on the wisdom and experience of human being, an efficient heuristic algorithm is proposed in this paper. Two group benchmarks are used to test the performance of the produced algorithm, 19 instances of first group and 3 instances of second group having achieved optimal solutions. The experimental results demonstrate that the presented algorithm is rather efficient for solving the rectangle-packing problem.     

Approximate algorithms for the container loading problem

In this paper we develop several algorithms for solving three–dimensional cutting/packing problems. We begin by proposing an adaptation of the approach proposed in Hifi and Ouafi (1997) for solving two–staged unconstrained two–dimensional cutting problems. We show how the algorithm can be polynomially solved for producing a constant approximation ratio. We then extend this algorithm for developing better approximate algorithms. By using hill–climbing strategies, we construct some heuristics which produce a good trade–off between the computational time and the solution quality. The performance of the proposed algorithms is evaluated on different problem instances of the literature, with different sizes and densities (a total of 144 problem instances).     

正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.     

Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape

In this paper, the two-dimensional cutting/packing problem with items that correspond to simple polygons that may contain holes are studied in which we propose algorithms based on no-fit polygon computation. We present a GRASP based heuristic for the 0/1 version of the knapsack problem, and another heuristic for the unconstrained version of the knapsack problem. This last heuristic is divided in two steps: first it packs items in rectangles and then use the rectangles as items to be packed into the bin. We also solve the cutting stock problem with items of irregular shape, by combining this last heuristic with a column generation algorithm. The algorithms proposed found optimal solutions for several of the tested instances within a reasonable runtime. For some instances, the algorithms obtained solutions with occupancy rates above 90% with relatively fast execution time.     

矩形件优化排样的混合启发式方法

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。