Bin packing with directed stackability conflicts.

*(English)*Zbl 1334.68092Summary: The Bin Packing problem is a well-known and highly investigated problem in the computer science: we have \(n\) items given with their sizes, and we want to assign them to unit capacity bins such, that we use the minimum number of bins.

In this paper, some generalizations of this problem are considered, where there are some additional stackability constraints defining that certain items can or cannot be packed on each other. The corresponding model in the literature is the Bin Packing Problem with Conflicts (BPPC), where this additional constraint is defined by an undirected conflict graph having edges between items that cannot be assigned to the same bin. However, we show some practical cases, where this conflict is directed, meaning that the items can be assigned to the same bin, but only in a certain order. Two new models are introduced for this problem: Bin Packing Problem with Hanoi Conflicts (BPPHC) and Bin Packing Problem with Directed Conflicts (BPPDC). In this work, the connection of the three conflict models is examined in detail.

We have investigated the complexity of the new models, mainly the BPPHC model, in the special case where each item have the same size. We also considered two cases depending on whether re-ordering the items is allowed or not.

We show that for the online version of the BPPHC model with unit size items, every Any-Fit algorithm gives not better than \(\frac32\)-competitive, when it is forbidden for the optimum to re-order the items, even if only 2 stackability classes, called Hanoi classes, are applied. This lower bound is generalized for arbitrary number of Hanoi classes. However, we also prove, that asymptotically the First-Fit algorithm is 1-competitive for this case.

Finally, we introduce an algorithm for the offline version of the BPPHC model with unit size items, which has polynomial time complexity, if the number of the Hanoi classes and the capacity of the bins are constant.

In this paper, some generalizations of this problem are considered, where there are some additional stackability constraints defining that certain items can or cannot be packed on each other. The corresponding model in the literature is the Bin Packing Problem with Conflicts (BPPC), where this additional constraint is defined by an undirected conflict graph having edges between items that cannot be assigned to the same bin. However, we show some practical cases, where this conflict is directed, meaning that the items can be assigned to the same bin, but only in a certain order. Two new models are introduced for this problem: Bin Packing Problem with Hanoi Conflicts (BPPHC) and Bin Packing Problem with Directed Conflicts (BPPDC). In this work, the connection of the three conflict models is examined in detail.

We have investigated the complexity of the new models, mainly the BPPHC model, in the special case where each item have the same size. We also considered two cases depending on whether re-ordering the items is allowed or not.

We show that for the online version of the BPPHC model with unit size items, every Any-Fit algorithm gives not better than \(\frac32\)-competitive, when it is forbidden for the optimum to re-order the items, even if only 2 stackability classes, called Hanoi classes, are applied. This lower bound is generalized for arbitrary number of Hanoi classes. However, we also prove, that asymptotically the First-Fit algorithm is 1-competitive for this case.

Finally, we introduce an algorithm for the offline version of the BPPHC model with unit size items, which has polynomial time complexity, if the number of the Hanoi classes and the capacity of the bins are constant.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68R05 | Combinatorics in computer science |

90C27 | Combinatorial optimization |

##### Keywords:

bin packing problem; conflicts; directed conflicts; Hanoi conflicts; unit-size items; dynamic programming
PDF
BibTeX
XML
Cite

\textit{A. Bódis}, Acta Univ. Sapientiae, Inform. 7, No. 1, 31--57 (2015; Zbl 1334.68092)

Full Text:
DOI

##### References:

[1] | J. Balogh, J. Békési, Gy. Dósa, L. Epstein, H. Kellerer, Zs. Tuza, Online results for black and white bin packing, Theory Comput. Syst., 56, 1 (2015) 137-155. ⇒34 |

[2] | N. Bansal, Z. Liu, A. Sankar, Bin-packing with fragile objects and frequency allocation in cellular networks, Wireless Networks, 15, 6 (2009) 821-830. ⇒33 |

[3] | M. Böhm, J. Sgall, P. Vesely, Online colored bin packing, arXiv:1404.5548 [cs.DS] (2014) ⇒34 |

[4] | F. Clautiaux, M. Dell’Amico, M. Iori, A. Khanafer, Lower and upper bounds for the Bin Packing Problem with Fragile Objects, Discrete Appl. Math., 163, 1 (2014) 73-86. ⇒33 · Zbl 1303.90087 |

[5] | 5] Jr., E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, M. Yannakakis, Bin packing with discrete item sizes part I: Perfect packing theorems and the average case behavior of optimal packings, SIAM J. Discrete Math., 13, 3 (2000) 384-402 ⇒45 · Zbl 0951.68192 |

