Este trabalho aborda o problema de no-wait flowshop em um ambiente com custos de setup apartados dos tempos de processamento, são investigados os casos de setups dependentes e independentes da seqüência para makespan e total flowtime. Diversas aplicações práticas podem ser modeladas sob estas suposições, dentre elas destacamos a indústria química e alimentícia. É proposta uma metaheurística evolutiva baseada em algoritmo genético e clustering search e seus resultados são comparados com os métodos de Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) através dos bancos de dados de Ruiz e Stützle (2008) e Ruiz e Allahverdi (2007). Os métodos são avaliados segundo o percentual de sucesso e desvio relativo médio. Os resultados obtidos demonstram a superioridade do método proposto para problemas de grande porte. / This work intends to research the no-wait flowshop scheduling problem with setup times separated from the processing costs; the both cases where the sequence is dependent and independent are targeted for makespan and total flowtime. There are numerous practical situations that can be modeled under these assumptions, such as, chemical industry, food processing, etc. A hybrid metaheuristic method based on a genetic algorithm and clustering search is proposed and its results are compared to the methods of Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) using the data base from Ruiz e Stützle (2008) and Ruiz e Allahverdi (2007). The methods are evaluated as regarding the success rate and average relative deviation. The results show that the proposed method delivers better solutions for problems with higher complexity.

Este trabalho aborda o problema de no-wait flowshop em um ambiente com custos de setup apartados dos tempos de processamento, são investigados os casos de setups dependentes e independentes da seqüência para makespan e total flowtime. Diversas aplicações práticas podem ser modeladas sob estas suposições, dentre elas destacamos a indústria química e alimentícia. É proposta uma metaheurística evolutiva baseada em algoritmo genético e clustering search e seus resultados são comparados com os métodos de Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) através dos bancos de dados de Ruiz e Stützle (2008) e Ruiz e Allahverdi (2007). Os métodos são avaliados segundo o percentual de sucesso e desvio relativo médio. Os resultados obtidos demonstram a superioridade do método proposto para problemas de grande porte. / This work intends to research the no-wait flowshop scheduling problem with setup times separated from the processing costs; the both cases where the sequence is dependent and independent are targeted for makespan and total flowtime. There are numerous practical situations that can be modeled under these assumptions, such as, chemical industry, food processing, etc. A hybrid metaheuristic method based on a genetic algorithm and clustering search is proposed and its results are compared to the methods of Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) using the data base from Ruiz e Stützle (2008) and Ruiz e Allahverdi (2007). The methods are evaluated as regarding the success rate and average relative deviation. The results show that the proposed method delivers better solutions for problems with higher complexity.

