ARAÚJO, P. H. M. Uma Heurística Langrangeana para o Problema de Ponderação de Rodadas. 2014. 84 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T20:24:27Z No. of bitstreams: 1 2014_dis_phmaraujo.pdf: 2899415 bytes, checksum: 09eb89cd95ed8aaebf416937c1fd27ac (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-02-09T15:42:02Z (GMT) No. of bitstreams: 1 2014_dis_phmaraujo.pdf: 2899415 bytes, checksum: 09eb89cd95ed8aaebf416937c1fd27ac (MD5) / Made available in DSpace on 2015-02-09T15:42:02Z (GMT). No. of bitstreams: 1 2014_dis_phmaraujo.pdf: 2899415 bytes, checksum: 09eb89cd95ed8aaebf416937c1fd27ac (MD5) Previous issue date: 2014 / In this dissertation, our main objective was to develop a technique for resolution to a problem in the area of telecommunications. The problem in question is called Round Weighting Problem (RWP) and was originally proposed in (KLASING; MORALES; P eRENNES, 2008). The context of the problem involves a wireless network where communications are performed by radio waves and the network operates through a network operation that satis es the constraints of the problem. Initially, we explain how a radio network is formed and describe the mode of operation of the radio network with restrictions using a mathematical model. Then, we formalize the RWP as an optimization problem, specifying their restrictions, corresponding to the generation of the set of possible network operations, and optimization criterion, regarding the use of network resources. Subsequently, we show a preliminary study of the Fractional Coloring problem (FC problem) and present a technique to solve this problem through the use of a lagrangian heuristic based on a lagrangian relaxation of an integer programming formulation of the problem. This resolution technique is then adapted to the RWP, consisting in the main contribution of our research. Finally, we show the computational results and analyzes of our implementations for the Fractional Coloring problem and RWP. / Nesta dissertação, nosso principal objetivo foi desenvolver uma técnica de resolução para um problema na área de telecomunicações. O problema em questão é chamado de problema de Ponderação de Rodadas (PR) e foi inicialmente proposto em [Klasing,Morales,Perennes, 2008]. O contexto do problema envolve uma rede sem fio, onde as comunicações são realizadas via ondas de rádio e a rede funciona através de uma operação da rede que satisfaz certas restrições. Inicialmente, explicamos como é formada uma rede de rádio e descrevemos a forma de operação da rede de rádio junto às restrições usando um modelo matemático. Em seguida, formalizamos o problema PR como um problema de otimização, especificando suas restrições, correspondente à geração do conjunto de possíveis operações da rede, e critério de otimização, referente ao uso dos recursos da rede. Posteriormente, mostramos um estudo preliminar do problema de Coloração Fracionária (CF) e apresentamos uma técnica de resolução deste problema através do uso de uma heurística lagrangeana baseada em uma relaxação lagrangeana de uma formulação de programação inteira do problema. Essa técnica de resolução é então adaptada para o problema PR, consistindo na principal contribuição de nossa pesquisa. Por fim, mostramos os resultados computacionais e análises das nossas implementações para os problemas CF e PR.

O escalonamento de veículos para múltiplas garagens é um problema clássico da Pesquisa Operacional de grande relevância à otimização da malha de transportes, de forma a buscar a melhor alocação dos recursos disponíveis. O problema é conhecido por ser do tipo NP-hard, e portanto a sua solução para grandes instâncias é realizada por heurísticas. Este trabalho aborda o desenvolvimento de uma heurística simples e eficiente para solucionar o MDVSP, buscando através da redução de possibilidades de viagens, pela retirada de viagens com baixas chances de pertencer a solução ótima reduzir a complexidade da rede. O problema reduzido, é então resolvido pela técnica de geração de colunas truncado e modificado, para resolver o problema de forma aceitável, encontrando soluções com bom compromisso entre tempo de execução e valor da função objetivo. A geração de colunas foi testada e validada através de comparações com trabalhos similares, enquanto que, cada técnica de redução de espaço de estados (de forma conjunta e individual) foram validados através da comparação com os resultados validados da geração de colunas modificada. A heurística mostrou uma melhoria considerável por meio da otimização do tempo de resolução, sem prejudicar os resultados de melhor valor, ficando com uma diferença máxima de 1% em comparação com os valores obtidos com geração de colunas. Se a redução for usada parcialmente, os tempos de solução podem ser reduzidos mais de sete vezes, com um pequeno incremento no valor da função objetivo. Pelas validações e experimentos realizados, pode-se afirmar que a heurística tem potencial para ser utilizada em problemas do mundo real, bem como servir como parte da solução de problemas correlatos mais complexos, como o crew scheduling, o disruption management e o escalonamento em tempo real. / The Multi Depot Vehicle Scheduling is a classical problem of Operations Research, with a great relevance to optimize the transportation network, as to find the best allocation of available resources. This problem is known to be NP-Hard, and therefore the solution of large instances is generally carried out by heuristics. This work proposes the development of a simple and efficient heuristic to solve the MDVSP, seeking by the reduction of travel possibilities, droping traveis with low chances to be in the best solution. The reduced problem is then solved by a modified truncated column generation technique, to solve the problem by an acceptable form, founding solutions for the MDVSP with a good compromise between time and costs. The column generation was tested and validated by the comparison of execution time and the value of objective function. The column generation was tested and comparised with similar works, whereas, each space state reduction technique (individual and joint) was validated in comparison with validated results of column generation truncated and modificated. The heuristics showed considerable improvements by the optimization of resolution time, without harm the best value results, obtaining differences lower as 1% comparing with the obtained values by the column generation solution. If the reduction is used partially, the solution times can be reduced in more then seven times, with a small increment in the objective function value. By the validations and experimenta realized, we can confirm that the heuristics has potential to be used in real world situations, as well as to serve as basis for the development of solution methods for more complex and correlated problems, as the crew scheduling problem, disruption management, and the real time assignment.

Made available in DSpace on 2016-08-29T15:33:17Z (GMT). No. of bitstreams: 1 tese_5121_.pdf: 735975 bytes, checksum: aeffd7d6fc81e4f73c1f18fb633dc4e1 (MD5) Previous issue date: 2012-07-30 / Agrupamento de dados é uma tarefa recorrente em mineração de dados. Com o passar do tempo, vem se tornando mais importante o agrupamento de bases cada vez maiores. Contudo, aplicar heurísticas de agrupamento tradicionais em grandes bases não é uma tarefa fácil. Essas técnicas geralmente possuem complexidades pelo menos quadráticas no número de pontos da base, tornando o seu uso inviável pelo alto tempo de resposta ou pela baixa qualidade da solução final. A solução mais comumente utilizada para resolver o problema de agrupamento em bases de dados grandes é usar algoritmos especiais, mais fracos no ponto de vista da qualidade. Este trabalho propõe uma abordagem diferente para resolver esse problema: o uso de algoritmos tradicionais, mais fortes, em um sub-conjunto dos dados originais. Esse sub-conjunto dos dados originais é obtido com uso de um algoritmo co-evolutivo que seleciona um sub-conjunto de pontos difícil de agrupar.

O escalonamento de veículos para múltiplas garagens é um problema clássico da Pesquisa Operacional de grande relevância à otimização da malha de transportes, de forma a buscar a melhor alocação dos recursos disponíveis. O problema é conhecido por ser do tipo NP-hard, e portanto a sua solução para grandes instâncias é realizada por heurísticas. Este trabalho aborda o desenvolvimento de uma heurística simples e eficiente para solucionar o MDVSP, buscando através da redução de possibilidades de viagens, pela retirada de viagens com baixas chances de pertencer a solução ótima reduzir a complexidade da rede. O problema reduzido, é então resolvido pela técnica de geração de colunas truncado e modificado, para resolver o problema de forma aceitável, encontrando soluções com bom compromisso entre tempo de execução e valor da função objetivo. A geração de colunas foi testada e validada através de comparações com trabalhos similares, enquanto que, cada técnica de redução de espaço de estados (de forma conjunta e individual) foram validados através da comparação com os resultados validados da geração de colunas modificada. A heurística mostrou uma melhoria considerável por meio da otimização do tempo de resolução, sem prejudicar os resultados de melhor valor, ficando com uma diferença máxima de 1% em comparação com os valores obtidos com geração de colunas. Se a redução for usada parcialmente, os tempos de solução podem ser reduzidos mais de sete vezes, com um pequeno incremento no valor da função objetivo. Pelas validações e experimentos realizados, pode-se afirmar que a heurística tem potencial para ser utilizada em problemas do mundo real, bem como servir como parte da solução de problemas correlatos mais complexos, como o crew scheduling, o disruption management e o escalonamento em tempo real. / The Multi Depot Vehicle Scheduling is a classical problem of Operations Research, with a great relevance to optimize the transportation network, as to find the best allocation of available resources. This problem is known to be NP-Hard, and therefore the solution of large instances is generally carried out by heuristics. This work proposes the development of a simple and efficient heuristic to solve the MDVSP, seeking by the reduction of travel possibilities, droping traveis with low chances to be in the best solution. The reduced problem is then solved by a modified truncated column generation technique, to solve the problem by an acceptable form, founding solutions for the MDVSP with a good compromise between time and costs. The column generation was tested and validated by the comparison of execution time and the value of objective function. The column generation was tested and comparised with similar works, whereas, each space state reduction technique (individual and joint) was validated in comparison with validated results of column generation truncated and modificated. The heuristics showed considerable improvements by the optimization of resolution time, without harm the best value results, obtaining differences lower as 1% comparing with the obtained values by the column generation solution. If the reduction is used partially, the solution times can be reduced in more then seven times, with a small increment in the objective function value. By the validations and experimenta realized, we can confirm that the heuristics has potential to be used in real world situations, as well as to serve as basis for the development of solution methods for more complex and correlated problems, as the crew scheduling problem, disruption management, and the real time assignment.

O escalonamento de veículos para múltiplas garagens é um problema clássico da Pesquisa Operacional de grande relevância à otimização da malha de transportes, de forma a buscar a melhor alocação dos recursos disponíveis. O problema é conhecido por ser do tipo NP-hard, e portanto a sua solução para grandes instâncias é realizada por heurísticas. Este trabalho aborda o desenvolvimento de uma heurística simples e eficiente para solucionar o MDVSP, buscando através da redução de possibilidades de viagens, pela retirada de viagens com baixas chances de pertencer a solução ótima reduzir a complexidade da rede. O problema reduzido, é então resolvido pela técnica de geração de colunas truncado e modificado, para resolver o problema de forma aceitável, encontrando soluções com bom compromisso entre tempo de execução e valor da função objetivo. A geração de colunas foi testada e validada através de comparações com trabalhos similares, enquanto que, cada técnica de redução de espaço de estados (de forma conjunta e individual) foram validados através da comparação com os resultados validados da geração de colunas modificada. A heurística mostrou uma melhoria considerável por meio da otimização do tempo de resolução, sem prejudicar os resultados de melhor valor, ficando com uma diferença máxima de 1% em comparação com os valores obtidos com geração de colunas. Se a redução for usada parcialmente, os tempos de solução podem ser reduzidos mais de sete vezes, com um pequeno incremento no valor da função objetivo. Pelas validações e experimentos realizados, pode-se afirmar que a heurística tem potencial para ser utilizada em problemas do mundo real, bem como servir como parte da solução de problemas correlatos mais complexos, como o crew scheduling, o disruption management e o escalonamento em tempo real. / The Multi Depot Vehicle Scheduling is a classical problem of Operations Research, with a great relevance to optimize the transportation network, as to find the best allocation of available resources. This problem is known to be NP-Hard, and therefore the solution of large instances is generally carried out by heuristics. This work proposes the development of a simple and efficient heuristic to solve the MDVSP, seeking by the reduction of travel possibilities, droping traveis with low chances to be in the best solution. The reduced problem is then solved by a modified truncated column generation technique, to solve the problem by an acceptable form, founding solutions for the MDVSP with a good compromise between time and costs. The column generation was tested and validated by the comparison of execution time and the value of objective function. The column generation was tested and comparised with similar works, whereas, each space state reduction technique (individual and joint) was validated in comparison with validated results of column generation truncated and modificated. The heuristics showed considerable improvements by the optimization of resolution time, without harm the best value results, obtaining differences lower as 1% comparing with the obtained values by the column generation solution. If the reduction is used partially, the solution times can be reduced in more then seven times, with a small increment in the objective function value. By the validations and experimenta realized, we can confirm that the heuristics has potential to be used in real world situations, as well as to serve as basis for the development of solution methods for more complex and correlated problems, as the crew scheduling problem, disruption management, and the real time assignment.

Submitted by Natalia de Souza Gonçalves (natalia.goncalves@ufpe.br) on 2015-05-08T13:45:06Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertacao_Final_Espedito_Luciano_Pereira_de_Melo_Biblioteca.pdf: 3496996 bytes, checksum: 7bbb08b60854a1e7eb38b44d5445cd65 (MD5) / Made available in DSpace on 2015-05-08T13:45:06Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertacao_Final_Espedito_Luciano_Pereira_de_Melo_Biblioteca.pdf: 3496996 bytes, checksum: 7bbb08b60854a1e7eb38b44d5445cd65 (MD5) Previous issue date: 2015-02-27 / Desde os anos 1990 é percebida a participação incisiva dos sistemas de informação no dia a dia das pessoas para o apoio no cumprimento dos seus objetivos pessoais e empresariais. Em especial, os Sistemas Integrados de Gestão, mais conhecidos como ERP (Enterprise Resource Planning), receberam atenção especial do mercado devido os grandes investimentos de tempo e dinheiro tanto em sua implantação quanto na sua continuidade e manutenção. Dentro das empresas, principalmente as de médio e grande portes, muitas das atividades diariamente realizadas só podem ser executadas por intermédio dos ERP. Porém, estudos apresentam que a interação com a interface humana destes sistemas poderá representar problemas de usabilidade quando os mesmos não conseguem transmitir aos seus usuários como realizar uma tarefa de forma objetiva e simples de acordo com os processos empresariais. Dessa forma, faz-se necessário a observância e a análise da usabilidade das interfaces dos ERP em todo o seu ciclo de vida. Para que um software possua uma boa usabilidade, o mesmo deve facilitar o processo de aprendizagem e atender as necessidades dos seus usuários, auxiliando-os a realizar as suas tarefas de forma eficiente. Este trabalho tem por objetivo propor uma metodologia de melhoria de usabilidade da interface humana de sistemas ERP, a fim de facilitar a execução de tarefas diárias nestes sistemas para usuários iniciantes, por meio da avaliação e correção dos problemas de usabilidade e da comunicação transparente e eficiente de tarefas incluídas em processos empresariais subjacentes. / Since the 90s, it is perceived the massive participation of information systems in daily life of people due to the support in execution their personal and business goals. In particular, ERP systems (Enterprise Resource Planning), received special attention from the market because of the large investments of time and money both in its implementation and in its continuity and maintenance. Within companies, especially those of medium and large sizes, many of the activities performed daily can only be enforced through the ERP systems. However, studies show that the interaction with the human interface of these systems could pose usability problems when they are unable to pass on to their users how to perform a task both objective and easily according to business processes. Thus, it is necessary compliance and the analysis of the usability of ERP systems interfaces throughout its life cycle. For software to provide good usability, it should facilitate the learning process and meet the needs of its users, helping them to carry out their tasks efficiently. This work aims at proposing a methodology for improvement of usability of human interface to ERP systems in order to facilitate the execution of daily tasks for novice users. This will be achieved through the evaluation and correction of usability issues and transparent and efficient communication of tasks included in the underlying business processes.

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T18:06:19Z (GMT). No. of bitstreams: 1 Scrich_CintiaRigao_D.pdf: 5028659 bytes, checksum: 8a6ac9c09514f4210e3b30dc988fa207 (MD5) Previous issue date: 1997 / Resumo: Este trabalho trata do problema de programação de tarefas nos ambientes job shop tradicional e job shop flexível com o objetivo de minimizar o atraso total das tarefas. A principal diferença do job shop flexível em relação ao job shop tradicional é que cada operação possui um conjunto de máquinas alternativas onde pode ser processada. Para cada um dos problemas é desenvolvida uma heurística guiada pela metaheurística Busca Tabu. Estratégias de diversificação e intensificação para a busca são sugeridas. Testes e resultados computacionais obtidos são apresentados. Para o job shop tradicional dois métodos heurísticos encontrados na literatura foram implementados e comparados com a heurística proposta / Abstract: This work addresses the traditional and the flexible job shop scheduling problems with the objective of minimizing total tardiness. The main difference between the flexible job shop and the traditional job shop is that each operation of a job can be processed in alternative machines. A heuristic method guided by the tabu search metaheuristic is developed for each problem. Diversification and intensification strategies are suggested. Tests and computational results are reported. For the traditional job shop two heuristic methods from the literature are implemented and compared with the proposed heuristic / Doutorado / Doutor em Engenharia Elétrica

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T21:05:28Z (GMT). No. of bitstreams: 1 Guimaraes_LuciaFilomenadeAlmeida_D.pdf: 6025825 bytes, checksum: 0cad394cd2c4d3042aece408ca602972 (MD5) Previous issue date: 1997 / Resumo: : O sistema Kanban de produção é um sistema do tipo ?puxar? para controle de chão de fábrica. Ele é motivado pelo conceito de produção Just-in-Time e tem como objetivo programar a produção, reduzindo ao mínimo os níveis de estoque. Neste trabalho considera-se um ambiente de produção com estrutura de montagem multi-estágio e restrições de capacidade dos itens componentes e do item final. Um modelo estocástico de otimização com recurso que incorpora as incertezas da demanda do item final e capacidade de produção é proposto. Demanda não atendida é permitida no estágio final do modelo. Um método do tipo Branch and Cut é desenvolvido para obter soluções ótimas. Soluções sub-ótimas são obtidas através de um método heurístico e de busca tabu. Testes computacionais são apresentado / Abstract: The kanban production system is a pull-type system for shop floor control. It is based on the concept of Just-in-Time production and has the porpuse of scheduling production, reducing inventory levels to a minimum. In this work, a multi-stage assembly-structure production setting with capacity constraints for the component items and the final item is considered. A stochastic optimization model with recourse that takes into account uncertainties of demand of the final item and production capacity is proposed. Backlog is allowed in the final stage. A Branch and Cut method is developed in order to obtain optimal solutions. Sub-optimal solutions are obtained by a heuristic method and by tabu search. Computational test are reported. / Doutorado / Doutor em Engenharia Elétrica

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T22:46:36Z (GMT). No. of bitstreams: 1 Ronconi_DeboraPretti_D.pdf: 6342421 bytes, checksum: 4eea640b528238ccaddebc27a9b9979a (MD5) Previous issue date: 1997 / Resumo: Este trabalho trata do problema de programar n tarefas em m máquinas no ambiente flowshop permutacional com buffer entre máquinas ilimitado a zero. O critério de otimalidade utilizado é a minimização da soma dos atrasos das tarefas. Primeiramente são sugeridas formulações de programação inteira mista para os problemas. Além disso realiza-se uma análise do comportamento de todas as soluções para diferentes cenários de datas de entrega para problemas de dimensão reduzida. A seguir são propostas heurísticas que utilizam Busca Tabu como método de exploração do espaço de soluções. Estratégias de diversificação, intensificação e de redução da vizinhança são apresentadas e avaliadas. O método Branch-and-Bound é utilizado para obter soluções ótimas, e um limitante inferior para o problema de flowshop com buffer zero é proposto. Testes computacionais são apresentados e a heurística é comparada com o algoritmo NEH e com o método Branch-and-Bound / Abstract: This work addresses the problem of scheduling n tasks on m machines in the permutation flowshop with both unlimited and zero buffers with the objective of minimizing total tardiness. First, we suggest mixed integer programming formulations for the problems. Furthermore, the behavior of all solutions for small problems is analyzed for different due date scenarios. Then Tabu Search-based heuristics are proposed as a method to explore the solution space. Diversification, intensification, and neighborhood restriction strategies are presented and evaluated. The Branch-and-Bound method is applied to obtain optimal solutions, and a lower bound for the flowshop problem with zero buffer is proposed. Computational tests are presented and compared with the NEH algorithm and with the Branch-and-Bound method / Doutorado / Doutor em Engenharia Elétrica

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-27T16:54:50Z (GMT). No. of bitstreams: 1 TinJunior_GilbertoJorge_M.pdf: 1402287 bytes, checksum: f569d1e1e8c6b5a1b10dfd3a2739c6ca (MD5) Previous issue date: 2001 / Mestrado