The flow shop scheduling with blocking is considered an important scheduling problem which has many real-world applications. This paper proposes a new algorithm which applies heuristic techniques in harmony search algorithm (HSA) to minimize the total flow time. The proposed method is called modified harmony search algorithm with neighboring heuristics methods (MHSNH). To improve the initial harmony memory, we apply two heuristic techniques: nearest neighbor (NN) and constructive modified NEH (MNEH). A modified version of harmony search algorithm evolves to explore and generates a new solution. The newly generated solution is then enhanced by using neighboring heuristics. Lastly, another neighboring heuristic is applied to improve the obtained solution. The proposed algorithm is evaluated using 12 real-world problem instances each with 10 samples. The experimental evaluation is accomplished using two factors: CPU computational time and the number of iterations. For the first factor, comparative evaluation against six well-established methods shows that the proposed method achieves almost the best overall results in six problem instances out of the twelve and yields fruitful results for others. For the second factor, comparative evaluation against twelve well-regarded methods shows that the proposed method achieves the best overall results in three problem instances and obtains very good results in other instances. In a nutshell, the proposed MHSNH is an effective strategy for solving the job shop scheduling problem. © 2019 Elsevier B.V.