The amount of data generated is on rise due to increased demand for fields like IoT, smart monitoring applications, etc. Data generated through such systems have many distinct characteristics like continuous data generation, evolutionary, multi-source nature, and heterogeneity. In addition, the real-world data generated in these fields is largely unlabelled. Clustering is an unsupervised learning technique used to group, analyze and interpret unlabelled data. Conventional clustering algorithms are not suitable for dealing with data having previously mentioned characteristics due to memory and computational constraints, their inability to handle concept drift, distributed location of data. Therefore novel clustering approaches capable of analyzing and interpreting evolving and/or multi-source streaming data are needed.  The thesis is focused on building evolutionary clustering algorithms for data that evolves over time. We have initially proposed an evolutionary clustering approach, entitled Split-Merge Clustering (Paper I), capable of continuously updating the generated clustering solution in the presence of new data. Through the progression of the work, new challenges have been studied and addressed. Namely, the Split-Merge Clustering algorithm has been enhanced in Paper II with new capabilities to deal with the challenges of multi-view data applications. A multi-view or multi-source data presents the studied phenomenon/system from different perspectives (views), and can reveal interesting knowledge that is not visible when only one view is considered and analyzed. This has motivated us to continue in this direction by designing two other novel multi-view data stream clustering algorithms. The algorithm proposed in Paper III improves the performance and interpretability of the algorithm proposed in Paper II. Paper IV introduces a minimum spanning tree based multi-view clustering algorithm capable of transferring knowledge between consecutive data chunks, and it is also enriched with a post-clustering pattern-labeling procedure.  The proposed and studied evolutionary clustering algorithms are evaluated on various data sets. The obtained results have demonstrated the robustness of the algorithms for modeling, analyzing, and mining evolving data streams. They are able to adequately adapt single and multi-view clustering models by continuously integrating newly arriving data.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-10-31T20:55:43Z No. of bitstreams: 1 eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5) / Made available in DSpace on 2017-10-31T20:55:43Z (GMT). No. of bitstreams: 1 eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5) Previous issue date: 2017-07-19 / Freight railways are the major means of transportation of bulk material, such as iron ore from the origin to the destination. Usually for heavy haul railways, the destination is a port. For the last few years there has been a fast growing demand. However, railway infrastructure capacity increasing is very expensive and require a lot of investiment budget. Therefore, an improvement of train scheduling process is needed to ensure the best and efficient use of the current railway. Nevertheless, in some situations it is overwhelmingly complex to solve, an NP-hard problem. Since all the previous work provided on the Train Timetable Problem is usually only applied locally to a single railway, this work provides a public base benchmark of test railways built by heuristcs. Moreover, this work deals with the train timetabling problem applied to mixed traffic railways with both cargo trains and passenger trains sharing the same resources with different priorities. It is proposed a new mathematical model extended from literature previous work intended to avoid infeasible solutions instead reparing or discarding on these cases. This model contains additional support for parallel multi-track for several railway’s signaling system approaches context as well as overtaking on it without deadlocks possibility. This model considers trains in current position and future departure planned. To achieve an improved train scheduling is applied the Evolutionary Clustering Search (ECS) with multi heuristics approaches and a modified mutation operator of Genetic Algorithm as component of ECS. The experiments shows ECS outperforms almost all tests scenario and the modified mutation operator strongly improve the results / Ferrovias de trens de carga são os principais meios de transporte de materiais, tais como minério de ferro, da sua origem até o seu destino. Geralmente para ferrovias de transporte pesado, o destino é o porto. Nos últimos anos, a demanda de produção tem aumentado assim como o uso da ferrovia para transportá-la, no entanto, a expansão da sua infraestrutura requer um grande investimento. Assim, um planejamento de circulação de trens mais efetivo que maximize a capacidade de tráfego se faz necessária. No entanto, em algumas situações a sua otimização é bastante complexa para ser executada, um problema NP-Difícil. Embora todo trabalho elaborado nesse tema é geralmente aplicado localmente em uma única ferrovia, este trabalho provê uma base genérica de ferrovias gerado por heurísticas. Além disso, esta dissertação lida com o problema de circulação de trens aplicado a ferrovias mistas envolvendo trens de carga assim como trens de passageiros compartilhando o mesmo recurso e com diferentes prioridades. É proposto um novo modelo matemático estendido de um trabalho existente na literatura que procura evitar conflitos ao invés de permitir soluções inviáveis, sendo necessário reparação delas ou descarte. Este modelo lida com uma quantidade variável de linhas em locais de parada compatível com várias abordagens de sistema de sinalização disponíveis, assim como considera ultrapassagens de forma a evitar deadlocks, da mesma forma que trata contextos de trens em circulação como planejados para realizar a otimização. Para encontrar boas soluções, ao planejamento de circulação de trens é aplicado uma abordagem do Evolutionary Clustering Search (ECS) com múltiplas heurísticas, e um operador de mutação modificado do Algoritmo Genético como componente do ECS. Os experimentos computacionais mostraram que o ECS superou quase todos os cenários de teste e o operador de mutação modificado melhorou significativamente os resultados finais.

