We address a generalization of the classical job-shop problem which is called a hybrid job-shop problem. The criteria under consideration are the minimization of the makespan and mean ow time. In the hybrid job-shop, machines of type k are available for processing the specific subset O^k of the given operations. Each set O^k maybe partitioned into subsets for their processing on the machines of type k. Solving the hybrid job-shopproblem implies the solution of two subproblems: an assignment of all operations fromthe set O^k to the machines of type k and nding optimal sequences of the operationsfor their processing on each machine. In this paper, a genetic algorithm is developedto solve these two subproblems simultaneously. For solving the subproblems, a specialchromosome is used in the genetic algorithm based on a mixed graph model. We com-pare our genetic algorithms with a branch and bound algorithms and three other recentheuristic algorithms from the literature. Computational results for benchmark instanceswith 10 jobs and up to 50 machines show that the proposed genetic algorithm is ratherecient for both criteria. Compared with the other heuristics, the new algorithm givesmost often an optimal solution and the average percentage deviation from the optimalfunction value is about 4 %.