An algorithm for the strip packing problem using collision free region and exact fitting placement

The irregular shape packing problem is approached. The container has a fixed width and an open dimension to be minimized. The proposed algorithm constructively creates the solution using an ordered list of items and a placement heuristic. Simulated annealing is the adopted metaheuristic to solve the optimization problem. A two-level algorithm is used to minimize the open dimension of the container. To ensure feasible layouts, the concept of collision free region is used. A collision free region represents all possible translations for an item to be placed and may be degenerated. For a moving item, the proposed placement heuristic detects the presence of exact fits (when the item is fully constrained by its surroundings) and exact slides (when the item position is constrained in all but one direction). The relevance of these positions is analyzed and a new placement heuristic is proposed. Computational comparisons on benchmark problems show that the proposed algorithm generated highly competitive solutions. Moreover, our algorithm updated some best known results. (C) 2012 Elsevier Ltd. All rights reserved.

Anomalous centrality evolution of two-particle angular correlations from Au-Au collisions at root s(NN)=62 and 200 GeV

We present two-dimensional (2D) two-particle angular correlations measured with the STAR detector on relative pseudorapidity eta and azimuth phi for charged particles from Au-Au collisions at root s(NN) = 62 and 200 GeV with transverse momentum p(t) >= 0.15 GeV/c, vertical bar eta vertical bar <= 1, and 2 pi in azimuth. Observed correlations include a same-side (relative azimuth <pi/2) 2D peak, a closely related away-side azimuth dipole, and an azimuth quadrupole conventionally associated with elliptic flow. The same-side 2D peak and away-side dipole are explained by semihard parton scattering and fragmentation (minijets) in proton-proton and peripheral nucleus-nucleus collisions. Those structures follow N-N binary-collision scaling in Au-Au collisions until midcentrality, where a transition to a qualitatively different centrality trend occurs within one 10% centrality bin. Above the transition point the number of same-side and away-side correlated pairs increases rapidly relative to binary-collision scaling, the eta width of the same-side 2D peak also increases rapidly (eta elongation), and the phi width actually decreases significantly. Those centrality trends are in marked contrast with conventional expectations for jet quenching in a dense medium. The observed centrality trends are compared to perturbative QCD predictions computed in HIJING, which serve as a theoretical baseline, and to the expected trends for semihard parton scattering and fragmentation in a thermalized opaque medium predicted by theoretical calculations and phenomenological models. We are unable to reconcile a semihard parton scattering and fragmentation origin for the observed correlation structure and centrality trends with heavy-ion collision scenarios that invoke rapid parton thermalization. If the collision system turns out to be effectively opaque to few-GeV partons the present observations would be inconsistent with the minijet picture discussed here. DOI: 10.1103/PhysRevC.86.064902

Collision free region determination by modified polygonal Boolean operations

Cutting and packing problems are found in numerous industries such as garment, wood and shipbuilding. The collision free region concept is presented, as it represents all the translations possible for an item to be inserted into a container with already placed items. The often adopted nofit polygon concept and its analogous concept inner fit polygon are used to determine the collision free region. Boolean operations involving nofit polygons and inner fit polygons are used to determine the collision free region. New robust non-regularized Boolean operations algorithm is proposed to determine the collision free region. The algorithm is capable of dealing with degenerated boundaries. This capability is important because degenerated boundaries often represent local optimal placements. A parallelized version of the algorithm is also proposed and tests are performed in order to determine the execution times of both the serial and parallel versions of the algorithm.

Parallel Layout Construction Algorithm for Irregular Shape Packing Problems

Cutting and packing problems arise in a variety of industries, including garment, wood and shipbuilding. Irregular shape packing is a special case which admits irregular items and is much more complex due to the geometry of items. In order to ensure that items do not overlap and no item from the layout protrudes from the container, the collision free region concept was adopted. It represents all possible translations for a new item to be inserted into a container with already placed items. To construct a feasible layout, collision free region for each item is determined through a sequence of Boolean operations over polygons. In order to improve the speed of the algorithm, a parallel version of the layout construction was proposed and it was applied to a simulated annealing algorithm used to solve bin packing problems. Tests were performed in order to determine the speed improvement of the parallel version over the serial algorithm