Evolutionary clustering (EC) is a kind of clustering algorithm to handle the noise of time-evolved data. It can track the truth drift of clustering across time by considering history. EC tries to make clustering result fit both current data and historical data/model well, so each EC algorithm defines snapshot cost (SC) and temporal cost (TC) to reflect both requests. EC algorithms minimize both SC and TC by different methods, and they have different ability to deal with a different number of cluster, adding/deleting nodes, etc.Until now, there are more than 10 EC algorithms, but no survey about that. Therefore, a survey of EC is written in the thesis. The survey first introduces the application scenario of EC, the definition of EC, and the history of EC algorithms. Then two categories of EC algorithms model-level algorithms and data-level algorithms are introduced oneby-one. What’s more, each algorithm is compared with each other. Finally, performance prediction of algorithms is given. Algorithms which optimize the whole problem (i.e., optimize change parameter or don’t use change parameter to control), accept a change of cluster number perform best in theory.EC algorithm always processes large datasets and includes many iterative data-intensive computations, so they are suitable for implementing on Spark. Until now, there is no implementation of EC algorithm on Spark. Hence, four EC algorithms are implemented on Spark in the project. In the thesis, three aspects of the implementation are introduced. Firstly, algorithms which can parallelize well and have a wide application are selected to be implemented. Secondly, program design details for each algorithm have been described. Finally, implementations are verified by correctness and efficiency experiments. / Evolutionär clustering (EC) är en slags klustringsalgoritm för att hantera bruset av tidutvecklad data. Det kan spåra sanningshanteringen av klustring över tiden genom att beakta historien. EC försöker göra klustringsresultatet passar både aktuell data och historisk data / modell, så varje EC-algoritm definierar ögonblicks kostnad (SC) och tidsmässig kostnad (TC) för att reflektera båda förfrågningarna. EC-algoritmer minimerar både SC och TC med olika metoder, och de har olika möjligheter att hantera ett annat antal kluster, lägga till / radera noder etc.Hittills finns det mer än 10 EC-algoritmer, men ingen undersökning om det. Därför skrivs en undersökning av EC i avhandlingen. Undersökningen introducerar först applikationsscenariot för EC, definitionen av EC och historien om EC-algoritmer. Därefter introduceras två kategorier av EC-algoritmer algoritmer på algoritmer och algoritmer på datanivå en för en. Dessutom jämförs varje algoritm med varandra. Slutligen ges resultatprediktion av algoritmer. Algoritmer som optimerar hela problemet (det vill säga optimera förändringsparametern eller inte använda ändringsparametern för kontroll), acceptera en förändring av klusternummer som bäst utför i teorin.EC-algoritmen bearbetar alltid stora dataset och innehåller många iterativa datintensiva beräkningar, så de är lämpliga för implementering på Spark. Hittills finns det ingen implementering av EG-algoritmen på Spark. Därför implementeras fyra EC-algoritmer på Spark i projektet. I avhandlingen införs tre aspekter av genomförandet. För det första är algoritmer som kan parallellisera väl och ha en bred tillämpning valda att implementeras. För det andra har programdesigndetaljer för varje algoritm beskrivits. Slutligen verifieras implementeringarna av korrekthet och effektivitetsexperiment.

Yes / In dealing with big data, we need effective algorithms; effectiveness that depends, among others, on the ability to remove outliers from the data set, especially when dealing with classification problems. To this aim, support vector finder algorithms have been created to save just the most important data in the data pool. Nevertheless, existing classification algorithms, such as Fuzzy C-Means (FCM), suffer from the drawback of setting the initial cluster centers imprecisely. In this paper, we avoid existing shortcomings and aim to find and remove unnecessary data in order to speed up the final classification task without losing vital samples and without harming final accuracy; in this sense, we present a unique approach for finding support vectors, named evolutionary Pentagon Support Vector (PSV) finder method. The originality of the current research lies in using geometrical computations and evolutionary algorithms to make a more effective system, which has the advantage of higher accuracy on some data sets. The proposed method is subsequently tested with seven benchmark data sets and the results are compared to those obtained from performing classification on the original data (classification before and after PSV) under the same conditions. The testing returned promising results.