This paper studies a new class of optimization problems which have multiple objective functions subject to a set of fuzzy relation equations. Since the feasible domain of such a problem is in general non-convex and the objective functions are not necessarily linear, traditional optimization methods may become ineffective and inefficient. Taking advantage of the special structure of the solution set, a reduction procedure is developed to simplify a given problem. Moreover, a genetic-based algorithm is proposed to find the “Pareto optimal solutions”. The major components of the proposed algorithm together with some encouraging test results are reported.