Micro-IPLS: Pallet loading on a microcomputer

IPLS is an interactive computerized system developed in 1982 to assist the U.S. Air Force with pallet loading. It uses a dynamic programming based heuristic to solve the two-dimensional problem of loading a rectangular pallet from a set of n rectangular boxes so as to maximize the area covered. Micro-IPLS is a version of IPLS that has been developed recently using Apple Fortran on an Apple II⁺ microcomputer with 64k. This paper discusses the underlying heuristic used by Micro-IPLS and compares its performance to the results obtained by the latest version of IPLS.     

Some experiments with a simple tabu search algorithm for the manufacturer's pallet loading problem

The manufacturer's pallet loading problem consists in arranging, orthogonally and without overlapping, the maximum number of boxes with dimensions (l,w) or (w,l) onto a rectangular pallet with dimensions (L,W). This problem has been successfully handled by block heuristics, which generate loading patterns composed by one or more blocks where the boxes have the same orientation. A common feature of such methods is that the solutions provided are limited to the so-called first order non-guillotine patterns. In this paper we propose an approach based on the incorporation of simple tabu search (without longer-term memory structures) in block heuristics. Starting from an initial loading pattern, the algorithm performs moves that increase the size of selected blocks in the current pattern; as a result, other blocks are decreased, eliminated or created. Computational results indicate that the approach is capable of generating superior order optimal patterns for difficult instances reported in the literature.     

生成最优二划分装盘方案的递归算法

针对物流领域的研究装盘问题,为提高装载效率,在矩形托盘中正交的布置最多数目同尺寸长方体小箱,并且小箱之间不发生重叠。采用二划分装盘方案。所谓"二划分",是指一条划分线总是贯穿被划分的区域,将区域划分为二个较小的矩形子区域。二划分方案可以通过使用水平或竖直的划分线,将装裁区域递归地二划分为若干个子区域,每一子区域有且仅有一个小箱。采用递归算法,通过适当设置成本参数,生成排数最少的最优二划分装盘方案。实验计算结果表明所述算法可以有效地简化装箱方案。     

Row and column generation technique for a multistage cutting stock problem

The multistage cutting stock problem (CSP) generalizes the one-dimensional CSP when a lengthwise cutting process is distributed over two or more successive stages. At every stage of the cutting process incoming rolls are slit into smaller rolls by width. The problem is to minimize total trim loss occurring at all stages of technological process meeting customer demands for finished rolls. We propose a row and column generation technique for solving the multistage one-dimensional CSP. The technique is a generalization of the column generation method suggested by Gilmore and Gomory for solving a classic CSP. The procedure generates only those intermediate rolls (rows) and cutting patterns (columns) that are needed. An auxiliary problem embedded into the frame of the revised simplex algorithm is a non-linear knapsack problem that can be solved efficiently. Computational results prove the overall method is a valuable addition to the tool set for modeling and solving the multistage CSP.Scope and purposeWe investigate a broad class of large-scale linear programming models and suggest a new and efficient way to solve them. The proposed method belongs to a category of decomposition techniques generalizing the famous column generation method. An iteration of the revised simplex algorithm may “enrich” the LP matrix either by generating a new column, as a purely column generation method does, or by generating a combination of a new row and a pair of new columns. The method is a row and column generation technique that we propose and investigate. Applications modeled by a multistage CSP occur in the industries that use a multistage cutting process: paper, leather, film, steel, etc., or a nested packing/loading process: transportation. The unknown variables in the multistage cutting stock problem are intermediate sizes (rows) and cutting patterns (columns). According to the algorithm both are to be generated dynamically. The proposed algorithm brings tremendous benefits in terms of the quality of solutions and computational performance.     

矩形件简单块占角排样方式的动态规划

