Generating pallet loading patterns with considerations of item stacking on end and side surfaces

In late 1979 a two phase heuristic algorithm employing dynamic programming was presented by Steudel for solving the two-dimensional cutting stock problem where all the small rectangles were of the same dimensions, but withour any restrictions that the cutting be performed in a purely “guillotine” fashion. The algorithm was applied to solving the common problem of loading rectangular items of size l by w on a rectangular pallet of size L and W so as to maximize the number of items per layer on the pallet deckboard. In this paper, a new three-phase heuristic is presented which extends the 1979 recursive procedure and evaluates the option of stacking items on their end and/or side surface within the best loading pattern of bottom-stacked items. The resulting pattern is then projected into the third dimension to generate the total “cubic” pallet load. Computation results show that end and/or side stacking (when applicable) can yield average improvements in the range of 5% in items per pallet load.     

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.     

关于约束底盘装载问题的一种启发式方法

已研究多年的底盘装载问题属于ＮＰ完备问题，关于它的解决方法多为启发式方法．本文讨论了约束底盘装载问题，并提出了一种基于计算机的启发式方法．实例表明，该方法能较好地解决约束底盘装载问题．     

基于改进CenterNet的托盘定位方法

目前, 托盘定位大多采用基于深度神经网络的目标检测算法, 一般使用矩形框进行托盘定位, 托盘中心点定位精度不高, 且无法有效估计托盘水平方向. 针对此问题, 本文提出了基于关键点检测的托盘定位方法, 通过检测托盘正面外轮廓的4个角点来定位托盘. 首先, 由于目前没有大规模的托盘数据集, 使用迁移学习的方法, 将CenterNet的人体姿态估计引入托盘定位任务. 然后改进关键点分组方法, 并提出关键点回归自适应补偿, 提高关键点检测精度. 在托盘关键点定位的基础上, 提出基于几何约束的托盘中心点计算和托盘水平方向估计方法. 本文方法与原CenterNet相比, 托盘关键点定位指标${{A}}{{{P}}^{{\text{kp}}}}$从0.352提高到0.728, 托盘中心点定位精度指标${{ALP}}$达到0.946, 并且可以有效估计托盘水平方向, 具有较高的实用价值.     

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

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

Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix

For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A^* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected.     

Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix

For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A^* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected.     

On heuristics for minimum length rectilinear partitions

The problem of partitioning a rectilinear figure into rectangles with minimum length is NP-hard and has bounded heuristics. In this paper we study a related problem,Elimination Problem (EP), in which a rectilinear figure is partitioned into a set of rectilinear figures containing no concave vertices of a fixed direction with minimum length. We show that a heuristic for EP within a factor of 4 from optimal can be computed in timeO(n ²), wheren is the number of vertices of the input figure, and a variant of this heuristic, within a factor of 6 from optimal, can be computed in timeO(n logn). As an application, we give a bounded heuristic for the problem of partitioning a rectilinear figure into histograms of a fixed direction with minimum length. An auxiliary result is that an optimal rectangular partition of a monotonic histogram can be computed in timeO(n ²), using a known speed-up technique in dynamic programming.     

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

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

Bounded size dictionary compression: SC-completeness and NC algorithms

