American Institute of Mathematical Sciences

Advanced
July  2005, 1(3): 323-335. doi: 10.3934/jimo.2005.1.323

A-shaped bin packing: Worst case analysis via simulation

Wenxun Xing 1, and  Feng Chen 2,

1. 

Department of Mathematical Sciences, Tsinghua University, Beijing, China
2. 

Department of Mathematics, Purdue University, 150 N. University Street, West Lafayette, IN 47907-2067, United States

Received  August 2004 Revised  January 2005 Published  July 2005

An A-shaped bin packing problem, where the items are cylinders and they must be packed into an A-shaped tower in each bin is considered in this paper. It is a variant of the classical one dimensional bin packing problem. For the off-line version of the problem, it is the same to the classical bin packing problem. For the on-line version of the problem, directly extended and radius-classified heuristics from the classical bin packing are analyzed and compared with the worst case analysis and simulation methods. The worst case analysis shows that the asymptotic competitive ratios of heuristics extended from the next fit, the worst fit, the best fit, the almost worst fit, the harmonics are all infinity except of the first fit with asymptotic competitive ratio 2. The radius-classified heuristics perform as well as in classical bin packing in view of the worst case analysis. Simulation results show that the best fit is the best among the directly extended heuristics and give the equilibrium point of choosing directly extended or radius-classified heuristics for an instance.
Keywords: simulation., worst case analysis, packing.
Mathematics Subject Classification: 90B05, 90B0.
Citation: Wenxun Xing, Feng Chen. A-shaped bin packing: Worst case analysis via simulation. Journal of Industrial and Management Optimization, 2005, 1 (3) : 323-335. doi: 10.3934/jimo.2005.1.323
[1]

Ruchika Sehgal, Aparna Mehra. Worst-case analysis of Gini mean difference safety measure. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1613-1637. doi: 10.3934/jimo.2020037
[2]

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial and Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651
[3]

Ying Ji, Shaojian Qu, Yeming Dai. A new approach for worst-case regret portfolio optimization problem. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 761-770. doi: 10.3934/dcdss.2019050
[4]

Yuyuan Ouyang, Trevor Squires. Some worst-case datasets of deterministic first-order methods for solving binary logistic regression. Inverse Problems and Imaging, 2021, 15 (1) : 63-77. doi: 10.3934/ipi.2020047
[5]

Ana I. Muñoz, José Ignacio Tello. Mathematical analysis and numerical simulation of a model of morphogenesis. Mathematical Biosciences & Engineering, 2011, 8 (4) : 1035-1059. doi: 10.3934/mbe.2011.8.1035
[6]

Sergio Amat, Pablo Pedregal. On a variational approach for the analysis and numerical simulation of ODEs. Discrete and Continuous Dynamical Systems, 2013, 33 (4) : 1275-1291. doi: 10.3934/dcds.2013.33.1275
[7]

Xiaoli Yang, Jin Liang, Bei Hu. Minimization of carbon abatement cost: Modeling, analysis and simulation. Discrete and Continuous Dynamical Systems - B, 2017, 22 (7) : 2939-2969. doi: 10.3934/dcdsb.2017158
[8]

Michele L. Joyner, Chelsea R. Ross, Colton Watts, Thomas C. Jones. A stochastic simulation model for Anelosimus studiosus during prey capture: A case study for determination of optimal spacing. Mathematical Biosciences & Engineering, 2014, 11 (6) : 1411-1429. doi: 10.3934/mbe.2014.11.1411
[9]

Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335
[10]

Qiaolin He. Numerical simulation and self-similar analysis of singular solutions of Prandtl equations. Discrete and Continuous Dynamical Systems - B, 2010, 13 (1) : 101-116. doi: 10.3934/dcdsb.2010.13.101
[11]

Rolf Rannacher. A short course on numerical simulation of viscous flow: Discretization, optimization and stability analysis. Discrete and Continuous Dynamical Systems - S, 2012, 5 (6) : 1147-1194. doi: 10.3934/dcdss.2012.5.1147
[12]

Maciek D. Korzec, Hao Wu. Analysis and simulation for an isotropic phase-field model describing grain growth. Discrete and Continuous Dynamical Systems - B, 2014, 19 (7) : 2227-2246. doi: 10.3934/dcdsb.2014.19.2227
[13]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[14]

Leonid V. Bogachev, Gregory Derfel, Stanislav A. Molchanov. Analysis of the archetypal functional equation in the non-critical case. Conference Publications, 2015, 2015 (special) : 132-141. doi: 10.3934/proc.2015.0132
[15]

Alexandre Caboussat, Roland Glowinski. Numerical solution of a variational problem arising in stress analysis: The vector case. Discrete and Continuous Dynamical Systems, 2010, 27 (4) : 1447-1472. doi: 10.3934/dcds.2010.27.1447
[16]

Ankhbayar Chuluunbaatar, Burmaa Galaa, Enkhbat Rentsen. Application of sphere packing theory in financial management. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022092
[17]

Blessing O. Emerenini, Stefanie Sonner, Hermann J. Eberl. Mathematical analysis of a quorum sensing induced biofilm dispersal model and numerical simulation of hollowing effects. Mathematical Biosciences & Engineering, 2017, 14 (3) : 625-653. doi: 10.3934/mbe.2017036
[18]

C. Burgos, J.-C. Cortés, L. Shaikhet, R.-J. Villanueva. A delayed nonlinear stochastic model for cocaine consumption: Stability analysis and simulation using real data. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1233-1244. doi: 10.3934/dcdss.2020356
[19]

Patrick Ballard, Bernadette Miara. Formal asymptotic analysis of elastic beams and thin-walled beams: A derivation of the Vlassov equations and their generalization to the anisotropic heterogeneous case. Discrete and Continuous Dynamical Systems - S, 2019, 12 (6) : 1547-1588. doi: 10.3934/dcdss.2019107
[20]

Xue Qiao, Zheng Wang, Haoxun Chen. Joint optimal pricing and inventory management policy and its sensitivity analysis for perishable products: Lost sale case. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2533-2552. doi: 10.3934/jimo.2021079

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (109)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy