Many embedded products industries work with a variety of products on their production lines. This variety causes difficulties in fulfilling the tasks sequencing on equipments, since these processes present a high complexity of running productive operations. A way to solve this problem is to seek scheduling optimization, by applying mathematical models. In this study the main challenge points out to the scheduling optimization in an embedded production system, taking to consideration the function of minimizing the makespan and maximizing the profit. Thus, there were implemented three mathematical formulations with the objective of minimizing the makespan and maximizing the profit function. In the first formulation it was considered the possibility of multiple stages and unique machines, on the second, it was considered the possibility of multiple stages and parallel machines, the third considered multiple stages and identical parallel machines with the setup depending on the sequence, and lastly, on the fourth formulation there were considered all the information present in the representation of states and tasks network (STN) for a scheduling case with a long term horizon. The results showed the possibility of applying these models in embedded industries in both, short and long term.Muitas indústrias de produtos embutidos trabalham com uma grande variedade de produtos em suas linhas de produção. Essa variedade provoca uma dificuldade para a realização do sequenciamento das tarefas nos equipamentos, uma vez que essas linhas apresentam uma alta complexidade de operações produtivas sendo executadas. Uma forma de resolver esse problema é buscar técnica de otimização aplicada na Programação da Produção, por meio da aplicação de modelos matemáticos resolvidos computacionalmente. Neste estudo, o desafio central refere-se à utilização de modelos matemáticos para a otimização da Programação da Produção em um Sistema de Produção de Embutidos, levando em consideração a função de minimização do Makespan e maximização do lucro. Assim, foram utilizados três formulações matemáticas com objetivo de minimização do Makespan e uma de maximização de uma função lucro. Na primeira formulação foi considerada a possibilidade de múltiplos estágios e máquinas únicas. Na segunda considerou-se a possibilidade de múltiplos estágios e máquinas paralelas. Na terceira considerou-se múltiplos estágios e máquinas paralelas idênticas com setup dependente da sequência. Por fim, na quarta formulação foram consideradas todas as informações presentes na representação de rede de estados e tarefas (STN) para um caso de programação da produção com horizonte de longo prazo. Os resultados mostraram a possibilidade de aplicação desses modelos em indústria de embutidos, tanto no horizonte de curto prazo como no longo prazo.1 CD-ROM (274 f.)