We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(log^kn), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(log^kn) space (that is, SC^k). We also introduce a variation of this heuristic that turns out to be an SC^k-complete problem (the original heuristic belongs to SC^k+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given.     

Manufacturing cell formation using an improved P-median model

The p-median model objective function is modified for the cell formation problem to minimize the variability between parts in a group by considering part similarity to all other parts in the group instead of similarity to an arbitrary median. The heuristic vertex substitution method for solution of the part grouping problem is adapted for this objective function and then modified to provide improved starting points. The theoretical lower bound for the heuristic is developed and shown to be valid for all solutions. Worst case run time is shown to be O(n²) or O(n³) for distance matrix or network inputs respectively. Tests on published problems show that the proposed p-median model method provides as good or better objective function value (OFV) than the OFV of a p-median model in which parts are grouped to an arbitrary median. Likewise the new p-median model is shown, for these published problems, to give as good or better OFV than the algorithms reported by the original authors of the problem. The test problems suggest that other measures of solution quality such as bottlenecks and duplicate machines in addition to OFV become important measures of solution quality for dense problems.     

Two-machine flowshop scheduling with bicriteria problem

This paper attempts to solve a two-machine flowshop bicriteria scheduling problem with release dates for the jobs, in which the objective function is to minimize a weighed sum of total flow time and makespan. To tackle this scheduling problem, an integer programming model with N²+3N variables and 5N constraints where N is the number of jobs, is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, a heuristic scheduling algorithm is presented. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. The average solution quality of the heuristic algorithm is above 99% and is much better than that of the SPT rule as a benchmark. A 15-job case requires only 0.018 s, on average, to obtain an ultimate or even optimal solution. The heuristic scheduling algorithm is a more practical approach to real world applications than the integer programming model.     

A fast algorithm for solving the first biharmonic boundary value problem

This paper presents a fast iterative algorithm for the solution of a finite difference approximation of the biharmonic boundary value problem on a rectangular region. For solving this problem, the matrix decomposition algorithm is efficiently applied to the semi-direct method which essentially treats the biharmonic equation as a coupled system of Poisson equations. Assuming anN×N grid of mesh points, the number of operations required for one iteration and for the solution terminated by 0 (N ^?2) is 0 (N ²) and 0 (N ^5/2 log₂ N), respectively. ForN ² processors, the parallel version of this algorithm would require 14 log₂ N steps per iteration. Both results are better than those known. A numerical experiment in a serial computation is also given.     

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.     

The two-stage assembly scheduling problem to minimize total completion time with setup times

We address the two-stage assembly scheduling problem where there are m machines at the first stage and an assembly machine at the second stage. The objective is to schedule the available n jobs so that total completion time of all n jobs is minimized. Setup times are treated as separate from processing times. This problem is NP-hard, and therefore we present a dominance relation and propose three heuristics. The heuristics are evaluated based on randomly generated data. One of the proposed heuristics is known to be the best heuristic for the case of zero setup times while another heuristic is known to perform well for such problems. A new version of the latter heuristic, which utilizes the dominance relation, is proposed and shown to perform much better than the other two heuristics.     

On heuristics for minimum length rectilinear partitions

The problem of partitioning a rectilinear figure into rectangles with minimum length is NP-hard and has bounded heuristics. In this paper we study a related problem,Elimination Problem (EP), in which a rectilinear figure is partitioned into a set of rectilinear figures containing no concave vertices of a fixed direction with minimum length. We show that a heuristic for EP within a factor of 4 from optimal can be computed in timeO(n ²), wheren is the number of vertices of the input figure, and a variant of this heuristic, within a factor of 6 from optimal, can be computed in timeO(n logn). As an application, we give a bounded heuristic for the problem of partitioning a rectilinear figure into histograms of a fixed direction with minimum length.An auxiliary result is that an optimal rectangular partition of a monotonic histogram can be computed in timeO(n ²), using a known speed-up technique in dynamic programming.Part of this work was done when the first author was a postdoctor fellow in MSRI, Berkeley, and supported in part by NSF Grant No. 8120790. The second author was supported in part by NSF Grant No. DCR-8411945.     

Shear flexible element based on coupled displacement field for large deflection analysis of laminated plates

A shear deformable theory accounting for the transverse-shear (in the sense of Reissner-Mindlin’s thick plate theory) and large deflections (in the sense of von Karman theory) is employed in the construction of variational statement. A four-node, lock-free, shear-flexible rectangular plate element based on the coupled displacement field is developed in this paper to carry out the large deflection analysis. The displacement field of the element is derived by making use of the linearized equations of static equilibrium. A bi-cubic polynomial distribution is assumed for the transverse displacement ‘w’. The field distribution for the in-plane displacements (u,v) and plate normal rotations (θ_x, θ_y) and twist (θ_xy) is derived using equilibrium of composite strips parallel to the plate edges. The displacement fields so derived are coupled through material couplings. The transverse shear strain fields of the proposed element do not contain inconsistent terms, so that the element predicts even shear-rigid bending accurately.The element is validated for a series of numerical problems and results for deflections and stresses are presented for rectangular composite plates with various boundary conditions, loading and lay-ups. The influence of the sign of the loading on the deflection of unsymmetrically laminated plates, in the large deflection regime is also investigated.     

Effects of box features on spine loading during warehouse order selecting.

Low back disorders in distribution centres or warehouses have been identified as an area of elevated risk in many industries. The task of an order selector requires workers manually to lift boxes from storage bins to a mobile pallet. This study explored the effect of box features and box location when lifting from a pallet in a storage bin upon spine loading. Ten experienced warehouse workers were asked to lift boxes from a pallet while the size, weight, handle features and location of the box on a pallet were changed. An EMG-assisted model was employed to assess spine compression, lateral shear and anterior-posterior shear during the lifts. The position from which the worker lifted a box on a pallet had the most profound effect on spine loading while the lower level of the pallet represented the greatest loadings on the spine. Box weight did not appear to be a feasible means of controlling spine loading unless its position on the pallet could also be controlled. The inclusion of handles had an effect similar to reducing the box weight by 4.5 kg, whereas box size did not effectively affect spine loading. The mechanisms by which these factors affect spine loading are discussed.     

Search strategy for scheduling flexible manufacturing systems simultaneously using admissible heuristic functions and nonadmissible heuristic functions

To scheduling flexible manufacturing system (FMS) efficiently, we propose and evaluate an improved search strategy and its application to FMS scheduling in the P-timed Petri net framework. On the execution of Petri net, the proposed method can simultaneously use admissible heuristic functions and nonadmissible heuristic functions for A^* algorithm. We also prove that the resulting combinational heuristic function is still admissible and more informed than any of its constituents. The experimental results of an example FMS and several sets of random generated problems show that the proposed search method performs better as we expected.     

A rotated nonconforming rectangular mixed element for elasticity

We present a low-order nonconforming mixed element for plane elasticity on rectangular meshes. The 3-dimensional space of rigid body motions is used to approximate the displacement and a 16-dimensional space is used to discretize the space of symmetric tensors. This element may be viewed as the rectangular analogue of the nonconforming Arnold-Winther element and is related to a discrete version of the elasticity differential complex with a nonconforming H ² element related to the rotated Q ₁ element.