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.