Abstract
The bin packing problem with divisible item sizes and rejection penalties (the BP–DR problem, for short) is defined as follows. Given a lot of bins with same capacity limitation L and a set \(X=\{x_{1},\ldots ,x_{n}\}\) of items with a size function \(s: X\rightarrow Z^{+}\) and a penalty function \(p:X\rightarrow R^{+}\), where the item sizes are divisible, i.e., either \(s(x_{i})|s(x_{j})\) or \(s(x_{j})|s(x_{i})\) for any two items \(x_{i}\) and \(x_{j}\) with \(1\le i < j\le n\), each of these n items must be either put into a bin under the constraint that the summation of sizes of items in that bin does not exceed L, or rejected with its penalty that we must pay for. No item can be spread into more than one bin. We consider the BP–DR problem and its important variant. (1) The BP–DR problem is asked to find a subset of items such that the items in that subset can be put in some bins to satisfy the constraint mentioned-above, the objective is to minimize the number of bins used plus the summation of penalties paid for the rejected items, and (2) Given a penalty budget \(B\in R^{+}\), the bin packing problem with divisible item sizes and bounded rejection penalties (the BP–DBR problem, for short) is asked to find a subset of items such that the items in that subset can be put in some bins to satisfy the constraint mentioned-above and that the summation of penalties paid for the rejected items does not exceed B, the objective is to minimize the number of bins used. In this paper, we design two exact combinatorial algorithms to solve the BP–DR problem and the BP–DBR problem, respectively.
Similar content being viewed by others
References
Coffman, E.G., Garey, M.R., Johnson, D.S.: Bin packing with divisible item sizes. J. Complex. 3, 406–428 (1987)
Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms. PWS Publishing Company, Boston (1997)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)
Csirik, J., Woeginger, G.J.: On-line packing and covering problems. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms: the State of the Art. Lecture Notes in Computer Science, pp. 147–177. Springer, New York (1998)
Detti, P.: A polynomial algorithm for the multiple knapsack problem with divisible item sizes. Inf. Process. Lett. 109(11), 582–584 (2009)
Dósa, G., He, Y.: Bin packing problems with rejection penalties and their dual problems. Inf. Comput. 204(5), 795–815 (2006)
Epstein, L.: Bin packing with rejection revisited. Algorithmica 56(4), 505–528 (2010)
Epstein, L., Levin, A.: AFPTAS results for common variants of bin packing: a new method for handling the small items. SIAM J. Optim. 20(6), 3121–3145 (2010)
Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+\(\varepsilon \) in linear time. Combinatorica 1(4), 349–355 (1981)
Johnson, D.S.: Near-Optimal Bin Packing Algorithms. Ph.D. Thesis, MIT, Department of Mathematics, Cambridge (1973)
Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 312–320. IEEE, New York (1982)
Knuth, D.E.: The Art of Computer Programming: Fundamental Algorithms, vol. 1, 2nd edn. Addison-Wesley, Reading, MA (1973)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 5th edn. Springer, Berlin (2012)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
Simchi-Levi, D.: New worst-case results for the bin packing problem. Nav. Res. Logist. 41, 579–585 (1994)
Ullman, J.D.: The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ (1971)
Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2011)
Zhang, G., Cai, X., Wong, C.K.: Linear time approximation algorithms for bin packing. Oper. Res. Lett. 26, 217–222 (2000)
Acknowledgements
The authors are all grateful to an associate editor and the reviewers for their insightful comments and for their suggested changes that improve the presentation greatly.
This paper is supported by the National Natural Science Foundation of China [Nos. 11861075, 12101593], Project for Innovation Team (Cultivation) of Yunnan Province [No.202005AE160006], Key Project of Yunnan Provincial Science and Technology Department and Yunnan University [No.2018FY001014] and Program for Innovative Research Team (in Science and Technology) in Universities of Yunnan Province [No.C176240111009]. Jianping Li is also supported by Project of Yunling Scholars Training of Yunnan Province. J.R. Lichen is also supported by Project of Doctorial Fellow Award of Yunnan Province [No.2018010514]. Pengxiang Pan is also supported by Project of Yunnan Provincial Department of Education Science Research Fund [No.2020Y0040].
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Li, J., Pan, P., Cai, L. et al. Bin packing with divisible item sizes and rejection penalties. Optim Lett 16, 1587–1597 (2022). https://doi.org/10.1007/s11590-021-01803-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-021-01803-3