Variability reduction with multiweighing proceedings

Summary In this paper we study the variability reduction gain in the production processes that require a process of packing with the objective of sales at constant nominal weights. We have obtained the value of the percentage variability reduction index in the packing processes of units formed by a fixed number of pieces attending to random packing and multiple weighting with variable number of scaling pan packing criteria. These indexes have been obtained both for only one packing objective processe and for double objective packing processes. Collaborator in the Catalan Institute of Technology (ICT).     

On genetic algorithms for the packing of polygons

A genetic algorithm for placing polygons on a rectangular board is proposed. The algorithm is improved by combination with deterministic methods.     

Multiple packing in sum-type metric spaces

We present the exact solution of the asymptotics of the multiple packing problem in a finite space with a sum-type metric.     

On packing time-respecting arborescences

We present a slight generalization of the result of Kamiyama and Kawase (2015) on packing time-respecting arborescences in acyclic pre-flow temporal networks. Our main contribution is to provide the first results on packing time-respecting arborescences in non-acyclic temporal networks. As negative results, we prove the NP-completeness of the decision problem of the existence of 2 arc-disjoint spanning time-respecting arborescences and of a related problem proposed in this paper.     

Computing the asymptotic worst-case of bin packing lower bounds

This paper addresses the issue of computing the asymptotic worst-case of lower bounds for the Bin Packing Problem. We introduce a general result that allows to bound the asymptotic worst-case performance of any lower bound for the problem and to derive for the first time the asymptotic worst-case of the well-known bound L₃ by Martello and Toth. We also show that the general result allows to easily derive the asymptotic worst-case of several lower bounds proposed in the literature.     

An infinite family of subcubic graphs with unbounded packing chromatic number

Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number.     

On packing of rectangles in a rectangle

It is known that ${\sum }_{i=1}^{\infty }1∕\left(i(i+1)\right)=1$. In 1968, Meir and Moser (1968) asked for finding the smallest $?$ such that all the rectangles of sizes $1∕i\times 1∕(i+1)$, $i\in \{1,2,\dots \}$, can be packed into a square or a rectangle of area $1+?$. First we show that in Paulhus (1997), the key lemma, as a statement, in the proof of the smallest published upper bound of the minimum area is false, then we prove a different new upper bound. We show that $?\le 1.26?10^{?9}$ if the rectangles are packed into a square and $?\le 6.878?10^{?10}$ if the rectangles are packed into a rectangle.     

An improved typology of cutting and packing problems

The number of publications in the area of Cutting and Packing (C&P) has increased considerably over the last two decades. The typology of C&P problems introduced by Dyckhoff [Dyckhoff, H., 1990. A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159] initially provided an excellent instrument for the organisation and categorisation of existing and new literature. However, over the years also some deficiencies of this typology became evident, which created problems in dealing with recent developments and prevented it from being accepted more generally. In this paper, the authors present an improved typology, which is partially based on Dyckhoff’s original ideas, but introduces new categorisation criteria, which define problem categories different from those of Dyckhoff. Furthermore, a new, consistent system of names is suggested for these problem categories. Finally, the practicability of the new scheme is demonstrated by using it as a basis for a categorisation of the C&P literature from the years between 1995 and 2004.     

Fractional Brownian motion and packing dimension

LetX(t) (tR ^N ) be a fractional Brownian motion of index inR ^d . For any compact setER ^N , we compute the packing dimension ofX(E).Partially supported by an NSF grant.     

A note on packing paths in planar graphs

Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths.Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Seb (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.Research partially supported by the Hungarian National Foundation for Scientific Research Grants OTKA 2118 and 4271.     

A space on which diameter-type packing measure is not Borel regular

We construct a separable metric space on which 1-dimensional diameter-type packing measure is not Borel regular.

     

Linear models for the approximate solution of the problem of packing equal circles into a given domain

The linear models for the approximate solution of the problem of packing the maximum number of equal circles of the given radius into a given closed bounded domain G are proposed. We construct a grid in G; the nodes of this grid form a finite set of points T, and it is assumed that the centers of circles to be packed can be placed only at the points of T. The packing problems of equal circles with the centers at the points of T are reduced to 0–1 linear programming problems. A heuristic algorithm for solving the packing problems based on linear models is proposed. This algorithm makes it possible to solve packing problems for arbitrary connected closed bounded domains independently of their shape in a unified manner. Numerical results demonstrating the effectiveness of this approach are presented.     

On the packing of fourteen congruent Spheres in a cube

We shall give the maximum radius of fourteen congruent, nonoverlapping spheres in a cube.      

A goal-driven approach to the 2D bin packing and variable-sized bin packing problems

In this paper, we examine the two-dimensional variable-sized bin packing problem (2DVSBPP), where the task is to pack all given rectangles into bins of various sizes such that the total area of the used bins is minimized. We partition the search space of the 2DVSBPP into sets and impose an order on the sets, and then use a goal-driven approach to take advantage of the special structure of this partitioned solution space. Since the 2DVSBPP is a generalization of the two-dimensional bin packing problem (2DBPP), our approach can be adapted to the 2DBPP with minimal changes. Computational experiments on the standard benchmark data for both the 2DVSBPP and 2DBPP shows that our approach is more effective than existing approaches in literature.     

New upper bounds for online strip packing

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.     

Optimal spray patterns for counterflow cooling towers with structured packing

In counterflow cooling towers, non-uniform patterns of flow are the consequence of the application of water from circular spray nozzles set in a square manifold. A detailed computational model for the performance of a tower accounting for this non-uniform water flow in cellular packing has been developed. The radial spray pattern of individual nozzles producing the best possible thermal performance was determined by optimization. It was concluded that for a particular nozzle manifold and packing arrangement, a performance limitation exists due to the inherently non-uniform pattern of water flow.     

Complexity of the packing coloring problem for trees

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.     

Simplex pivots on the set packing polytope

This paper considers the set packing problem max{wx: Ax b, x 0 and integral}, whereA is anm × n 0–1 matrix,w is a 1 ×n weight vector of real numbers andb is anm × 1 vector of ones. In equality form, its linear programming relaxation is max{wx: (x, y) P(A)} whereP(A) = {(x, y):Ax +I _m y =b, x0,y0}. Letx ¹ be any feasible solution to the set packing problem that is not optimal and lety ¹ =b – Ax ¹; then (x ¹,y ¹) is an integral extreme point ofP(A). We show that there exists a sequence of simplex pivots from (x ¹,y ¹) to (x*,y*), wherex* is an optimal solution to the set packing problem andy* =b – Ax*, that satisfies the following properties. Each pivot column has positive reduced weight and each pivot element equals plus one. The number of pivots equals the number of components ofx* that are nonbasic in (x ¹,y ¹).This research was supported by NSF Grants ECS-8005360 and ECS-8307473 to Cornell University.     

A two-stage intelligent search algorithm for the two-dimensional strip packing problem

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances.