A new version of BLS algorithm is introduced. Levenshtein Distance (LD) metric is applied to the BLS heuristic. The QAP is optimized with several processors using OpenMP. Significant improvements are obtained. The BLS-OpenMP can be reported as one of the best heuristics for the QAP.