目的 针对矩形件无约束2维剪切排样问题,提出一种可简化板材切割工艺的简单块占角排样方式,并构造这种排样方式的动态规划生成算法。方法 该排样方式在板材左下角按照简单块方式排样若干行若干列同种矩形件,将板材剩余部分划分为两个子板;将子板按照上述方法继续递归排样和划分,直至子板排满矩形件为止。采用动态规划确定所有可能尺寸的板材左下角排样的最优矩形件、矩形件的最优行列数和板材剩余部分的最优子板划分。运用规范尺寸排除不必要的计算。结果 将本文算法与目前常见的算法进行比较,实验结果表明本文算法计算时间合理,排样价值较高。在第1组41道基准例题中,本文算法所有例题均求出了精确解,同质块T型算法、同质块两段算法和复合条带两段算法分别有7道、5道和4道例题未求出精确解。在第2组20道基准例题中,本文算法只有1道例题未求出精确解,普通三阶段算法、同质块T型算法、同质块两段算法和匀质条带三块算法分别有18道、15道、15道和20道例题未求出精确解。在第3组50道随机例题中,本文算法、普通两段算法和同质块两段算法板材利用率分别为99.913 7%、99.862 3%和99.796 1%。在第4组31道基准例题中,本文算法所有例题均求出了精确解,普通占角排样算法有2道例题未求出精确解。结论 本文算法计算时间远小于精确算法,优化效果接近精确算法;本文算法计算时间与多种启发式算法接近,但优化效果好于多种启发式算法。     

冲裁件条料最优四块剪切下料方案的生成算法

讨论冲裁件条料剪切下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成条料最优四块排样方式的背包算法,然后采用基于列生成的线性规划算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并确定各种冲裁件的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用例题将该排样方式生成算法和文献中多段排样方式生成算法进行比较,实验计算结果表明,该算法得到的排样方式排样价值较高。最后通过文献中实例的下料方案求解,可以看出该算法解决实际下料问题是有效的。     

一种有效的求解一维下料问题的启发式算法

使用了一种改进的顺序启发式算法,在排样方式的生成过程中不断修正当前排入毛坯的价值,使之趋于合理,依次选取求解背包函数获得的最大单位价值的排样方式组成当前排样方案,迭代调用该过程多次,最终选取最优的排样方案。在保证较高材料利用率的同时考虑减少排样方式,增加最后一根材料余料长度等多个优化目标。通过多组实验结果比较,证实了算法的有效性。     

A heuristic partitioning algorithm for a packaging problem

A heuristic algorithm for solving a problem of a minimum-cost packaging ofN items of the magnitudea _j intoM boxes of the capacityb _i with a costc _ij being assigned to the itemj packing into the boxi is presented. The principal idea of the algorithm consists in the preliminary partitioning of the problem into smaller subproblems and getting an approximate solution by solving these subproblems. A motivation of the heuristic and an application of the algorithm are given.     

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

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

一种平板车装载问题的启发式算法

提出平板车装载问题的一各上启发式方法,不仅能够从几种型号的平板车中选择出一种装载性能较好的平板车,而且能够将具有不同特性的不同尺寸的物品放在该型号平板车中,它能够在满足一些约束条件下求得一种可行的装载方案,实例充分证明了该算法的有效性和实用性,能够直接用于实际生活中。     

Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts

This paper deals with the two-dimensional bin packing problem with conflicts (BPC-2D). Given a finite set of rectangular items, an unlimited number of rectangular bins and a conflict graph, the goal is to find a conflict-free packing of the items minimizing the number of bins used. In this paper, we propose a new framework based on a tree-decomposition for solving this problem. It proceeds by decomposing a BPC-2D instance into subproblems to be solved independently. Applying this decomposition method is not straightforward, since merging partial solutions is hard. Several heuristic strategies are proposed to make an effective use of the decomposition. Computational experiments show the practical effectiveness of our approach.     

Heuristic for the two-dimensional arbitrary stock-size cutting stock problem

A heuristic is presented for the two-dimensional arbitrary stock-size cutting stock problem, where a set of rectangular items with specified demand are cut from plates of arbitrary sizes that confirm to the supplier’s provisions, such that the plate cost is minimized. The supplier’s provisions include: the lengths and widths of the plates must be in the specified ranges; the total area of the plates with the same size must reach the area threshold. The proposed algorithm uses a pattern-generation procedure with all-capacity property to obtain the patterns, and combines it with a sequential heuristic procedure to obtain the cutting plan, from which the purchasing decision can be made. Practical and random instances are used to compare the algorithm with a published approach. The results indicate that the trim loss can be reduced by more than half if the algorithm is used in the purchasing decision of the plates.     

Computer aided design of unit loads

