Content area
We consider a two-bar charts packing problem in which it is necessary to pack bar charts consisting of two bars in a unit-height strip of minimum length. Each bar has a height of at most 1 and unit length. The problem under consideration is NP-hard and generalizes the bin packing problem and two-dimensional vector packing problem. This paper proves updated accuracy estimates and time complexity for several previously developed polynomial approximation algorithms for the two-bar charts packing problem and particular cases of the problem. We show the attainability of the estimates. Furthermore, we consider a problem of packing an unlimited number of bar charts belonging to
INTRODUCTION
The bar charts packing problem (BCPP) arose when optimizing an investment portfolio in the oil and gas industry [1]. Let us assume that the territory of a field is divided into clusters for each of which a development project is known. The project is characterized, in particular, by annual oil production volumes. Thus, if the year of the project start is known, then the production volumes in the first and all subsequent years of the project implementation are also known. The oil production schedule for each project can be presented as a histogram in which the height of the bar corresponds to the production volume in the corresponding year. It is necessary to determine the launch year of each project so that the total execution time of all projects is minimal, and the annual production volume does not exceed a specified value, determined, for example, by the pipeline throughput.
The described problem reduces to finding a bar charts packing into a part of a semi-infinite strip of minimum length. Previously, a special case of the problem called 2-BCPP was studied, where each bar chart consists of two bars. For convenience, we will denote a bar chart with two bars by 2-BC. The 2-BCPP problem was first formulated in [2], and then studied in [3, 4, 5, 6–7]. Let there be a semi-infinite horizontal strip of unit height and a set consisting of -BC. We divide the strip into equal cells of unit height and width. All bar charts have unit width and positive height of at most one. In an feasible packing, the bar charts can move vertically, but are continuous horizontally, and they cannot be rearranged. Moreover, in an feasible packing, the sum of the heights of the bars in one cell is at most one. The -BCPP problem is to find an feasible packing of -BC into a minimum number of cells. Figure 1 shows an example of an feasible packing of three bar charts into four cells, i.e., the packing length is four.
[See PDF for image]
Fig. 1.
An example of feasible packing of three -BCs.
Similar problems that are well studied at the moment and that are generalized by the -BCPP problem are the Bin Packing Problem (BPP) [8, 9, 10, 11, 12, 13, 14, 15–16] and the Two-Dimensional Vector Packimng Problem (2-DVPP) [17, 18, 19–20].
In the classical one-dimensional bin packing problem (BPP), one is given a set of objects , the size of each object, and a set of identical bins of unit capacity are given. The goal is to place all objects into the minimum number of bins. The BPP is a special case of the -BCPP problem, where each -BC consists of columns of the same height. If , then the BPP problem is ( )-nonapproximable for any positive [8, 9]. As shown in [10], a 3/ -approximate solution can be found by the First Fit Decreasing (FFD) algorithm. In the FFD algorithm, items are first numbered in nonincreasing size order, then scanned in numbered order, and the current item is placed in the first bit it fits into. In 2007, it was proven that the FFD algorithm uses at most bins, where is the minimum number of bins for packing items of set , and an example of attainability of this estimate was found [11]. A modified version of the FFD algorithm (Modified First Fit Decreasing, MFFD) groups items by size and packs items of different groups separately. Johnson and Gary, who constructed the MFFD algorithm, showed that it uses at most bins. Later, the additive constant was reduced to 1. In [14], an asymptotic polynomial approximation scheme (APTAS) was proposed for the BPP problem and it was shown that for any there exists a linear-time algorithm that uses at most bins. Also, for the BPP problem, an asymptotic fully polynomial approximation scheme [15] and an additive approximation algorithm that constructs a packing of length no greater than [16] are constructed.
The 2-DVPP problem is a generalization of the BPP problem and a special case of the 2-BCPP. In this case, each 2-BC pair can be located in a bin one above the other. In this case, the objects and the bins are characterized by two parameters. The goal is to pack all objects into the minimum number of bins without violating constraints on both parameters. In 2003, a 2-approximation algorithm for the 2-DVPP was presented the complexity of which is equal to [17]. A detailed review of approximation algorithms for the 2-DVPP can be found in [18]. The best algorithm constructs ( )-approximate solution for any [19]. In 1997, it was proved that there does not exist any APTAS scheme for the 2-DVPP problem if [20].
On the other hand, the 2-BCPP is a special case of the Resource-Constrained Project Scheduling Problem (RCPSP) [21]. In the 2-BCPP, each project consists of two jobs of unit duration that are executed one after the other without interruption. A project can be represented as a 2-BC in which the amount of renewable resource consumed corresponds to the height of the bar. The goal is to determine the start time of each project such that all projects are executed in minimal time given the resource constraint. The RCPSP is NP-hard, and no polynomial algorithms with guaranteed accuracy estimates are known for it. As a rule, heuristic algorithms are developed to construct an approximate solution, and their a posteriori analysis is carried out [22, 23, 24–25].
The -BCPP problem is quite new and is considered in a small number of publications [2, 3, 4, 5, 6–7, 26]. In [2], an algorithm of linear complexity is proposed that constructs a packing of length at most , where is the minimum length of a -BC packing. In [3, 4, 5], special cases of the -BCPP problem were studied when each -BC contains at least one bar higher than and—additionally—when all -BCs are either nonincreasing or nondecreasing. In [3], two polynomial -approximation algorithms were proposed to solve these problems. The authors of [5] proved that when each -BC contains a bar of height greater than , the -BCPP remains NP-hard in the strong sense. In the same paper, an algorithm is proposed that constructs a packing of length at most . In [6], an algorithm is proposed for finding a linearly ordered packing in which the first bars of all -BCs are in different cells of length at most . In [7], classes of problems are considered that are both generalizations of the -BCPP and its special cases. Using known algorithms, the authors find upper and lower bounds on the objective function for the -BCPP problem, and also propose two integer linear programming models and conduct a numerical experiment on six different databases. In [26], the problem of packing bar charts consisting of three bars is studied. A linear-time-consuming algorithm is proposed that constructs a packing of length no greater than . If each bar chart contains a bar greater than , then the problem is proven to be NP-hard.
The results in this paper are refined estimates for previously developed algorithms for both the general and special cases of the -BCPP problem. Examples of attainability of the estimates are found. For the special case where the height of each bar does not exceed , an algorithm of linear complexity is proposed that constructs a packing of length no greater than . An example of asymptotic attainability of this estimate is given. In addition, the problem of packing an unlimited number of -BCs belonging to one of types is considered. In this problem, it is necessary to find a packing of maximum density. For this purpose, an algorithm was developed that constructs an optimal packing with complexity , where is the upper bound on the number of options for filling one cell with the first bars of the -BCs of the types.
1. STATEMENT OF THE PROBLEM
Let a horizontal semiinfinite (left-bounded) strip of unit height and a set , , of bar charts consisting of two bars be given. For each -BC , we denote the height of the first (left) bar by , and the height of the second (right) one by . We divide the strip into identical rectangles of unit height and width, which we call cells, and number them with positive integers starting from the left edge of the strip.
Definition 1.
A -BC is nonincreasing (nondecreasing) if ( ).
Definition 2.
A packing of a set of bar charts is a function that to each histogram assigns an integer corresponding to the number of the cell of the strip that its first bar falls into. Thus, in the packing , the bars of the -BC occupy cells and .
Definition 3.
A packing is feasible if the sum of the heights of the bars that fall into each cell of the strip does not exceed 1.
Only feasible packings are considered below.
Definition 4.
The length of a packing is the number of cells in the strip in which at least one bar is located.
We can assume that any packing starts from the first cell and that each of the cells contains at least one bar. If this is not the case, then the entire packing or part of it can be shifted to the left.
The -BCPP problem consists of constructing a feasible packing of a set of bar charts of minimum length (i.e., using the minimum number of cells).
The -BCPP problem was first formulated as a Boolean linear programming problem in [2]. Below we reproduce this formulation for the convenience of the reader. Introduce the variables Then the -BCPP is written in the form
1
2
3
The objective function (1) is the number of cells populated by at least one bar. Conditions (2) guarantee that all -BCs from the set are packed into a strip. It follows from inequalities (3) that in each cell the sum of the heights of the bars does not exceed the height of the strip.
2. REFINED ESTIMATES
2.1. Algorithm
2.1.1. Greedy Algorithm
In [2], a greedy Algorithm of complexity was proposed that is used as a procedure in Algorithm [2]. In this paper, we propose to use another version of the greedy algorithm, which is called [1]. Applying this algorithm at the second stage of Algorithm will allow it to be implemented with less complexity. The operation of is as follows. Let be an arbitrarily ordered set of elements from . The first element from is placed in cells 1 and 2 and removed from . Elements removed from are already packed, and they are not moved further. Then the following standard procedure is performed. For the first bar chart from , the leftmost position is sought that does not violate the feasibility of the packing and the order of -BCs. Thus, for an arbitrary -BC , the inequalities hold for all (see Fig. 1). The location of the bar chart in the packing is fixed, and the -BC itself is removed from . The algorithm stops when . The complexity of is equal to .
Obviously, depending on the order of the bar charts in the set , Algorithm can construct different solutions.
2.1.2. Refined accuracy estimate for Algorithm
Definition 5.
A -BC is called large if at least one of its bars is higher than . Also, large is the bar itself that is higher than ; otherwise it is small.
Let us recall Algorithm for solving the 2-BCPP problem from [2]. It consists of three stages. The first preparatory stage consists of merging the bar charts in such a way that each 2-BC becomes as large as possible. To do this, a pair of bar charts and with are merged into one new 2-BC with bar heights and . As a result, the set of bar charts is transformed: two bar charts and are removed from it and one new 2-BC is added. In one scan of the bar charts, for all -BCs, except possibly one, at least one bar becomes large. At the second stage of the algorithm, the updated set of -BCs is split into two subsets and . Nonincreasing bar charts are placed in , and nondecreasing ones are placed in (Fig. 2b). The set of elements from is packed using Algorithm from left to right, and the set of elements from is packed by an analog of Algorithm from right to left. Note that Algorithm of quadratic complexity was used to pack the sets and in [2]. Two packings are obtained—left and right. At the third stage of Algorithm , the right packing of elements of set is shifted maximally to the left without violating the feasibility of the packing (Fig. 2c).
[See PDF for image]
Fig. 2.
Illustration of the operation of Algorithm : (a) set , (b) sets of combined bar charts, (c) packing constructed by Algorithm .
Theorem 1.
Algorithm with complexity constructs a -approximate solution to the -BCPP problem, and this bound is achievable.
Proof. In [2] it is proved that as a result of Algorithm the packing density of all cells, except possibly one, is greater than . Thus, the algorithm constructs a packing for the -BCPP the length of which is no more than . The estimate for the length of the constructed packing remains valid if at the second stage the packing of elements of the sets and is carried out by Algorithm . The proof of this statement coincides with the proof of Theorem 1 in [2] if Algorithm is replaced by .
Let be the height of the last bar in the left packing, and let be the height of the first bar in the right packing. In addition, let , , and let be the length of the packing constructed by Algorithm . Since after shifting the right packing to the left as much as possible, in the worst case the density of all cells except one is greater than , the following inequalities hold: Besides this, it is obvious that , and hence we obtain or . However, since the packing length is an integer, we finally have .
The first stage of Algorithm can be implemented with complexity as follows. Let . We scan the bar charts in numerical order. If the next -BC has a large first bar and it is larger than the second, then we place it in the set . If the next -BC has a large second barf and it is larger than the first, then we place it in the set . If both bar are small and , then we place the current bar chart in and continue scanning. If both charts are small and , then we merge the current bar chart with the bar chart located in . If the resulting new combined bar chart has at least one bar greater than , then we exclude it from and place it in if its first column is greater than the second, otherwise we place it in . If, after combining the current bar chart with the bar chart from , we obtain a new bar chart in which both bars are small, then we leave the new combined bar chart in and move on to considering the next bar chart from . Thus, the sets and are formed as a result of one review of all bar charts.
At the second stage, the bar chart packings from sets and are independently constructed using Algorithm . At each step of Algorithm , one bar chart is added to the already constructed packing. Due to the fact that large -BCs are nonincreasing (nondecreasing) in the corresponding packings, in each cell of the packings of sets and there can be no more than two bars. Therefore, for an arbitrary bar chart it is sufficient to check the fulfillment of the inequality to determine its best feasible position. If the inequality is satisfied, then the first bar of the -BC is placed in the last nonempty cell of the packing, otherwise, in the first empty cell. Thus, the complexity of the process of finding the best position for the current bar chart is limited by . The number of steps of Algorithm does not exceed . Therefore, the complexity of the second stage of the algorithm is . The complexity of the third stage is . Thus, the complexity of Algorithm is .
Let us consider the following example (Fig. 3a). Let , and let the bar charts have the following bar heights: , , , , , , , , , , , , , . At the first stage, Algorithm looks at -BCs in numerical order and combines them until all of them, except the last one, become large. As a result, -BCs 1 and 2, 3 and 4, 5 and 6 will be combined to form a new updated list of bar charts , where , , , , , , , (Fig. 3b).
All -BCs in are nonincreasing, so the right packing is empty. At the second stage, -BCs are packed by Algorithm . The first -BC is placed in cells 1 and 2 and removed from . Since for the second -BC the sum is greater than one, the algorithm assigns to it the cell of the strip with number 3 and removes it from . Similarly, the algorithm assigns to the third and fourth -BCs the cells of the strip with numbers 5 and 7, respectively, and finishes its work (Fig. 33c). The length of the constructed packing is . However, -BCs from set can be packed optimally into four cells (Fig. 3d). In this case, the sum of the heights of the bars in the first cell is equal to , in the second cell, to , in the third cell, to , and in the last cell of the optimal packing, to . Thus, in the considered example we have . The proof of the theorem is complete.
[See PDF for image]
Fig. 3.
Example of attainability of the estimate : (a) set , (b) set of united nonincreasing -BCs, (c) packing constructed by Algorithm , (d) optimal packing.
After the first stage of Algorithm , several bar charts are combined into one bar chart; this reduces the number of feasible packings. In addition, the length of the packing constructed by Algorithm depends considerably on the order of elements in list . The following numerical experiment was carried out in [2]. To assess the impact of the bar merging procedure in Algorithm , an algorithm called is implemented, consisting only of the second and third stages of Algorithm . Algorithm splits all bar charts in one scan into two sets of nonincreasing and nondecreasing -BCs. In this case, the corresponding sets and contain arbitrary -BCs (in Algorithm after the first stage these sets contained large -BCs). Then Algorithm constructs the left and right packings using Algorithm and shifts the right packing to the left as much as possible without violating feasibility.
2.2. Packing Small Bar Charts
By -BCPP| we denote a special case of the -BCPP problem where the height of both bars of each bar charts does not exceed , and we prove the following theorem.
[See PDF for image]
Fig. 4.
Example of the operation of Algorithm for : (a) the set of -BCs, (b) left and right packings, (c) packing constructed by Algorithm .
Theorem 2.
For the -BCPP| problem, Algorithm with complexity constructs a packing of length no greater than , and this estimate is asymptotically achievable.
Proof. Let the height of all bars not exceed . First constructs a left packing of nonincreasing bar charts, placing -BCs one above the other in the first two cells as long as possible. After that, two cases are possible:
The first bar of the next -BC does not fit into the second cell.
The first bar of the next -BC can be placed into the second cell.
In the first case, the packing density of the first two cells is greater than . In the second case, as a result of further work of the algorithm, the first bars of other -BCs fall into the second cell until the unfilled space of the cell becomes less than . Therefore, in this case too, the density of the first two cells is greater than .
Then similarly fills the following cells. When placing the last bar chart in the left packing the cells into which its columns fall may have a density of no more than (Fig. 4b). Thus, in each cell of the left packing, except possibly the last two, the density is greater than .
The right packing of nondecreasing bar charts is constructed in a similar mirror-image manner (from right to left), ensuring that the density of all cells of the right packing, except possibly the first two, is greater than .
At the last stage of Algorithm , the right packing is shifted to the left as much as possible without violating the feasibility of the packing. Let and denote the total height of the bars in the penultimate and last cells of the left packing, respectively, and let and denote the total height of the bars in the second and first cells of the right packing, respectively. After shifting the right packing to the left as much as possible, we obtain one of the following cases:
.
, .
.
In the first case, the left and right packings cannot merge into any cell. This means that the combined density of the last cell of the left packing and the first cell of the right packing is greater than . However, due to the nondecreasing and nonincreasing nature of the bar charts in different packings, the penultimate cell of the left packing and the second cell of the right packing also have a combined density greater than . Thus, four cells of the resulting packing have a density greater than , and all other cells have a density greater than , which yields an estimate of .
In the second case, the packings were combined into two cells the density of which can be less than . The density of all other cells, except for the two common ones, is more than , which also allows us to estimate the length of the packing as .
In the third case, the packings were combined in only one cell. Without loss of generality, we assume that the packings cannot be combined in two cells because the inequality is not satisfied. Then the common cell of the two packings and the cell with the previous number have a combined density greater than . The density of the cell with the number following the common cell can be less than . The density of all other cells is greater than , which also gives the estimate . The estimate has been obtained in all the cases considered.
As a result of one viewing of all bar charts, the sets and are formed. Then the packing of the elements of the sets and is constructed using Algorithm . At each step of Algorithm , one bar chart is added to the already constructed packing. The complexity of the process of finding the best position for the current bar chart is limited by the function . The number of steps of Algorithm is at most . Therefore, the complexity of constructing the left and right packings is equal to . The complexity of shifting the right packing is equal to . Thus, Algorithm has a complexity equal to .
Consider the following example. Let 1 (the height of the strip) be divisible by without a remainder. We have bar charts, of which are nonincreasing with bar heights , , , are nonincreasing with bar heights , , , and one is nondecreasing -BC with bar heights , . The inequalities are satisfied for any positive . This means that after the algorithm places the first bar charts, the space in the first cell and more than and less than in the second cell is unoccupied. Then nonincreasing bar charts with the height of both bars are packed starting from the third cell, since placing even one not yet packed nonincreasing -BC in the first two cells violates feasibility. Note that after shifting the right packing, consisting of a single nondecreasing -BC, the left and right packings have no common cells. The length of the approximate packing constructed by Algorithm for this example is equal to (Fig. 5a). The bar charts are optimally packed into 4 cells (Fig. 5b). Thus, as , the estimate is achieved for the length of the packing constructed by the algorithm. The proof of the theorem is complete.
[See PDF for image]
Fig. 5.
Example of asymptotic attainability of the estimate for Algorithm , , : (a) packing constructed by Algorithm , (b) optimal packing.
2.3. Refined Accuracy Estimate for Algorithm
Algorithm was first proposed in the paper [3]. Let us give a brief description of this algorithm for solving the -BCPP problem in the case where each -BC is large and nonincreasing.
Definition 6.
Two -BCs form a -union if cells of the packing contain bars of both -BCs.
Let each - be large and nonincreasing. Then each cell can contain no more than two bars, and two -BCs can form only a 1-union. Obviously, -BCs before packing occupy cells of the strip. Each 1-union reduces the length of the packing by .
[See PDF for image]
Fig. 6.
Example of Algorithm : (a) the set of large nonincreasing -BCs, (b) the first matching, , (c) the second matching, .
Given a set of bar charts , we construct a graph in which the vertices correspond to the bar charts, , with if -BCs and can form a 1-union. At the first step of Algorithm , a maximum matching of cardinality is constructed in the graph . The result is 2- and -BCs that correspond to the set of vertices of the new graph . The graph has edge if the bar charts and can form a 1-union. At an arbitrary step , the next maximal matching of cardinality is constructed in the corresponding graph . The algorithm stops if the next graph is empty, . Figure 6 shows an example of the operation of Algorithm .
If there are no edges in the graph , then the length of the packing constructed by Algorithm is equal to
4
In [3] it is proved that the optimal packing can also be constructed by successively finding matchings. Let a matching of cardinality be constructed in the optimal packing at step . Then the length of the optimal packing is5
Moreover, the paper [3] proves the inequalities6
and also the fact that Algorithm constructs a 3/2-approximate solution to the 2-BCPP problem if all 2-BCs are large and nonincreasing. It turns out that this estimate can be reduced, as shown in the following theorem.[See PDF for image]
Fig. 7.
Example of attainability of : (a) set , (b) packing constructed by Algorithm , (c) optimal packing.
Theorem 3.
If all -BCs are large and nonincreasing, then for the -BCPP Algorithm constructs a packing whose length does not exceed , and this bound is attainable.
Proof. From (4)–(6) it follows that , , or . Then It is obvious that large nondecreasing -BCs can form no more than 1-unions. Therefore, . Finally, we have
Let us consider the following example. Let and let the bar charts have the following bar heights: , , , , , , , , , (Fig. 7a). Obviously, the cardinality of the first matching is no more than 2, since the set consists of five -BCs. If in the first matching constructed by the algorithm the 1-union is formed by -BCs 2 and 5, 3 and 4, then other 1-unions are impossible, and the algorithm stops. The length of the approximate packing is (Fig. 7b). The optimal packing can be obtained if -BCs are successively 1-united in the order of numbering, its length is (Fig. 7c). Thus, . The proof of the theorem is complete.
3. PACKING -BCS OF A LIMITED NUMBER OF TYPES
Suppose that one has an unlimited number of -BCs that belong to one of types, , . In particular, if , then all -BCs are the same. Since there are infinitely many bar charts, the length of the packing does not make sense, so we will estimate its density. If , then the number of different combinations of filling each cell is finite. Consequently, in any packing sooner or later there will be a cell whose combination of the first -BC bars has already been encountered in some cell with a lower number (Fig. 8). Obviously, if the packing is constructed by a deterministic algorithm, then starting from this cell the filling of some sequence of cells in the packing will be infinitely repeated. We will call such a sequence the regular part of the packing.
Definition 7.
In every packing of infinitely many -BCs of types there is a sequence of cells in which the first and last cells are filled with the same combination of the first -BC bars. The regular part of the packing is the first such sequence without the last cell.
The -BCPP| problem consists in constructing a feasible packing of an unlimited number of -BCs of types of maximum density.
[See PDF for image]
Fig. 8.
Example of the regular part in a packing of 2-BCs of two types.
3.1. -BCs of the Same Type
In this case, . In [1], the following statement was proved. If the order of packing of nonincreasing (nondecreasing) bar charts is given, then the greedy algorithm (or its analog packing bar charts from right to left) constructs a packing of minimal length. Let us use this statement. Since the -BCs belong to a single type, all of them are either nondecreasing or nonincreasing. In addition, we can assume that any order is given for packing identical -BCs. Thus, the following assertion holds.
Assertion 1.
If all -BCs are of the same type, then Algorithm constructs a maximum density packing for the -BCPP|1 problem.
3.2. -BCs of Types
Let us consider the case of and then generalize the result. We have an unlimited number of -BCs of two types with bar heights and , respectively. Denote by and the number of -BCs of the first and second types, respectively, that can be 2-combined without violating feasibility, i.e., , . Assume that , otherwise either none of the -BCs can be packed into a strip or we obtain the case considered in Sec. 3.1. Let us denote by ( ) the number of the first bars of the -BCs of the first (second) type in cell . We assign code to each variant of filling cell . The number of feasible combinations and is limited by the value . Since the bar charts consist of two bars, each code corresponds to the value , reflecting the sum of the heights of the bars that fall into the next cell. Any packing can be represented by a sequence of codes until the regular part is found.
[See PDF for image]
Fig. 9.
Example of finding dominant packings for all combinations of filling the second cell.
Definition 8.
The dominant packing for the code is the sequence of codes ending in with the maximum density.
[See PDF for image]
Fig. 10.
Example of finding dominant packings for all combinations of filling the third cell.
In this section, we propose Algorithm for solving the -BCPP|2 is proposed. The operation of the algorithm consists of successively finding the dominant packing for each code of filling the current cell. First, Algorithm considers all possible codes of filling the first cell , , . If the feasibility of the next code is violated in the first or second cell, then the algorithm deletes the code. Then, for each value of , all feasible combinations of filling the second cell are found. Note that the third cell always contains a height that has already appeared in the second cell for some values of and . The dominant packing is selected from the sequences of codes ending in (Fig. 9). If among the dominant packings there is a repetition of the code in the sequence or the last code is , then the corresponding packing with the found regular part is remembered. For the remaining dominant packings, all possible etc. are considered (Fig. 10) until the regular part is found for the next cell in all dominant packings (Fig. 11). Then all the packings in which a regular part was found are compared, and the packing with the maximum density is selected (Fig. 12). In Figs. 9–11, the packings highlighted by the red dashed line contain a regular part (code in the rectangle); the packings highlighted by the blue dashed line are dominant without a regular part.
[See PDF for image]
Fig. 11.
Example of finding dominant packings for all combinations of filling the fourth and fifth cells.
Theorem 4.
Algorithm constructs a maximum-density packing with complexity for the -BCPP|2 problem.
Proof. Each time the algorithm encounters a code repetition or a code in the dominant packing, it remembers the packing with the regular part that has the maximum density for a particular filling code of the current cell. In this way, a set of code sequences is selected that dominate all other possible sequences. This means that the selected set contains the optimal code sequence, which is found after comparing the density of all packings with the regular part found.
During the algorithm’s operation, one dominant packing is searched for each code of filling the current cell. The number of possible codes filling each cell is no more than . For each code, no more than packing variants are considered. Consequently, the complexity of finding all dominant packings for one cell is equal to . The number of iterations is at most , since a repetition of the code in the sequence is guaranteed to occur further on. Thus, the complexity of Algorithm is equal to . The proof of the theorem is complete.
[See PDF for image]
Fig. 12.
Optimal packing with maximum density among all dominant packings with the regular part found.
Remark 1.
Algorithm can be applied to find an exact solution to the -BCPP| problem for any , . The number of feasible combinations of the first -BC bars of types is limited by the number . The complexity of the algorithm when there are -BC types is .
CONCLUSIONS
The problem of packing bar charts consisting of two bars into a strip of minimum length is considered. Improved a priori estimates of accuracy for previously developed approximate algorithms are proposed. The attainability of these estimates is shown. In addition, a special case of the -BCPP problem where the height of both bars of each bar chart does not exceed is studied for the first time. It is proved that Algorithm with complexity constructs a packing for this special case of the problem of length no greater than , where is the minimal packing length. An example of asymptotic attainability of this bound is given.
In addition, the problem of packing an unlimited number of -BCs belonging to one of types is considered for the first time. An algorithm is proposed to construct an optimal packing for this problem the complexity of which is equal to , where is the upper bound on the number of variants of filling one cell with the first bars of -BCs of types that do not violate the feasibility of packing.
ACKNOWLEDGMENTS
The author expresses gratitude to A.I. Erzin for valuable advice and constructive assistance in presenting the results.
This work was supported by ongoing institutional funding. No additional grants to carry out or direct this particular research were obtained.
CONFLICT OF INTEREST
The author of this work declares that he has no conflicts of interest.
Translated by V. Potapchouck
Publisher’s Note. Pleiades Publishing remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. AI tools may have been used in the translation or editing of this article.
REFERENCES
1 A. I. Erzin, R. V. Plotnikov, A. P. Korobkin, G. E. Melidi, and S. A. Nazarenko, “Optimal investment in the development of oil and gas field,” Mathematical Optimization Theory and Operations Research. Rev. Sel. Pap. 19th Int. Conf. MOTOR 2020 (Novosibirsk, Russia, July 6–10, 2020), vol. 1275 of Commun. Comput. Inf. Sci (Springer, Cham, 2020), pp. 336–349.
2 Erzin, A.I.; Melidi, G.E.; Nazarenko, S.A.; lotnikov, R.V. Two-bar charts packing problem. Optim. Lett.; 2021; 15,
3 Erzin, A.I.; Melidi, G.E.; Nazarenko, S.A.; Plotnikov, R.V. A -approximation for big two-bar charts packing. J. Combin. Optim.; 2021; 42,
4 A. I. Erzin, G. E. Melidi, S. A. Nazarenko, and R. V. Plotnikov, “A posteriori analysis of the algorithms for two-bar charts packing problem,” Advances in Optimization and Applications. Rev. Sel. Pap. 12th Int. Conf. OPTIMA 2021 (Petrovac, Montenegro, September 27–October 1, 2021), vol. 1514 of Commun. Comput. Inf. Sci. (Springer, Cham, 2021), pp. 201–216.
5 Erzin, A.I.; Kononov, A.V.; Melidi, G.E.; Nazarenko, S.A. A approximation for big two-bar charts packing problem. J. Math. Sci.; 2023; 269,
6 A. I. Erzin, Kononov A. V., S. A. Nazarenko, and K. I. Sharankhaev, “An -time algorithm for linearly ordered packing of 2-bar charts into bins,” Mathematical Optimization Theory and Operations Research. Rev. Sel. Pap. 22th Int. Conf. MOTOR 2023 (Yekaterinburg, Russia, July 2–8, 2023), vol. 1881 of Commun. Comput. Inf. Sci. (Springer, Cham, 2023), pp. 122–133.
7 Barkel, M.; Delorme, M. Arcflow formulations and constraint generation frameworks for the two bar charts packing problem. INFORMS J. Comput.; 2023; 35,
8 Garey, M.R.; Johnson, D.S. Computers and Intractability. A Guide to the Theory of NP-Completeness; 1979; San Francisco, Freeman:
9 Vazirani, V.V. Approximation Algorithms; 2001; Heidelberg, Springer:
10 Simchi-Levi, D. New worst-case results for the bin-packing problem. Nav. Res. Logist.; 1994; 41,
11 G. Dósa, “The tight bound of first fit decreasing bin-packing algorithm is ,” Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. Rev. Sel. Pap. 1st Int. Symp. (Hangzhou, China, April 7–9, 2007), vol. 4614 of Lect. Notes Comput. Sci. (Springer, Heidelberg, 2007), pp. 1–11.
12 Johnson, D.S.; Garey, M.R. A theorem for bin packing. J. Complex.; 1985; 1,
13 Yue, M.; Zhang, L. A simple proof of the inequality for the MFFD bin-packing algorithm. Acta Math. Appl. Sin.; 1995; 11,
14 Fernandez de la Vega, W.; Lueker, G.S. Bin packing can be solved within in linear time. Combinatorica; 1981; 1, pp. 349-355.647985
15 N. Karmarkar and R. M. Karp, “An efficient approximation scheme for the one dimensional bin-packing problem,” 23rd Annu. Symp. Found. Comput. Sci. (Chicago, USA, November 3–5, 1982), (IEEE, Piscataway, 1982), pp. 312–320.
16 R. Hoberg and T. Rothvos, “A logarithmic additive integrality gap for bin packing,” Proc. 28th Annu. ACM-SIAM Symp. Discrete Algorithms (Barcelona, Spain, January 16–19, 2017), (SIAM, Philadelphia, PA, 2017), pp. 2616–2625.
17 Kellerer, H.; Kotov, V. An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing. Oper. Res. Lett.; 2003; 31, pp. 35-41.1946732
18 Christensen, H.I.; Khanb, A.; Pokutta, S.; Tetali, P. Approximation and online algorithms for multidimensional bin packing: A survey. Comput. Sci. Rev.; 2017; 24, pp. 63-79.3655768
19 N. Bansal, M. EliáŢ, and A. Khan, “Improved approximation for vector bin packing,” Proc. 27th Annu. ACM-SIAM Symp. Discrete Algorithms (Arlington, VA, USA, January 10–12, 2016), (SIAM, Philadelphia, PA, 2016), pp. 1561–1579.
20 Woeginger, G.J. There is no asymptotic PTAS for two-dimensional vector packing. Inf. Process. Lett.; 1997; 64,
21 Brucker, P.; Knust, S. Complex Scheduling; 2006; Heidelberg, Springer:
22 Goncharov, E.N. A greedy heuristic approach for the resource-constrained project scheduling problem. Stud. Inf. Univ.; 2011; 9,
23 Goncharov, E.N. Stochastic greedy algorithm for the problem of scheduling with resource constraints. Discretn. Anal. Issled. Oper.; 2014; 21,
24 Hartmann, S. A self-adapting genetic algorithm for project scheduling under resource constraints. Nav. Res. Logist.; 2002; 49, pp. 433-448.1918279
25 Kolisch, R.; Hartmann, S. Experimental investigation of heuristics for resource-constrained project scheduling: An update. Eur. J. Oper. Res.; 2006; 174, pp. 23-37.
26 Erzin, A.I.; Sharankhaev, K.I. Three-bar charts packing problem. Commun. Comput. Inf. Sci.; 2023; 1739, pp. 61-75.4590676
© Pleiades Publishing, Ltd. 2024.