Problema de seqüenciamento em uma máquina com penalidades por antecipação e atraso: modelagem e resolução

• Ano de defesa: 2007
• Autor(a) principal: Aloisio de Castro Gomes Junior
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: ILS; Programação linear inteira mista; Metaheurísticas; GRASP; Seqüenciamento em uma máquina; Engenharia de produção
• Link de acesso: http://hdl.handle.net/1843/NVEA-7B7M9F

This dissertation deals with the problem of scheduling single machine with earliness and tardiness penalties, with sequence dependent setup and due windows.For contextualization of the problem studied, some techniques used by others authors to solve it and similar problems are showed. Firstly, a model of mixed integer linear programming is proposed to represent the problem. This model was implemented usingthe modeling tool AMPL and solved by optimization software CPLEX 9.1. Afterwards, heuristics methods based on GRASP, Iterated Local Search and Variable Neighborhood Descent to solve it are proposed. For each job sequence generated by the heuristics, an optimal timing algorithm is used to determine the starting time for each job in the job sequence. Computational experiments realized with instances randomly generatedshow that the methods proposed are able to reach the optimal solution in most of the small instances (8 to 12 jobs) and yield low gaps in instances with 15 to 75 jobs.