A Look-Forward Heuristic for Packing Spheres into a Three-Dimensional Bin

• Autorzy: Hakim Akeb
• Języki publikacji: EN

Abstrakty

EN

In this paper, a look-forward heuristic is proposed in order to solve the problem of packing spheres into a three-dimensional bin of fixed height and depth but variable length. The objective is to pack all the spheres into the bin of minimum length. This problem is also known under the name of the three-dimensional strip packing problem. The computational investigation, conducted on a set of benchmark instances taken from the literature, shows that the method is effective since it improves most of the best known results.(original abstract)

Słowa kluczowe

EN

Algorithms; Scientific research; Heuristics methods

PL

Algorytmy; Badania naukowe; Metody heurystyczne

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 397--404

Twórcy

autor

Hakim Akeb

• ISC Paris Business School

Bibliografia

• Akeb H., Hifi M., and Lazure D., "An Improved Algorithm for the Strip Packing Problem," Proceedings of the Federated Conference on Computer Science and Information Systems, FedCSIS 2012, Wroclaw, Poland, pp. 357-364. ISBN 978-83-60810-51-4. https://fedcsis.org/proceedings/2012/pliks/93.pdf
• Birgin E. G. and Sobral F. N. C., "Minimizing the object dimensions in circle and sphere packing problems," Compt. Oper. Res., vol. 35, 2008, pp. 2357-2375. http://dx.doi.org/10.1016/j.cor.2006.11.002
• Gavriliouk E. O., "Unequal sphere packing problem in the context of stereotactic radiosurgery," Shaker Verlag, 2007, 96 pages.
• Huang W. Q., Li Y., Akeb H., and Li C. M., Y., "Greedy algorithms for packing unequal circles into a rectangular container," J. Oper. Res. Soc., vol. 56, 2005, pp. 539-548. http://dx.doi.org/10.1057/palgrave.jors.2601836
• Kubach T., Bortfeldt A., Tilli T., and Gehring H., "Greedy algorithms for packing unequal sphere into a cuboidal strip or a cuboid," Asia Pac. J Oper. Res., vol. 28, 2011, pp. 739-753. http://dx.doi.org/10.1142/S0217595911003326
• Lenstra L. K. and Rinnooy Kan A.H.G., "Complexity of packing, covering, and partitioning problems," In Schrijver A (ed.), Packing and Covering in Combinatorics. Amsterdam: Mathematisch Centrum, 1979, pp. 275-291.
• Lin M., Chen R., and Liu J. s., "Lookahead Strategies for Sequential Monte Carlo," Statist. Sci., vol 28, 2013, pp. 69-94. http://dx.doi.org/10.1214/12-STS401
• Li Y. and Ji W., "Stability and convergence analysis of a dynamicsbased collective method for random sphere packing," J. Comput. Phys., vol. 250, 2013, pp. 373-387. http://dx.doi.org/10.1016/j.jcp.2013.05.023
• M'Hallah R., Alkandari A., and Mladenovi´c N., "Packing unit spheres into the smallest sphere using VNS and NLP," Compt. Oper. Res., vol. 40, 2013, pp. 603-615. http://dx.doi.org/10.1016/j.cor.2012.08.019
• M'Hallah R. and Alkandari A., "Packing unit spheres into a cube using VNS," Electron. Notes Discrete Math., vol. 39, 2012, pp. 201-208. http: //dx.doi.org/10.1016/j.endm.2012.10.027
• Soontrapa K. and Chen Y., "Mono-sized sphere packing algorithm development using optimized Monte Carlo technique," Adv. Powder Technol., vol. 24(6), 2013, pp. 955-961. http://dx.doi.org/10.1016/j.apt.2013.01.007
• Stoyan Y., Yaskow G., and Scheithauer G., "Packing of various radii solid spheres into a parallelepiped," Cent. Europ. J. Oper. Re., vol. 11, 2003, pp. 389-407.
• Sutou A. and Dai Y., "Global optimization approach to unequal sphere packing problems in 3D," J. Optimiz. Theory App., vol. 114, 2002, pp. 671-694. http://dx.doi.org/10.1023/A:1016083231326
• Visscher W. and Bolsterli M., "Random packing of equal and unequal spheres in two and three dimensions," Nature, vol. 239, 1972, pp. 504-507. http://dx.doi.org/10.1038/239504a0
• Wang J., "Packing of unequal spheres and automated radiosurgical treatment planning," J. Comb. Optim., vol. 3, 1999, pp. 453-463. http://dx.doi.org/10.1023/A:1009831621621