Large cities have been facing serious problems in the management of traffic, owing to the increasing number of vehicles and pedestrians. Traffic engineering is essential in managing traffic and improving urban mobility. This paper deals with the problem of fixed-time signal programming on traffic networks. A new bi-objective optimization model is proposed to maximize the average and minimize the variance of the vehicle speeds in the network. Although the first function is commonly discussed in the literature, the second one is novel, and its aim is to provide flow balance along the network. This combination of functions is optimized by the Memory-Based Variable-Length Nondominated Sorting Genetic Algorithm 2 (MBVL-NSGA2), which avoids the revaluation of candidate solutions. This approach was validated through experiments using the microscopic simulator GISSIM, in a multi-intersection real network, using measured data from Belo Horizonte traffic engineering company (BHTRANS). The practical results of MBVL-NSGA2 were compared with four approaches: (1) current BHTRANS solutions; (2) a genetic algorithm optimizing the first function; (3) a genetic algorithm optimizing the second function, and; (4) the traditional NSGA2. Analysis showed that this proposal is able to generate better traffic signal plans, at the same time that it generates a diversified set of efficient candidate solutions.