An extended class of flexible shop scheduling problems is considered. First, the problem is translated into a mathematical programming formula, i.e., a mixed-integer programming problem. This makes it possible to apply standard packages of mixed integer programming solvers and, while lots of computational time is required in general, to obtain the optimal schedule. Then, in order to seek the schedules close to the optimal for larger-scale problems, a solution method by adopting genetic algorithms based on the formula is newly designed. Through some computational experiments, the effectiveness and the potential of the proposed approach are investigated.