This paper deals with the resolution of the job shop problem with blocking, where the machines have a limited or no storage space. This brings a new constraint to the classical job shop problem. In industry, there are many situations where there are no storage space at all, and this leads to blocking constraints; i.e. if the next machine for a given operation is not available, then this operation will remain pending on the current machine even if its processing is over, in which case we call it a blocked machine. To solve this problem, we propose two different metaheuristics based on Tabu Search TS and genetic algorithms GA. In the first one, our contribution lays in a very efficient neighborhood exploring and evaluation techniques, which improve the reliability of the method. These techniques operate on the critical path found in the alternative graph and always construct feasible solutions. In the second, we use two different paradigms of parallelization with GA. The first uses a network computers and the second uses GPU with CUDA technology. The results are very interesting. In both methods, we obtain a very significant reduction of computation time compared with the existing literature results.