Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores (Energia). Universidade do Porto. Faculdade de Engenharia. 2011

Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 2009

Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores (Major Energia). Faculdade de Engenharia. Universidade do Porto. 2009

Tese de doutoramento. Programa Doutoral em Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2012

Tese de doutoramento. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 2007

Magíster en Ciencias, Mención Computación / Se sabe que existen factores humanos que influencian el comportamiento de un equipo de desarrollo durante la ejecución de un proyecto de software. Entre estos factores está la pro-actividad y el perfil psico-técnico de sus miembros, el grado de sociabilidad interpersonal del equipo, y el nivel de liderazgo del jefe de proyecto, entre otros. Los equipos cohesionados usualmente llevan a cabo procesos de software más coordinados y efectivos, que resultan en productos finales de mejor calidad y/o procesos de desarrollo que requieren un menor esfuerzo. La conformación de un buen equipo de desarrollo implica una inversión en tiempo y recursos económicos, que usualmente no puede ser asumida por varios tipos de organizaciones. Como por ejemplo, pequeñas empresas de software, que típicamente cuentan con recursos humanos y financieros limitados. En ese escenario los jefes de proyecto usan métodos y criterios ad-hoc para formar sus equipos; por ejemplo asignan al proyecto a la gente que está disponible. En consecuencia el nivel de cohesión de los equipos formados de esa manera es imprevisible. La detección tardía de incompatibilidades entre los miembros de un equipo de desarrollo puede generar resultados catastróficos para un proyecto. Esta problemática también está presente en escenarios universitarios, particularmente en carreras de Computación e Informática, donde el docente a cargo de un curso necesita armar equipos cohesivos con estudiantes que usualmente no conoce. Si los equipos están bien conformados, la probabilidad de éxito de un proyecto mejora considerablemente. En otro caso, el equipo tiene una alta probabilidad de fracaso. Si consideramos que el desarrollo de software es una actividad que se aprende en gran medida haciéndola, lograr experiencias con resultados positivos ayuda considerablemente a la formación de los estudiantes. En este escenario la conformación de equipos de desarrollo cohesivos juega un papel decisivo. Este trabajo de tesis propone una heurística para diseñar equipos cohesivos de desarrollo de software en escenarios universitarios. Para poder entregar un resultado, dicha heurística utiliza como base los perfiles psicológico, social y técnico de las personas, más un conjunto de parámetros (como por ejemplo, el tamaño de los equipos a conformar). Esta propuesta se validó en forma empírica en equipos de desarrollo de los cursos CC51A: Ingeniería de Software y CC61A: Proyecto de Software, impartidos por el Departamento de Ciencias de la Computación de la Universidad de Chile. En ambos cursos se realizan proyectos específicos, utilizando equipos de entre 5 y 7 estudiantes. Si bien se requiere más experimentación para poder sacar conclusiones definitivas, los resultados obtenidos hasta el momento indican claramente que los equipos diseñados usando heurística, muestran un nivel de comunicación y coordinación superior a aquellos conformados en forma aleatoria. Además, la calidad del producto final obtenido por estos equipos siguió el mismo patrón de comportamiento. Como productos de este trabajo de tesis se obtuvo: (1) un instrumento de diagnóstico que permite identificar el perfil socio-técnico de los desarrolladores, (2) una heurística que permite diseñar equipos cohesivos de desarrollo de software en base al perfil socio-técnico de los potenciales miembros, y (3) una herramienta de software que apoya los procesos de diagnóstico de candidatos y armado de equipos cohesivos en base al diagnóstico anterior. A futuro se espera aplicar esta propuesta para conformar de equipos de desarrollo en pequeñas empresas de software.

