Optimizing large scale bin packing problem with hybrid harmony search algorithm

Adamuthe, A.; Nitave, T.

doi:10.5267/j.ijiec.2020.11.002

Abstract: Bin packing problem (BPP) is a combinatorial optimization problem with a wide range of applications in fields such as financial budgeting, load balancing, project management, supply chain management. Harmony search algorithm (HSA) is widely used for various real-world and engineering problems due to its simplicity and efficient problem solving capability. Literature shows that basic HSA needs improvement in search capability as the performance of the algorithm degrades with increase in the problem complexity. This paper presents HSA with improved exploration and exploitation capability coupled with local iterative search based on random swap operator for solving BPP. The study uses the despotism based approach presented by Yadav et al. (2012) [Yadav P., Kumar R., Panda S.K., Chang, C. S. (2012). An intelligent tuned harmony search algorithm for optimisation. Information Sciences, 196, 47-72.] to divide Harmony memory (HM) into two categories which helps to maintain balance between exploration and exploitation. Secondly, local iterative search explores multiple neighborhoods by exponentially swapping components of solution vectors. A problem specific HM representation, HM re-initialization strategy and two adaptive PAR strategies are tested. The performance of proposed HSA is evaluated on 180 benchmark instances which consists of 100, 200 and 500 objects. Evaluation metrics such as best, mean, success rate, acceleration rate and improvement measures are used to compare HSA variations. The performance of the HSA with iterative local search outperforms other two variations of HSA.

How to cite this paper

 Adamuthe, A & Nitave, T. (2021). Optimizing large scale bin packing problem with hybrid harmony search algorithm.International Journal of Industrial Engineering Computations , 12(2), 205-220.

References

