This paper presents the application of common heuristics, random search and evolutionary algorithms with representation of random keys and permutations in order to compare as techniques of optimization for the machine sequence planning in a real scenario considering multiples precedence. The results indicate a compromise that the user must take between the quality of the solution and the processing time.