A Parallel Genetic Algorithm for Three Dimensional Bin Packing with Heterogeneous Bins
 |
International Journal of Computer Trends and Technology (IJCTT) |  |
| © 2014 by IJCTT Journal | ||
| Volume-17 Number-1 |
||
| Year of Publication : 2014 | ||
| Authors : Drona Pratap Chandu | ||
| DOI : 10.14445/22312803/IJCTT-V17P108 |
Drona Pratap Chandu. "A Parallel Genetic Algorithm for Three Dimensional Bin Packing with Heterogeneous Bins". International Journal of Computer Trends and Technology (IJCTT) V17(1):33-38, Nov 2014. ISSN:2231-2803. www.ijcttjournal.org. Published by Seventh Sense Research Group.
Abstract -
This paper presents a parallel genetic algorithm for three dimensional bin packing with heterogeneous bins using Hadoop Map-Reduce framework. The most common three dimensional bin packing problem which packs given set of boxes into minimum number of equal sized bins is proven to be NP Hard. The variation of three dimensional bin packing problem that allows heterogeneous bin sizes and rotation of boxes is computationally more harder than common three dimensional bin packing problem. The proposed Map-Reduce implementation helps to run the genetic algorithm for three dimensional bin packing with heterogeneous bins on multiple machines parallely and computes the solution in relatively short time.
References
[1] Xueping Li, Zhaoxia Zhao, Kaike Zhang ,“A genetic algorithm for the three-dimensional bin packing problem with heterogeneous bins” in proceedings of the 2014 Industrial and Systems Engineering Research Conference.
[2] AJeffrey Dean and Sanjay Ghemawat, “Map-Reduce: Simplified Data Processing on Large Clusters” in Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation 2004, 137-149.
[3] http://hadoop.apache.org/
[4] Chen, C. S., Lee, S. M., and Shen, Q. S., “An analytical model for the contianer loading problem”, European Journal of Operational Research,1995, 80(1):68–76.
[5] Den Boef, E., Korst, J., Martello, S., Pisinger, D., and Vigo, D.,“Erratum to The three-dimensional bin packing problem: Robot-packable and orthogonal variants of packing problems”, Operations Research, 2005,53(4):735–736.
[6] Martello, S., Pisinger, D., Vigo, D., Den Boef, E., and Korst, J., “Algorithm 864: General and robot-packable variants of the three-dimensional bin packing problem”, ACM Transactions on Mathematical Software,2007, 33(1):1–12
[7] George, J. A. and Robinson, D. F. , “A heuristic for packing boxes into a container. Computers and Operations Research”, 1980,7(3):147–156.
[8] Bischoff, E. E., Janetz, F., and Ratcliff, M. S. W. , “Loading pallets with non-identical items”, European Journal of Operational Research, 1995, 84:681–692.
[9] Pisinger, D., “Heuristics for the container loading problem. European Journalof Operational Research”, 2002,141:382–392.
[10] Baltacio glu, E., Moore, J. T., and Hill Jr., R. R., “The distributor’s threedimensional pallet-packing problem: a human intelligence-based heuristic approach”, International Journal of Operational Research, 2006,1(3):249–266.
[11] Faroe, O., Pisinger, D., and Zachariasen, M., “Guided local search for three-dimensional bin-packing problem” INFORMS Journal on Computing, 2003,15(3):267–283.
[12] Gehring, H. and Bortfeldt, A., “A genetic algorithm for solving the container loading problem” International Transactions in Operational Research, 1997, 4:401–418.
[13] Hopper, E. and Turton, B. C. H., “An empirical investigation of metaheuristics and heuristic algorithms for a 2D packing problem”, European Journal of Operations Research, 2001, 128:34–57.
[14] Zhang, D.-F., Wei, L.-J., Chen, Q.-S., and Chen, H.-W., “A combinatorial heuristic algorithm for the three-dimensional packing problem (in Chinese with English abstract)”, Journal of Software, 2007, 18(9):2083–2089.
[15] Crainic, T. G., Perboli, G., and Tadei, R., Extreme point-based heuristics for three-dimensional bin packing. INFORMS Journal on Computing, 20(3):368–384.abstract). Journal of Software, 2008, 18(9):2083–2089.
[16] Lodi, A., Martello, S., and Vigo, D., Heuristic algorithms for the threedimensional bin packing problem. European Journal of Operational Research, 2002,141:410–420.
Keywords
Genetic algorithm, three dimensional bin packing, map reduce, hadoop.