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

A-shaped bin packing: Worst case analysis via simulation

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.
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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Dieter Bothe, Jan Prüss. Modeling and analysis of reactive multi-component two-phase flows with mass transfer and phase transition the isothermal incompressible case. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 673-696. doi: 10.3934/dcdss.2017034

[18]

Mao Chen, Xiangyang Tang, Zhizhong Zeng, Sanya Liu. An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle. Journal of Industrial & Management Optimization, 2020, 16 (1) : 495-510. doi: 10.3934/jimo.2018164

[19]

Cristina Anton, Jian Deng, Yau Shu Wong, Yile Zhang, Weiping Zhang, Stephan Gabos, Dorothy Yu Huang, Can Jin. Modeling and simulation for toxicity assessment. Mathematical Biosciences & Engineering, 2017, 14 (3) : 581-606. doi: 10.3934/mbe.2017034

[20]

Gong Chen, Peter J. Olver. Numerical simulation of nonlinear dispersive quantization. Discrete & Continuous Dynamical Systems - A, 2014, 34 (3) : 991-1008. doi: 10.3934/dcds.2014.34.991

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]