具有稳定性约束的一维箱子覆盖问题
One-Dimensional Bin-Covering Problem with Stability Constraints
DOI: 10.12677/AAM.2022.111051, PDF,    科研立项经费支持
作者: 吴彬彬, 苗睿卿：云南民族大学数学与计算机科学学院，云南 昆明；张同全：云南民族大学预科教育学院，云南 昆明
关键词: 箱子覆盖问题；NP-完备性；稳定性约束；弱渐进近似算法；Bin-Covering Problem； NP-Completeness； Stability Constraints； Weakly Asymptotic Approximation Algorithm
摘要: 给定一个物品序列和若干箱子，如何合理地放置物品以使得最多的箱子被覆盖就称为箱子覆盖问题。作为一维箱子覆盖问题的推广，提出了具有稳定性约束的一维箱子覆盖问题，即要求同一箱子中小的物品置于大的物品上方。分析了问题的NP-完备性，给出了一种弱渐进近似算法，并分析了算法的时间复杂度。
Abstract: The bin-covering problem is to reasonably place the items under a given sequence of items and a number of bins, so that most bins are covered. For promoting the one-dimensional bin-covering problem, the paper proposes the one-dimensional bin-covering problem with stability constraints, which requires the small items in the same bin to be placed above the large items. The paper analyzes the NP-completeness of the problem and provides a weakly asymptotic approximation algorithm for the problem by analyzing the time complexity of the algorithm.
文章引用：吴彬彬, 苗睿卿, 张同全. 具有稳定性约束的一维箱子覆盖问题[J]. 应用数学进展, 2022, 11(1): 434-441. https://doi.org/10.12677/AAM.2022.111051

参考文献

[1] Assmann, S.F., Johnson, D.S., Kleitman, D.J. and Leung, J.Y.-T. (1984) On a Dual Version of the One-Dimensional Bin Packing Problem. Journal of Algorithms, 5, 502-525. [Google Scholar] [CrossRef] 
[2] Han, S., Hong, D. and Leung, J.Y.-T. (1996) Leung. Probabilistic Analysis of a Bin Covering Algorithm. Operations Research Letters, 18, 193-199. [Google Scholar] [CrossRef] 
[3] Gehring, H., Menschner, K. and Meyer, M. (1990) A Computer-Based Heuristic for Packing Pooled Shipment Containers. European Journal of Operational Research, 44, 277-289. [Google Scholar] [CrossRef] 
[4] Maruyama, K., Chang, S.K. and Tang, D.T. (1977) A General Packing Algorithm for Multidimensional Resource Requirements. International Journal of Computer & Information Sciences, 6, 131-149. [Google Scholar] [CrossRef] 
[5] Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., et al. (2000) Multiprocessor Scheduling with Rejection. SIAM Journal on Discrete Mathematics, 13, 64-78. [Google Scholar] [CrossRef] 
[6] Gnanavelbabu, A., Caldeira Rylan, H. and Vaidyanathan, T. (2021) A Simulation-Based Modified Backtracking Search Algorithm for Multi-Objective Stochastic Flexible Job Shop Scheduling Problem with Worker Flexibility. Applied Soft Computing Journal, 113, Article ID: 107960. [Google Scholar] [CrossRef] 
[7] 程会兵. 考虑时间窗约束的装箱问题研究[[D]: [硕士学位论文]. 南昌: 江西财经大学, 2019.
[8] Woeginger, G.J. and Zhang, G. (1999) Optimal On-Line Algorithms for Variable-Sized Bin Covering. Operations Research Letters, 25, 47-50. [Google Scholar] [CrossRef] 
[9] 孙春玲, 李建平. 最小基数箱子覆盖问题及其启发式算法[J]. 云南大学学报(自然科学版), 2004(S1): 8-11.
[10] 唐浩龙. 一维捆绑式箱子覆盖问题[D]: [硕士学位论文]. 昆明: 云南大学, 2016.

为你推荐