Orientador: Paulo Morelato FrançaDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de ComputaçãoResumo: O problema de Sequenciamento em Máquina Simples (SMS) é um dos mais tradicionais na área de sequenciamento. Neste trabalho é explorado inicialmente o problema de SMS com restrições de tempo (datas de entrega de produtos e tempos de preparação). O objetivo é a minimização do atraso total, que se caracteriza pela soma dos atrasos na entrega de todos os produtos. O método escolhido é baseado em Algoritmos Meméticos (AM). AM constituem uma classe de metaheurística do tipo populacional que engloba outras já conhecidas, como Algoritmos Genéticos híbridos, Busca por Espalhamento, entre outras. Nesta tese, o AM utilizado é um Algoritmo Genético (AG) acrescido de uma rotina de busca local aplicada a cada elemento novo da população. Na parte evolutiva são estudadas e testadas várias possibilidades para os operadores de recombinação, mutação, estruturas populacionais, etc. São também pesquisadas estruturas de busca local que melhor se adequam para a formação de um AM. As comparações de desempenho são feitas com três diferentes abordagens encontradas na literatura. Como complementação ao trabalho são ainda analisadas a robustez do AM e o fitness landscape. Ambos são de extrema importância para validar o método e para caracterizar a dificuldade em resolver diferentes instâncias do problema. ...Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digitalAbstract: The Single Machine Scheduling Problem (SMS) is one of the most representative in the scheduling area. In this work we initially explore the SMS problem with time constraints (due-dates and setup times). The goal is to minimize the total tardiness, which is characterized by the sum of the delays in the production of all products. The method chosen is based on Memetic Algorithms (MA). MA constitute a class of population metaheuristics that comprise many others, such as Hybrid Genetic Algorithms, Scatter Search, etc. In this thesis the MA implemented is a Genetic Algorithm (GA) with a local search routine that is applied to each new element of the population. Concerning the evolutionary part we study and test several possibilities of recombination operators, mutation, population structures, etc. We also test local search structures that are better fitted to the design of an MA. Performance comparisons are carried out with three different approaches found in the literature. As an addition to this work we also analyze the robustness of the MA and the Fitness Landscape. 80th are extremely important to validate the method and to characterize the difficulty to solve different instances of the problem. As an extension we show some results for the Parallel Machine Scheduling (PMS) problem with sequence-dependent setup times. ...Note: The complete abstract is available with the full electronic digital thesis or dissertationsMestradoAutomaçãoMestre em Engenharia Eletrica