Adamuthe A., & Nitave T. (2020). Harmony search algorithm with adaptive parameter setting for solving large bin packing problems, Decision Science Letters, 10(2).
Al-Betar, M. A., Khader, A. T., & Liao, I. Y. (2010). A harmony search with multi-pitch adjusting rate for the university course timetabling. In Recent advances in Harmony search algorithm (pp. 147-161). Springer, Berlin, Heidelberg.
Alvim, A. C., Ribeiro, C. C., Glover, F., & Aloise, D. J. (2004). A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 10(2), 205-229.
Baker, B. S., Coffman, Jr, E. G., & Rivest, R. L. (1980). Orthogonal packings in two dimensions. SIAM Journal on computing, 9(4), 846-855.
Blum, C., & Schmid, V. (2013). Solving the 2D bin packing problem by means of a hybrid evolutionary algorithm. Procedia Computer Science, 18, 899-908.
Chakraborty, P., Roy, G. G., Das, S., Jain, D., & Abraham, A. (2009). An improved harmony search algorithm with differential mutation operator. Fundamenta Informaticae, 95(4), 401-426.
Chen, J., Pan, Q. K., Wang, L., & Li, J. Q. (2012). A hybrid dynamic harmony search algorithm for identical parallel machines scheduling. Engineering Optimization, 44(2), 209-224.
Chung, F. R., Garey, M. R., & Johnson, D. S. (1982). On packing two-dimensional bins. SIAM Journal on Algebraic Discrete Methods, 3(1), 66-76.
Coffman, Jr, E. G., Garey, M. R., & Johnson, D. S. (1978). An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing, 7(1), 1-17.
Coffman, Jr, E. G., Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1980). Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4), 808-826.
De Cauwer, M., Mehta, D., & O'Sullivan, B. (2016). The temporal bin packing problem: an application to workload management in data centres. In 2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 157-164). IEEE.
dos Santos Coelho, L., & de Andrade Bernert, D. L. (2009). An improved harmony search algorithm for synchronization of discrete-time chaotic systems. Chaos, Solitons & Fractals, 41(5), 2526-2532.
El-Abd, M. (2013). An improved global-best harmony search algorithm. Applied Mathematics and Computation, 222, 94-106.
Fleszar, K., & Hindi, K. S. (2002). New heuristics for one-dimensional bin-packing. Computers & Operations Research, 29(7), 821-839.
Frenk, J. G., & Galambos, G. (1987). Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem. Computing, 39(3), 201-217.
Gary, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness.(1979). WH Freman and Co.
Geem Z.W., Tseng CL., Park Y. (2005) Harmony search for generalized orienteering problem: best touring in China. In: Wang L., Chen K., Ong Y.S. (eds) Advances in Natural Computation. ICNC 2005. Lecture Notes in Computer Science, vol 3612. Springer, Berlin, Heidelberg.
Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A new heuristic optimization algorithm: harmony search. Simulation, 76(2), 60-68.
Guo, Z., Yang, H., Wang, S., Zhou, C., & Liu, X. (2018). Adaptive harmony search with best-based search strategy. Soft Computing, 22(4), 1335-1349.
Hasançebi, O., Erdal, F., & Saka, M. P. (2010). Adaptive harmony search method for structural optimization. Journal of Structural Engineering, 136(4), 419-431.
Hasanipanah, M., Keshtegar, B., Thai, D. K., & Troung, N. T. (2020). An ANN-adaptive dynamical harmony search algorithm to approximate the flyrock resulting from blasting. Engineering with Computers, 1-13..
Hopper, E., & Turton, B. (1999). A genetic algorithm for a 2D industrial packing problem. Computers & Industrial Engineering, 37(1-2), 375-378.
Kong, X., Gao, L., Ouyang, H., & Li, S. (2015). A simplified binary harmony search algorithm for large scale 0–1 knapsack problems. Expert Systems with Applications, 42(12), 5337-5355.
Leinberger, W., Karypis, G., & Kumar, V. (1999, September). Multi-capacity bin packing algorithms with applications to job scheduling under multiple constraints. In Proceedings of the 1999 International Conference on Parallel Processing (pp. 404-412). IEEE.
Lodi, A., Martello, S., & Vigo, D. (1999a). Approximation algorithms for the oriented two-dimensional bin packing problem. European Journal of Operational Research, 112(1), 158-166.
Lodi, A., Martello, S., & Vigo, D. (1999b). Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing, 11(4), 345-357.
Lodi, A., Martello, S., & Vigo, D. (1999c). Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem. In Meta-Heuristics (pp. 125-139). Springer, Boston, MA.
Mahdavi, M., Fesanghary, M., & Damangir, E. (2007). An improved harmony search algorithm for solving optimization problems. Applied Mathematics and Computation, 188(2), 1567-1579.
Manjarres, D., Landa-Torres, I., Gil-Lopez, S., Del Ser, J., Bilbao, M. N., Salcedo-Sanz, S., & Geem, Z. W. (2013). A survey on applications of the harmony search algorithm. Engineering Applications of Artificial Intelligence, 26(8), 1818-1831.
Moh’d Alia, O., & Mandava, R. (2011). The variants of the harmony search algorithm: an overview. Artificial Intelligence Review, 36(1), 49-68.
Monaci, M., & Toth, P. (2006). A set-covering-based heuristic approach for bin-packing problems. INFORMS Journal on Computing, 18(1), 71-85.
Omran, M. G., & Mahdavi, M. (2008). Global-best harmony search. Applied Mathematics and Computation, 198(2), 643-656.
Pandi, V.R., Panigrahi, B.K. (2011) Dynamic economic load dispatch using hybrid swarm intelligence based harmony search algorithm. Expert Systems with Applications, 38, 8509-8514. https://doi.org/10.1016/j.eswa.2011.01.050
Paquay, C., Schyns, M., & Limbourg, S. (2016). A mixed integer programming formulation for the three‐dimensional bin packing problem deriving from an air cargo application. International Transactions in Operational Research, 23(1-2), 187-213.
Parreño, F., Alvarez-Valdés, R., Oliveira, J. F., & Tamarit, J. M. (2010). A hybrid GRASP/VND algorithm for two-and three-dimensional bin packing. Annals of Operations Research, 179(1), 203-220.
Perboli, G., Gobbato, L., & Perfetti, F. (2014). Packing problems in transportation and supply chain: new problems and trends. Procedia-Social and Behavioral Sciences, 111, 672-681.
Saka M.P., & Hasançebi O. (2009). Adaptive Harmony Search Algorithm for Design Code Optimization of Steel Structures. In: Geem Z.W. (eds) Harmony Search Algorithms for Structural Design Optimization. Studies in Computational Intelligence, vol 239. Springer, Berlin, Heidelberg
Schoenfield, J. E. (2002). Fast, exact solution of open bin packing problems without linear programming. Draft, US Army Space and Missile Defense Command, Huntsville, Alabama, USA.
Schwerin, P., & Wäscher, G. (1997). The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP. International Transactions in Operational Research, 4(5-6), 377-389.
Simchi‐Levi, D. (1994). New worst‐case results for the bin‐packing problem. Naval Research Logistics (NRL), 41(4), 579-585.
Song, W., Xiao, Z., Chen, Q., & Luo, H. (2013). Adaptive resource provisioning for the cloud using online bin packing. IEEE Transactions on Computers, 63(11), 2647-2660.
Stützle, T. (1999). Local search algorithms for combinatorial problems: analysis, improvements, and new applications.
Suganthan, P. N., Hansen, N., Liang, J. J., Deb, K., Chen, Y. P., Auger, A., & Tiwari, S. (2005). Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. KanGAL report, 2005005(2005), 2005.
Taherinejad, N. (2009, August). Highly reliable harmony search algorithm. In 2009 European Conference on Circuit Theory and Design (pp. 818-822). IEEE.
Wang, C. M., & Huang, Y. F. (2010). Self-adaptive harmony search algorithm for optimization. Expert Systems with Applications, 37(4), 2826-2837.
Wang, L., Pan, Q. K., & Tasgetiren, M. F. (2011). A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem. Computers & Industrial Engineering, 61(1), 76-83.
Wong, L., & Lee, L. S. (2009). Heuristic placement routines for two-dimensional bin packing problem. Journal of Mathematics and Statistics, 5(4), 334.
Wu, B., Qian, C., Ni, W., & Fan, S. (2012). Hybrid harmony search and artificial bee colony algorithm for global optimization problems. Computers & Mathematics with Applications, 64(8), 2621-2634.
Yadav P., Kumar R., Panda S.K., Chang, C. S. (2012). An intelligent tuned harmony search algorithm for optimisation. Information Sciences, 196, 47-72.
Yang, X. S. (2009). Harmony search as a metaheuristic algorithm. In Music-inspired harmony search algorithm (pp. 1-14). Springer, Berlin, Heidelberg