The unit load design problem includes the selection of the best pallet or container size, the best pallet or container layout, and the best number of parta per pallet or container. Three different approaches to solve the unit load design problem are identified in this paper and a new procedure is proposed: Computer Aided Design of Unit Loads (CADUL I). Using CADUL I, unit loads are designed considering system constraints (i.e., rack opening dimensions, aisle width, trailer-truck container dimensions, product crushability constraints, material handling equipment stacking capability and weight capacity) and a cost function that includes handling, storage, transportation, and pallet or container costs. An example is used to illustrate how CADUL I works and how these approaches to unit load design perform sensitivity analysis to validate the results obtained.     

Exact algorithms for the two-dimensional guillotine knapsack

The two-dimensional knapsack problem requires to pack a maximum profit subset of “small” rectangular items into a unique “large” rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem.In this paper we present a recursive exact procedure that, given a set of items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are computationally evaluated on well-known benchmark instances from the literature.The C++ source code of the recursive procedure is available upon request from the authors.     

The effects of operator position,pallet orientation,and palletizing condition on low back loads in manual bag palletizing operations

Many mining commodities are packaged and shipped using bags. Small bags are typically loaded onto pallets for transport and require a significant amount of manual handling by workers. This specific task of manual bag handling has been associated with the development of musculoskeletal disorders (MSDs), especially low back disorders. This study evaluates the biomechanical demands of different work layouts when performing manual palletizing of small bags, and evaluates the biomechanical stresses associated with different stacking techniques. Results indicate that peak forward bending moments as well as spinal compression and shear forces are higher when the pallet is situated at the side of the conveyor as opposed to the end of the conveyor. At low levels of the pallet, controlled bag placement results in higher peak forward bending moments than stacking at higher levels and when dropping the bag to lower levels. The results of this study will be used to inform the development of an audit tool for bagging operations in the mining industry.Relevance to industryIn many cases for workers loading small bags, compression forces exceed the NIOSH criterion of 3400 N. Orientation of the pallet has a significant impact on spinal compression, and positioning the pallet at the end of the conveyor reduces the estimated compressive loading on the lumbar spine by approximately 800 N.     

Two-dimensional on-line bin packing problem with rotatable items

In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is “rotatable” by $\text{90°}$. Two on-line algorithms for solving the problem are proposed. The second algorithm is an extension of the first algorithm, and the worst-case ratio of the second one is at least 2.25 and at most 2.565.     

An efficient placement heuristic for three-dimensional rectangular packing

By embodying the spirit of “gold corner, silver side and strawy void” directly on the candidate packing place such that the searching space is reduced considerably, and by utilizing the characteristic of weakly heterogeneous problems that many items are in the same size, a fit degree algorithm (FDA) is proposed for solving a classical 3D rectangular packing problem, container loading problem. Experiments show that FDA works well on the complete set of 1500 instances proposed by Bischoff, Ratcliff and Davies. Especially for the 800 difficult strongly heterogeneous instances among them, FDA outperforms other algorithms with an average volume utilization of 91.91%, which to our knowledge is 0.45% higher than current best result just reported in 2010.     

Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing

We present algorithms for the following three-dimensional (3D) guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. We consider the case where the items have fixed orientation and the case where orthogonal rotations around all axes are allowed. For the unbounded 3D knapsack problem, we extend the recurrence formula proposed by [1] for the rectangular knapsack problem and present a dynamic programming algorithm that uses reduced raster points. We also consider a variant of the unbounded knapsack problem in which the cuts must be staged. For the 3D cutting stock problem and its variants in which the bins have different sizes (and the cuts must be staged), we present column generation-based algorithms. Modified versions of the algorithms for the 3D cutting stock problems with stages are then used to build algorithms for the 3D strip packing problem and its variants. The computational tests performed with the algorithms described in this paper indicate that they are useful to solve instances of moderate size.     

铁路输送中平车装载问题的模型与算法

分析了铁路运输中的平车装载问题，借鉴了First Fit算法的思想，并引入条件变异算子，提出了求解平车装载问题的一种改进遗传算法，给出了该改进遗传算法编码方法、遗传算子改进方案和适应度函数的定义，该算法能有效地解决初始群体和进化过程中的无效染色体和早熟问题，并用实例验证了该算法的有效性。     

An evolutionary algorithm for the one‐dimensional cutting stock problem

This paper deals with the one‐dimensional integer cutting stock problem, which consists of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to minimize the waste of material. The case in which there are various types of objects available in stock in limited quantities is studied. A new heuristic method based on the evolutionary algorithm concept is proposed to solve the problem. This heuristic is empirically analyzed by solving randomly generated instances and the results are compared with other methods from the literature.