Submitted by Marcos Samuel (msamjunior@gmail.com) on 2017-06-13T13:35:56Z No. of bitstreams: 1 Dissertação Ligia.pdf: 1370436 bytes, checksum: e38350a980574846d81de84112d043d4 (MD5) / Approved for entry into archive by Vanessa Reis (vanessa.jamile@ufba.br) on 2017-06-27T12:45:35Z (GMT) No. of bitstreams: 1 Dissertação Ligia.pdf: 1370436 bytes, checksum: e38350a980574846d81de84112d043d4 (MD5) / Made available in DSpace on 2017-06-27T12:45:35Z (GMT). No. of bitstreams: 1 Dissertação Ligia.pdf: 1370436 bytes, checksum: e38350a980574846d81de84112d043d4 (MD5) / Partindo da premissa de que os problemas são os instrumentos pelos quais a Matemática sempre se desenvolveu e que resolvê-los é o que impulsiona não só o seu ensino, mas o desenvolvimento desta Ciência, o presente trabalho aborda a temática dos problemas matemáticos sob perspectiva da elaboração dos mesmos. Este material apresenta um resumo teórico sobre alguns aspectos da resolução de problemas onde buscou-se através do método heurístico organizado por George Polya e de estudos derivados da obra do autor expor alguns temas tais como a escrita matemática, os tipos de problemas, as etapas e estratégias de resolução e os elementos que caracterizam um bom problema matemático. Tópicos fundamentais que alicerçaram e instrumentalizaram uma oficina com estratégias para a elaboração de problemas matemáticos voltados para o Ensino Médio, o objeto central deste estudo, juntamente com o relato de sua aplicação em uma turma de licenciandos em Matemática.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-22T12:50:56Z No. of bitstreams: 1 texto completo.pdf: 2002096 bytes, checksum: 846f5e7b160234fc5880c038b656d3f6 (MD5) / Made available in DSpace on 2017-08-22T12:50:56Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2002096 bytes, checksum: 846f5e7b160234fc5880c038b656d3f6 (MD5) Previous issue date: 2017-03-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de flow shop scheduling não permutacional com trabalhadores heterogêneos (FSNPTH). Sendo este classificado como um problema multicomponente, uma vez que, combina dois problemas no qual o resultado de um afeta o outro. O FSNPTH é composto por dois problemas clássicos de otimização combinatória: alocação de trabalhadores em máquinas e o flow shop scheduling não permutacional (FSNP). O problema consiste em alocar trabalhadores hete- rogêneos em máquinas dispostas em série, na qual a heterogeneidade se dá pelo tempo gasto pelo trabalhador ao operar uma máquina. A alocação dos trabalha- dores definem os tempos de execução das tarefas do problema de FSNP. O objetivo do problema de FSNPTH é minimizar o tempo máximo de conclusão das tarefas, conhecido como makespan. Para resolve-lo, inicialmente é proposto a aplicação do método Proximity Search (PS) para tentar determinar soluções ótimas para o pro- blema utilizando o modelo de programação linear inteira mista 0-1 (PLIM). Esse método consiste em substituir a função objetivo por uma função de proximidade e adicionar uma restrição de corte no modelo. Iterativamente o novo modelo é resolvido e a restrição de corte é atualizada. Isso garante que PS limite o espaço de busca e identifique as soluções ótimas. Foram desenvolvidas três versões do PS denotadas por P S 1 , P S 2 e P S 2RIN S . Dado que o problema pertence à classe NP-Difícil e é considerado de difícil resolução de maneira exata, foram desenvolvi- dos dois algoritmos híbridos, VNS-IG e TS-IG, a fim de obter soluções de forma aproximada de alta qualidade em baixo tempo computacional. Esses algoritmos combinam as meta-heurísticas Variable Neighborhood Search (VNS) e Busca Tabu (TB, do inglês Tabu Search) com o Iterated Greedy (IG). Experimentos computa- cionais e análises estatísticas foram realizados a fim de comparar o desempenho das versões do PS e dos algoritmos propostos. De acordo com os experimentos computacionais, as versões do PS obtiveram melhorias na qualidade da solução obtida e redução no tempo computacional se comparado a resolução do modelo matemático pelo solver IBM ILOG CPLEX. Além disso os experimentos realiza- dos mostram que algoritmos propostos são significativamente superiores ao melhor algoritmo da literatura (Scatter Search) em relação a dois fatores: qualidade das soluções e tempo de execução. / The current work addresses the non-permutation flow shop scheduling problem with heterogeneous workers (Het-FSSP), which is defined as a multicomponent problem, since it combines two problems where the result of one affects the other. Het-FSSP consists of two classical combinatorial optimization problems: machine worker allocation and non-permutation flow shop scheduling (NPFSS). The pro- blem is to allocate heterogeneous workers in machines arranged in series, in which the heterogeneity is due to the time spent by the worker when operating a ma- chine. The allocation of workers defines the periods of execution of the jobs of the NPFSS problem. The goal of the Het-FSSP problem is to minimize the maximum job completion time, which is known as makespan. In order to solve this problem, it is initially proposed to apply the Proximity Search (PS) method to try to de- termine optimal solutions for the problem using mixed integer programing (MIP) model. This method consists of replacing the objective function with a proximity function and adding a cut-off constraint on the model. Then, by iteration, the new model is resolved and the cut restriction is updated. This ensures that PS limits the search space and identifies optimal solutions. Three PS versions denoted by P S 1 , P S 2 and P S 2RIN S have been developed. Since the problem belongs to the NP-Difficult class and is considered to be difficult to solve exactly, two hybrid algorithms, VNS-IG and TS-IG, were developed in order to obtain approximate solutions of high quality in low computational time. These algorithms combine the meta-heuristics Variable Neighborhood Search (VNS) and Tabu Search (TS) with Iterated Greedy (IG). Computational experiments and statistical analyzes were performed in order to compare the performance of PS versions and the proposed algorithms. The computational experiments results suggest that the PS versions acquired improvements in the quality of the solution obtained and also reduced computational time spent compared to the resolution of the mathematical model by the IBM ILOG CPLEX solver. In addition, the experiments performed have shown that the proposed algorithms are significantly superior to the best algorithm found in the literature (Scatter Search) in relation to two factors: solution quality and execution time.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-04-27T09:48:38Z No. of bitstreams: 1 texto completo.pdf: 1187966 bytes, checksum: 9ba7c5ee8c3eafbfbcf97aa8cf96eae5 (MD5) / Made available in DSpace on 2016-04-27T09:48:38Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1187966 bytes, checksum: 9ba7c5ee8c3eafbfbcf97aa8cf96eae5 (MD5) Previous issue date: 2015-12-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de sequenciamento de tarefas em máquinas parale- las não-relacionadas considerando restrições de precedência entre as tarefas e tempos de preparação dependentes da sequência e da máquina. Este problema tem como objetivo minimizar o tempo máximo de conclusão do sequenciamento, conhecido como makespan. Em problemas que consideram restrições de precedência, nenhuma tarefa pode iniciar seu processamento sem que todas as suas tarefas predecessoras tenham sido concluídas. Para resolver este problema foram desenvolvidos três mo- delos de programação linear inteira mista (PLIM), denotados por Modelo 1, Modelo 2 e Modelo 3. Em seguida, sete heurísticas construtivas foram desenvolvidas, deno- tadas por HC1 a HC7, as quais se diferenciam pelas regras de prioridade utilizadas. Neste trabalho também é implementado o método chamado Proximity Search (PS), que tenta determinar soluções ótimas para o problema. O método PS precisa de uma solução inicial e de um modelo base de PLIM. Neste método a função objetivo do modelo é substituída por uma função de proximidade e o conjunto de soluções viáveis é reduzido através da adição de cortes. A ideia é, iterativamente, resolver o modelo com a tentativa de melhorar a solução corrente. Foram desenvolvidas três versões do PS denotadas por P S1, P S2 e P S2RIN S . Neste trabalho também foram desenvolvidos algoritmos baseados em meta-heurísticas a fim de resolver o problema de forma aproximada. Primeiramente, foram desenvolvidas duas buscas locais denotadas por BL1 e BL2 baseadas na estratégia de inserção por vizinhança. Em seguida, foram implementadas duas meta-heurísticas: GRASP (Greedy Ran- domized Adaptive Search) e IG (Iterated Greedy). Experimentos computacionais e análises estatísticas foram realizados a fim de comparar o desempenho dos modelos, das versões do P S e das heurísticas propostas. De acordo com os experimentos, o Modelo 1 apresentou-se mais eficiente na qualidade das soluções obtidas e a heurís- tica HC7 mostrou-se mais eficiente na geração de uma solução razoavelmente boa. Além disso, as versões do PS obtiveram melhorias na qualidade da solução obtida e redução no tempo computacional gasto se comparado ao Modelo 1. Em seguida, o IG obteve desempenho significativamente melhor que o GRASP e o PS em relação à qualidade da solução final e a velocidade com que a solução corrente é melhorada. / In this work we address the scheduling problem in unrelated parallel machine with precedence constraints between the jobs and sequence-dependent and machine- dependent setup times. The objective of this problem is to minimize the maximum completion time of sequence, called makespan. The precedence constraints force a job not to be started before all its predecessors are finished. To solve this problem, we developed three models of mixed integer programming (MIP), denoted by Model 1, Model 2 and Model 3. Next, seven constructive heuristics were developed, deno- ted by HC1 to HC7, which differ in the priority rules. Also in this work, a method called Proximity Search (PS) is implemented, which tries to find optimal solutions to the problem. The method requires an initial solution and a MILP-based model. In this method, the objective function of the model is replaced by a proximity func- tion and the set of feasible solutions is reduced by the addition of cuts. The idea is to iteratively solve the model trying to improve the current solution. We deve- loped three versions of the P S denoted by P S1, P S2 and P S2RIN S . In addition, we developed algorithms based on metaheuristics to solve the problem approxima- tely. First, were developed two local searches denoted by BL1 and BL2 based on the insertion neighborhood. Next, were implemented two metaheuristics: GRASP (Greedy Randomized Adaptive Search) and IG (Iterated Greedy). Computational experiments and statistical analyzes were performed in order to compare the per- formance of models, PS versions and heuristics. According to the experiments, the Model 1 is more efficient in the quality of solutions and the HC7 heuristic is more efficient in generating a reasonably good solution. In addition, the versions of the PS obtained improvements in the quality of the obtained solution and reduction in computational time spent compared to Model 1. Then, the IG obtained significantly better performance than the GRASP and PS in relation to the quality of the final solution and the speed with which the current solution is improved.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-09-13T12:57:14Z No. of bitstreams: 1 texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) / Made available in DSpace on 2016-09-13T12:57:14Z (GMT). No. of bitstreams: 1 texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) Previous issue date: 2016-02-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A cada dia mais dados são gerados das mais diversas fontes. A extração de conheci- mento das bases de dados torna-se cada vez mais desafiadora, visto que os processos utilizados não são triviais. O agrupamento de dados usa técnicas que são capa- zes de trabalhar com dados pouco conhecidos de forma não supervisionada. Essas técnicas dividem os dados em grupos tentando capturar a estrutura presente nos dados para obter um conhecimento que servirá de ponto inicial para seu estudo. Poucos algoritmos de agrupamentos conseguem trabalhar em um contexto escalá- vel. Um dos algoritmos mais influentes no agrupamento é o k -médias, que possui complexidade linear e duas fases bem distintas, facilmente adaptada para modelos escaláveis. Porém, k -médias possui limitações, como sensibilidade à inicialização e especificação do número de grupos k, que geralmente é desconhecido. O obje- tivo desta pesquisa é estudar e desenvolver algoritmos de agrupamento para este contexto escalável. Especificamente, procura-se trabalhar com meta-heurísticas que proporcionem o agrupamento escalável sem a necessidade de especificação do nú- mero de grupos k. Essa dissertação propõe dois novos algoritmos de agrupamento que encontram um valor para k automaticamente em um modelo escalável chamado MapReduce. Adicionalmente, foi estudado um algoritmo com o mesmo propósito encontrado na literatura. Todos os algoritmos foram desenvolvidos e comparados de duas maneiras: pela sua complexidade assintótica e através de experimentos em bases artificiais e reais. Com base em testes estatísticos, foi possível verificar as principais diferenças entre a performance dos algoritmos. / Everyday more data are generated from several sources. The knowledge extraction from datasets becomes more and more challenging as the applied techniques are not trivial. Data clustering techniques are able to work with little knowledge about the data in a totally unsupervised manner. These techniques divide data into clusters trying to capture the structure of the data to obtain knowledge that will serve as a starting point for further studies. Few clustering algorithms are able to work in a scalable scenario. One of the most influential clustering algorithms is k -means, which has linear asymptotic complexity and two distinct phases, which can be easily adapted for scalable models. However, k -means has limitations such as sensitivity to initialization and previous specification of the numbers of clusters k, which is generally unknown, specially for real world scenarios. The objective of this rese- arch is to study and develop scalable clustering algorithms. Specifically, the use of meta-heuristics for scalable clustering to automatically determine the number of k clusters. This dissertation proposes two new clustering algorithms that are able to automatically find the value k in a scalable programing model called MapRe- duce. Additionally, an state-of-art algorithm from the literature has been studied and compared. All algorithms were developed and compared in two ways: based on their asymptotic complexity and through experiments in artificial and real datasets. Based on statistical tests, is was possible to find the main differences among quality and performance of all compared algorithms.