Mathematics
Bin-packing Algorithms
Bin-packing algorithms are mathematical methods used to solve optimization problems where a set of items of different sizes must be packed into a limited number of containers or bins. The goal is to minimize the number of bins used or to maximize the space utilization of the bins. These algorithms have applications in logistics, transportation, and resource allocation.
Written by Perlego with AI-assistance
Related key terms
1 of 5
3 Key excerpts on "Bin-packing Algorithms"
eBook - PDFOperations Planning
Mixed Integer Optimization Models
- Joseph Geunes(Author)
- 2014(Publication Date)
- CRC Press(Publisher)
28 Operations Planning: Mixed Integer Optimization Models a material, can also be cast as bin packing problems when the objective con-sists of minimizing the number of standard-sized resources required to meet a given set of demands. The following subsection will discuss some well-known heuristic solution methods for the bin packing problem. Following this we will consider the more general version of SP formulated in the previous section, where each subset S may have a unique value of C S , and where this value may depend on the collection of elements in S . 3.3.1 Bin packing heuristics This section discusses four well-known and simple (but generally powerful) heuristic methods for solving bin packing problems. Each of these methods starts with a single open bin (bin 1) and proceeds down a list of items that must be allocated to bins, only opening a new bin when none of the existing open bins can accommodate the next item on the list. We use the convention of indexing the n th bin opened as bin n . In the most basic version of these heuristic approaches, the list of items is processed in an arbitrary order, and an item is inserted in the lowest indexed bin in which it will fit, given all prior assignments of items to bins (if none of the previously opened bins can accommodate the item, a new bin is then opened). This greedy heuristic approach is referred to as the first-fit method. Instead of inserting the next item in the list into the lowest indexed open bin, suppose we insert the item into the bin that will have the lowest remaining capacity after inserting the item, among all open bins into which the item can fit (again, if the item cannot fit in any of the open bins, a new one is opened). The resulting approach, called the best-fit method, requires more effort than the first-fit method on average, as the item’s size must be compared with the remaining capacity of all open bins at each step.
eBook - PDF- David P. Williamson, David B. Shmoys(Authors)
- 2011(Publication Date)
- Cambridge University Press(Publisher)
The bin-packing problem is related to a decision problem called the partition prob- lem. In the partition problem, we are given n positive integers b 1 , . . . , b n whose sum B = ∑ n i =1 b i is even, and we wish to know if we can partition the set of indices {1, . . . , n} into sets S and T such that ∑ i ∈S b i = ∑ i ∈T b i . The partition problem is well known to be NP-complete. Notice that we can reduce this problem to a bin-packing problem by setting a i = 2b i / B and checking whether we can pack all the pieces into two bins or not. This gives the following theorem. Theorem 3.8. Unless P = NP, there cannot exist a ρ -approximation algorithm for the bin-packing problem for any ρ < 3/2. However, consider the First-Fit-Decreasing algorithm, where the pieces are packed in order of non-increasing size, and the next piece is always packed into the first bin in which it fits; that is, we first open bin 1, and we start bin k + 1 only when the current piece does not fit into any of the bins 1, . . . , k . If FFD( I ) denotes the number of bins used by this algorithm on input I , and OPT( I ) denotes the number of bins used in the optimal packing, then a celebrated classic result shows that that FFD( I ) ≤ (11/9) OPT( I ) + 4 for any input I . Thus, significantly stronger results can be obtained by relaxing the notion of the performance guarantee to allow for small additive terms. In fact, it is completely consistent with our current understanding of complexity theory that there is an algorithm that always produces a packing with at most OPT( I ) + 1 bins.
eBook - PDF- Adedeji B. Badiru, Marlin U. Thomas, Adedeji B. Badiru, Marlin U. Thomas(Authors)
- 2009(Publication Date)
- CRC Press(Publisher)
An unlimited number of identical rectangular bins of width W and height H are available. The objective is to pack all items into the minimum number of bins, in such a way that no two items overlap and the item edges are parallel to those of the bins. Items may be packed in either of their two allowable orientations. It is assumed without loss of generality that all input data are positive integers and that any item will fit into a bin in at least one of its orientations. Lodi et al. (1999a) use the notation 2D|R|F (two dimensions |rotation allowed| free packing allowed) for this problem. The 2D-BPP is known to be NP-hard (Chu and Beasley, 1998). When considering practical sized 2D-BPPs, classical exact methods are insufficient. Most recently published work has investigated heuristic and metaheuristic approaches. Lodi et al. (2002a, 2002b) present surveys on 2D packing problems and advances in 2D packing. The first paper covers models, approximation algorithms, lower bounds and exact algorithms. The second paper discusses bounds, exact methods, heuristic approaches, and metaheuristic methods for the various classes of 2D prob-lems. Lodi et al. (1999b) present approximation algorithms for the 2D bin packing problem (BPP). There are several popular one-pass heuristic approaches for packing 2D rectangular items. The most basic of the 2D heuristics rely on a version of the bottom left (BL) heuristic (Baker et al., 1980). Chazelle (1983) provides the first O( n 2 ) implementations of a one-pass BL heuristic for the 2D-BPP, but offers no detail on how to keep the data structure updated. There are several different variations for selecting where an item is placed. Chazelle (1983) used the lowest possible BL stable location and broke ties by tak-ing the leftmost, Jakobs (1996) began at the top right and then alternated movements, first moving as far as possible toward the bottom then as far as possible to the left until the item was BL stable.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
