We propose in this paper different approaches for the flexible job shop scheduling problem. The chosen criterion is the total tardiness due to the importance of respecting the due dates in production process and in the whole supply chain. The first approach is based on the decomposition of the problem in an assignment problem and a sequencing problem. The first part is ensured by an assignment technique based on a heuristic approach and the definition of an intermediary criteria. The second part consists in applying a genetic algorithm to deal with the sequencing problem. The second approach is rather an integrated one based on genetic algorithm and the generalization of a coding used for the classic job-shop.