In this paper we propose an improved algorithm to search optimal solutions to the flow shop scheduling problems with fuzzy processing times and fuzzy due dates. A longest common substring method is proposed to combine with the random key method. Numerical simulation shows that longest common substring method combined with rearranging mating method improves the search efficiency of genetic algorithm in this problem. For application in large-sized problems, we also enhance this modified algorithm by CUDA based parallel computation. Numerical experiments show that the performances of the CUDA program on GPU compare favorably to the traditional programs on CPU. Based on the modified algorithm invoking with CUDA scheme, we can search satisfied solutions to the fuzzy flow shop scheduling problems with high performance