This paper studies the flexible job-shop scheduling problem (FJSP) with the objective of minimizing the total completion time. This problem is known to be strongly NP-hard [1]. Therefore, it is quite difficult to achieve an optimal solution to this problem with exact methods and heuristic approaches are generally used to find near optimal solutions within a reasonable computation time. The present work proposes a Random-Key based genetic algorithm for the joint resolution of the inherent assignment and sequencing subproblems. A new chromosome encoding method with some effective crossover and mutation operators are introduced. Also, a mixed integer linear program is developed and tested. Computational experiments are carried out on a large set of instances. The proposed algorithm is proved to be both effective and efficient in solving the studied problem.