379,128 research outputs found
On-line bin-packing problem : maximizing the number of unused bins
No full textIn this paper, we study the on-line version of the bin-packing problem. We analyze the approximation behavior of an on-line bin-packing algorithm under an approximation criterion called differential ratio. We are interested in two types of results : the differential competitivity ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problem and for the quality of the algorithm developed to solve it. In its off-line version, the bin-packing problem, BP, is better approximated in differential framework than in standard one. Our objective is to determine if or not such result exists for the on-line version of BP.On-line algorithm, bin-packing problem, competitivity ratio.
Worst-case analysis for new online bin packing problems
No full textWe consider two new online bin packing problems, the online Variable Cost and Size Bin Packing Problem (o-VCSBPP) and the online Generalized Bin Packing Problem (o-GBPP). We take two well-known bin packing algorithms to address them, the First Fit (FF) and the Best Fit (BF). We show that both algorithms have an asymptotic worst-case ratio bound equal to 2 for the o-VCSBPP and this bound is tight. When there are enough bins of a particular type to load all items, FF and BF also have an absolute worst-case ratio bound equal to 2 for the o-VCSBPP, and this bound is also tight. In addition, we prove that no worst-case ratio bound of FF and BF can be computed for the o-GBPP. Therefore, we consider a natural evolution of these algorithms, the First Fit with Rejection and the Best Fit with Rejection, able to reject inconvenient bins at the end of the process. Similarly, we prove that no worst-case ratio of these algorithms can be computed for the o-GBPP. Finally, we give sucient conditions under which algorithms do not admit any performance ratio, and conclude that the worst-case results obtained for the o-VCSBPP and the o-GBPP also hold for the oine variant of these two problem
Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem
No full textWe present a new approximation algorithm for the two-dimensional bin-packing problem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e. g. if we open an new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.worst-case analysis;probabilistic analysis;bin-packing;heuristic algorithm;on-line algorithm;two-dimensional packing
Probabilistic analysis of algorithms for dual bin packing problems
No full textIn the dual bin packing problem, the objective is to assign items of given size to the largest possible number of bins, subject to the constraint that the total size of the items assigned to any bin is at least equal to 1. We carry out a probabilistic analysis of this problem under the assumption that the items are drawn independently from the uniform distribution on [0, 1] and reveal the connection between this problem and the classical bin packing problem as well as to renewal theory.
Bin-to-bin spectrum reconstruction method for analyzing γ-rays passing through a certain thickness of aluminum
No full textAgri Ibrahim Cecen University;IC Foudation2nd International Conference on Advances in Natural and Applied Sciences, ICANAS 2017 -- 18 April 2017 through 21 April 2017 -- 127507Energy distribution of Y-rays emitted from standard sources, passing through various thicknesses of Al medium, were obtained by using 5.08cm x 5.08cm NaI(Tl) detector. The full energy peak and the total efficiency, photopeak/total (P/T) ratios and energy resolution of NaI(Tl) detector were measured using standard Y-ray sources. Detector response functions (DRFs) were obtained in every energy value of Y-ray rays by means of P/T ratios and energy resolutions. Y-rays incoming to the slice-shape geometry medium, can take all the energy values between 0 and the maximum energy. The energy range is divided into n lower energy region. DRFs are obtained for the energy values correspond to the midpoint of each energy range. In this way, the response matrix is developed. A bin to bin unfolding method is applied to the Y-ray spectra and the results are compared with the spectra obtained by the Monte Carlo method. © 2017 Author(s)
Commentario breve alla Costituzione, II ed., a cura di S. Bartole e R. Bin
No full textnuova edizione, totalmente riscritta, dello "storico" commentario alla costituzion
Extreme-Point-based Heuristics for the Three-Dimensional Bin Packing problem
No full textOne of the main issues in addressing three-dimensional packing problems is finding an efficient and accurate definition of the points at which to place the items inside the bins, because the performance of exact and heuristic solution methods is actually strongly influenced by the choice of a placement rule. We introduce the extreme point concept and present a new extreme point-based rule for packing items inside a three-dimensional container. The extreme point rule is independent from the particular packing problem addressed and can handle additional constraints, such as fixing the position of the items. The new extreme point rule is also used to derive new constructive heuristics for the three-dimensional bin-packing problem. Extensive computational results show the effectiveness of the new heuristics compared to state-of-the-art results. Moreover, the same heuristics, when applied to the two-dimensional bin-packing problem, outperform those specifically designed for the proble
A heuristic procedure for one dimensional bin packing problem with additional constraints
No full textWe proposed a heuristic algorithm to solve the one-dimensional bin-packing problem with additional constraints. The proposed algorithm has been applied to solve a practical vehicle-allocation problem. The experimental results show that our proposed heuristic provides optimal or near-optimal results, and performs better than the first fit decreasing algorithm modified to incorporate additional constraints.
Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints
No full textThe paper examines a new problem in the irregular packingliterature that has existed in industry for decades;two-dimensional irregular (convex) bin packing with guillotineconstraints. Due to the cutting process of certain materials, cutsare restricted to extend from one edge of the stock-sheet toanother, called guillotine cutting. This constraint is commonplace in glass cutting and is an important constraints intwo-dimensional cutting and packing problems. In the literature,various exact and approximate algorithms exist for finding the twodimensional cutting patterns that satisfy the guillotine cuttingconstraint. However, to the best of our knowledge, all of thealgorithms are designed for solving rectangular cutting where cutsare orthogonal with the edges of the stock-sheet. In order tosatisfy the guillotine cutting constraint using these approaches,when the pieces are non-rectangular, practitioners implement a twostage approach. First, pieces are enclosed within rectangle shapesand then the rectangles are packed. Clearly, imposing this condition is likely to lead to additional waste. Thispaper aims to generate guillotine-cutting layouts of irregularshapes using a number of strategies. The investigation comparestwo two-stage approaches; one approximates pieces by rectangles,the other approximates pairs of pieces by rectangles usingphi-functions for optimal clustering. Both these approaches usestate of the art rectangle bin packing with guillotineconstraints. Further, we design and implement a one-stage approachusing a self-adapted forest search algorithm. Experimental resultsshow the one-stage strategy to produce good solutions in less timeover the two-stage approach
Ant colony optimisation and local search for bin-packing and cutting stock problems
No full textThe Bin Packing Problem and the Cutting Stock Problem are two related classes of NP-hard combinatorial optimization problems. Exact solution methods can only be used for very small instances, so for real-world problems, we have to rely on heuristic methods. In recent years, researchers have started to apply evolutionary approaches to these problems, including Genetic Algorithms and Evolutionary Programming. In the work presented here, we used an ant colony optimization (ACO) approach to solve both Bin Packing and Cutting Stock Problems. We present a pure ACO approach, as well as an ACO approach augmented with a simple but very effective local search algorithm. It is shown that the pure ACO approach can compete with existing evolutionary methods, whereas the hybrid approach can outperform the best-known hybrid evolutionary solution methods for certain problem classes. The hybrid ACO approach is also shown to require different parameter values from the pure ACO approach and to give a more robust performance across different problems with a single set of parameter values. The local search algorithm is also run with random restarts and shown to perform significantly worse than when combined with ACO
- …
