An optimization model with a linear objective function subject to max-t fuzzy relation equations as constraints is presented, where t is an Archimedean t-norm. Since the non-empty solution set of the fuzzy relation equations is in general a non-convex set, conventional linear programming methods are not suitable for solving such problems. The concept of covering problem is applied to establish 0-1 integer programming problem equivalent to linear programming problem and a binary coded genetic algorithm is proposed to obtain the optimal solution. An example is given for illustration of the method.