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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems, 2010, 27 (4) : 1447-1472. doi: 10.3934/dcds.2010.27.1447
[16]

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
[17]

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 & Continuous Dynamical Systems - S, 2021, 14 (4) : 1233-1244. doi: 10.3934/dcdss.2020356
[18]

Chuanxin Zhao, Lin Jiang, Kok Lay Teo. A hybrid chaos firefly algorithm for three-dimensional irregular packing problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 409-429. doi: 10.3934/jimo.2018160
[19]

Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057
[20]

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 & Continuous Dynamical Systems - S, 2019, 12 (6) : 1547-1588. doi: 10.3934/dcdss.2019107

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences