A programação de tarefas em linhas de produção nas empresas sempre foi e continua sendo um elemento fundamental para o sucesso das organizações em um mercado tão globalizado e competitivo. A melhor utilização dos recursos instalados através da melhor alocação das tarefas gerará melhores resultados para a organização. Entende-se pela melhor utilização dos recursos a redução do tempo total de finalização das tarefas (makespan) sem prejudicar o atendimento da data de entrega. Aplica-se esta idéia para as indústrias de um modo geral, que tenham linhas de produção, podendo citar a indústria calçadista, foco neste trabalho, as indústrias de massas, biscoitos e balas, entre outras. Na literatura especializada, esta programação é conhecida como sequenciamento de tarefas em processadores. Neste trabalho aplicado junto a indústria calçadista, foca-se em uma área mais específica: o sequenciamento de tarefas em processadores paralelos. Os problemas de sequenciamento se caracterizam pela grande exigência computacional para a resolução com algoritmos de otimização. Isto remete a utilização de heurísticas para a resolução destes problemas. Neste trabalho explora-se a Meta-Heurística Busca Tabu, que se apresentou com resultados muito bons em relação ao ótimo e em relação ao trabalhador humano. / The jobs scheduling in processor lines in the companies was always, and continues being, a fundamental element to the organization’s success in a very globalized and competitive market. The best use of the installed resources, through the best distribution of the jobs will generate better results for the organization. The best utilization of the resources means the reduction of the makespan without prejudicing the due-date. This idea is applied to all industries in general, that have processor lines, for example the shoes factories, focused in this research, pasta, cookies and sugar balls factories, beyond others. In the specialized literature this subject is know as job scheduling. This researh is applyed to a shoes factory is focused on more specific area: the job scheduling in parallel machines. The scheduling problems are characterized on its computational difficulty using optimization algoritms. That is the reason why we used heuristics to solve these problems. In this research we explore the Meta-Heuristic Tabu Search, wich showed very good results comparing to the optimun and comparing to the human worker.

A programação de tarefas em linhas de produção nas empresas sempre foi e continua sendo um elemento fundamental para o sucesso das organizações em um mercado tão globalizado e competitivo. A melhor utilização dos recursos instalados através da melhor alocação das tarefas gerará melhores resultados para a organização. Entende-se pela melhor utilização dos recursos a redução do tempo total de finalização das tarefas (makespan) sem prejudicar o atendimento da data de entrega. Aplica-se esta idéia para as indústrias de um modo geral, que tenham linhas de produção, podendo citar a indústria calçadista, foco neste trabalho, as indústrias de massas, biscoitos e balas, entre outras. Na literatura especializada, esta programação é conhecida como sequenciamento de tarefas em processadores. Neste trabalho aplicado junto a indústria calçadista, foca-se em uma área mais específica: o sequenciamento de tarefas em processadores paralelos. Os problemas de sequenciamento se caracterizam pela grande exigência computacional para a resolução com algoritmos de otimização. Isto remete a utilização de heurísticas para a resolução destes problemas. Neste trabalho explora-se a Meta-Heurística Busca Tabu, que se apresentou com resultados muito bons em relação ao ótimo e em relação ao trabalhador humano. / The jobs scheduling in processor lines in the companies was always, and continues being, a fundamental element to the organization’s success in a very globalized and competitive market. The best use of the installed resources, through the best distribution of the jobs will generate better results for the organization. The best utilization of the resources means the reduction of the makespan without prejudicing the due-date. This idea is applied to all industries in general, that have processor lines, for example the shoes factories, focused in this research, pasta, cookies and sugar balls factories, beyond others. In the specialized literature this subject is know as job scheduling. This researh is applyed to a shoes factory is focused on more specific area: the job scheduling in parallel machines. The scheduling problems are characterized on its computational difficulty using optimization algoritms. That is the reason why we used heuristics to solve these problems. In this research we explore the Meta-Heuristic Tabu Search, wich showed very good results comparing to the optimun and comparing to the human worker.

A programação de tarefas em linhas de produção nas empresas sempre foi e continua sendo um elemento fundamental para o sucesso das organizações em um mercado tão globalizado e competitivo. A melhor utilização dos recursos instalados através da melhor alocação das tarefas gerará melhores resultados para a organização. Entende-se pela melhor utilização dos recursos a redução do tempo total de finalização das tarefas (makespan) sem prejudicar o atendimento da data de entrega. Aplica-se esta idéia para as indústrias de um modo geral, que tenham linhas de produção, podendo citar a indústria calçadista, foco neste trabalho, as indústrias de massas, biscoitos e balas, entre outras. Na literatura especializada, esta programação é conhecida como sequenciamento de tarefas em processadores. Neste trabalho aplicado junto a indústria calçadista, foca-se em uma área mais específica: o sequenciamento de tarefas em processadores paralelos. Os problemas de sequenciamento se caracterizam pela grande exigência computacional para a resolução com algoritmos de otimização. Isto remete a utilização de heurísticas para a resolução destes problemas. Neste trabalho explora-se a Meta-Heurística Busca Tabu, que se apresentou com resultados muito bons em relação ao ótimo e em relação ao trabalhador humano. / The jobs scheduling in processor lines in the companies was always, and continues being, a fundamental element to the organization’s success in a very globalized and competitive market. The best use of the installed resources, through the best distribution of the jobs will generate better results for the organization. The best utilization of the resources means the reduction of the makespan without prejudicing the due-date. This idea is applied to all industries in general, that have processor lines, for example the shoes factories, focused in this research, pasta, cookies and sugar balls factories, beyond others. In the specialized literature this subject is know as job scheduling. This researh is applyed to a shoes factory is focused on more specific area: the job scheduling in parallel machines. The scheduling problems are characterized on its computational difficulty using optimization algoritms. That is the reason why we used heuristics to solve these problems. In this research we explore the Meta-Heuristic Tabu Search, wich showed very good results comparing to the optimun and comparing to the human worker.

Submitted by Elton Lever (elton@icomp.ufam.edu.br) on 2018-08-23T20:26:01Z No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-08-23T20:35:20Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-08-24T13:35:27Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Made available in DSpace on 2018-08-24T13:35:28Z (GMT). No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) Previous issue date: 2017-06-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation addresses the class of job scheduling problems with precedence constraints and unit execution times, in identical parallel processors. Such a class of problems is of great importance in computational complexity theory, since small varia- tions in the conditions involved in scheduling make an easy problem very difficult. Two major problems involve the condition of the number of processors, where, if the number of processors is variable, given as input, such problem is proved to be NP-complete, but if the number of processors is fixed, the problem is still open. In this context, the focus of the research involves the problem already proven to be NP-complete, where for which we investigated the main approximation algorithms in the literature and their proofs of approximation ratio of the optimal, such as of the Garey & Jonhson’s 2-approximation algorithm, of the Hu, of the Coffman & Graham, and of the Gangal & Ranade with 2 − (7/(3P + 1)), the best approximation ratio in the literature. The approximation ratio proofs of such algorithms were detailed. As the main contribution of this research, were proved the optimality for specific classes of acyclic directed graphs involving trees (prece- dence trees, such as in-tree and out-tree) for the best approximation algorithms literature. / Esta dissertação aborda a classe de problemas de escalonamento de tarefas com restrições de precedências e tempos unitários em processadores paralelos idênticos. Tal classe de problemas tem uma grande importância em teoria da complexidade computacional, uma vez que pequenas variações nas condições envolvidas no esca- lonamento, fazem com que um problema fácil se torne muito difícil. Dois grandes problemas envolvem a condição do número de processadores, onde, se o número de processadores for variável, dado como entrada, tal problema é provado ser NP-completo, mas, se o número de processadores for fixo, o problema ainda está em aberto. Neste contexto, o foco da pesquisa envolve o problema já provado ser NP-completo, onde para qual se investigou os principais algoritmos aproximativos existentes na literatura e suas provas de razão de aproximação do ótimo, tais como o algoritmo 2-aproximativo de Garey & Jonhson e as melhorias de Hu, Coffman & Graham e de Gangal & Ranade (GR) com 2 −(7/(3P+1)), o de melhor razão de aproximação da literatura. As provas de razão de aproximação de tais algoritmos foram detalhadas. Como principal contribuição da pesquisa, foram determinados casos especiais ótimos, para classes específicas de grafos direcionados acíclicos que envolvem arborescências (árvores de precedência, como in-tree e out-tree) para o melhor algoritmos aproximativo da literatura. / Compreender o que querem em alguns momentos.