[6] | Jr., E. G. Coffman, D. S. Johnson, L. A. McGeoch, R. R. Weber, Bin packing with discrete item sizes part II: tight bounds on First Fit, Random Structures Algorithms, 10, 1-2 (1997) 69-101. ⇒45 |

[7] | Gy. Dósa, L. Epstein, Colorful bin packing, Algorithm Theory - SWAT 2014, Lecture Notes in Comput. Sci., 8503 (2014) 170-181. ⇒34 |

[8] | Gy. Dósa, J. Sgall, First Fit bin packing: a tight analysis, 30th International Symposium on Theoretical Aspects of Computer Science: STACS, Dagstuhl, Germany, 2013, pp. 538-549. ⇒47 · Zbl 1354.68118 |

[9] | Gy. Dósa, Zs. Tuza, D. Ye, Bin packing with ’Largest In Bottom’ constraint: tighter bounds and generalizations, J. Comb. Optim., 26, 3 (2013) 416-436. ⇒34 · Zbl 1282.90149 |

[10] | L. Epstein, On online bin packing with LIB Constraints, Naval Res. Logist., 56, 8 (2009) 780-786. ⇒34 · Zbl 1180.90267 |

[11] | L. Epstein, Cs. Imreh, A. Levin, Class constrained bin packing revisited, Theoret. Comput. Sci., 411, 34-36 (2010) 3073-3089. ⇒33 · Zbl 1196.68311 |

[12] | L. Epstein, A. Levin, On bin packing with conflicts, Approximation and Online Algorithms, Lecture Notes in Comput. Sci.4368 (2007) 160-731. ⇒34 |

[13] | K. Jansen, An approximation scheme for bin packing with conflicts, J. Comb. Optim., 3, 4 (1999) 363-377. ⇒34 · Zbl 0971.90072 |

[14] | K. Jansen, S. Öhring, Approximation algorithms for time constrained scheduling, Inform. and Comput., 132, 2 (1997) 85-108. ⇒34 · Zbl 0866.68012 |

[15] | A. Khanafer, F. Clautiaux, E. G. Talbi, Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts, Computers and Operations Research, 39, 1 (2012) 54-63. ⇒34 · Zbl 1251.90282 |

[16] | P. Manyem, Uniform sized bin packing and covering: Online version, Topics in industrial mathematics, Springer US, 2000. ⇒34 |

[17] | P. Manyem, R. L. Salt, M. S. Visser, Approximation lower bounds in online LIB bin packing and covering, J. Autom. Lang. Comb., 8, 4 (2003) 663-674 ⇒34 · Zbl 1088.68836 |

[18] | S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley and Sons, 1990. ⇒36 · Zbl 0708.68002 |

[19] | B. McCloskey, A. Shankar, Approaches to bin packing with clique-graph conflicts, EECS Department, University of California, Berkeley (2005) ⇒34 |

[20] | R. Sadykov, F. Vanderbeck, Bin packing with conflicts: a generic branch-and-price algorithm, INFORMS J. Comput., 25, 2 (2013) 244-255. ⇒34 |

[21] | H. Shachnai, T. Tamir, Tight bounds for online class-constrained packing, Theoret. Comput. Sci., 321, 1 (2004) 103-123. ⇒33, 45 · Zbl 1067.90144 |

[22] | H. Shachnai, T. Tamir, Polynomial time approximation schemes for class-constrained packing problems, Journal of Scheduling, 4, 6 (2001) 313-338. ⇒33 · Zbl 1028.90048 |

[23] | H. Shachnai, T. Tamir, On two class-constrained versions of the multiple knapsack problem, Algorithmica, 29, 3 (2001) 442-467. ⇒33 · Zbl 0969.68183 |

[24] | K. Thulasiraman, M. N. S. Swamy, 5.7 Acyclic Directed Graphs, Graphs: Theory and Algorithms, John Wiley and Sons, 1992. 118. ⇒43 · Zbl 0766.05001 |

[25] | J. D. Ullman, The performance of a memory allocation algorithm., Princeton University, Department of Electrical Engineering, Computer Science Laboratory, (1971) ⇒47 |

[26] | E. C. Xavier, F. K. Miyazawa, The class constrained bin packing problem with applications to video-on-demand, Theoret. Comput. Sci., 393, 1-3 (2008) 240-259. ⇒33 · Zbl 1135.68636 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.