Made available in DSpace on 2014-06-11T19:26:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-10-26Bitstream added on 2014-06-13T19:33:57Z : No. of bitstreams: 1 silva_rt_me_guara.pdf: 445223 bytes, checksum: f6563e16194940a8f4f8abc7c03ac033 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / A Organização Internacional do Trabalho estima que existem cerca de 650 milhões de pessoas com deficiência em idade produtiva. No entanto, esta parcela da população possui altos índices de desemprego devido a várias barreiras. Uma alternativa para facilitar a inclusão dessas pessoas é a criação de Centros de Trabalho para pessoas com Deficiência (CTD`s) onde as pessoas com deficiência tenham a oportunidade de experimentar um ambiente de trabalho real antes de irem para um emprego “normal”. Neste tipo de ambiente, onde é impossível ao gestor prever quais trabalhadores estarão disponíveis a cada dia devido às altas taxas de absenteísmo, há a necessidade de se definir uma organização mais produtiva diariamente. Neste contexto se torna oportuna a utilização do Problema de Balanceamento de Linha e Designação de Trabalhadores (em inglês ALWABP), onde se busca minimizar o tempo de ciclo a partir de um dado número de trabalhadores, alocando tarefas às estações de trabalho e trabalhadores às estações, tendo em vista que alguns trabalhadores podem ser muito lentos para executar certas tarefas ou até incapazes, devido a alguma deficiência que eles apresentam, e muito eficientes na execução de outras. O objetivo geral desta dissertação consiste em empregar diferentes meta-heurísticas para resolver o ALWABP, comparando com os melhores resultados das instâncias encontradas na literatura. Dentre várias meta-heurísticas disponíveis na literatura foram utilizados o Harmony Search (HS), o Adaptive Large Neighborhood Search (ALNS) e o Clustering Search (CS) utilizando o HS e o ALNS como heurísticas geradoras de soluções. Cada uma das quatro implementações foram testadas em 320 instâncias propostas na literatura divididas em quatro famílias. Os experimentos computacionais mostraram bons resultados... / The International Labour Organization estimates that there are approximately 650 million disabled people in working age. However, this population presents high rates of unemployment due to numerous barriers. An alternative to facilitate the inclusion of these people is the establishment of Centers for Working People with Disabilities where people with disabilities have the opportunity to experience a real work environment before going to a “normal” job. In this type of environment, where it is impossible to predict which workers will be available each day due to high rates of absence in this population, there is a need to define a more productive organization on a daily basis. In this context it becomes appropriate to use the Assembly Line Worker Assignment and Balancing Problem (ALWABP), which seeks to minimize the cycle time for a given number of workers, assigning tasks to workstations and workers to stations, considering that some workers may be too slow to perform certain tasks, or even unable due to some deficiency they present, and very efficient in performing others. The aim of this dissertation is to employ different meta-heuristics to solve the ALWABP, comparing with the best results of instances found in the literature. Among several meta-heuristics available in the literature were used Harmony Search (HS), Adaptive Large Neighborhood Search (ALNS) and Clustering Search (CS) using the HS and ALNS as heuristics for the generation of solutions. Each of the four implementations has been tested in 320 instances proposed in the literature, classified into four families. The computational experiments showed good results, and in some instances obtaining better solution values best known. Conclusions regarding... (Complete abstract click electronic access below)

Orientador: Galeno José de Sena / Banca: Marcos Antonio Pereira / Banca: Anibal Tavares de Azevedo / Resumo: A Organização Internacional do Trabalho estima que existem cerca de 650 milhões de pessoas com deficiência em idade produtiva. No entanto, esta parcela da população possui altos índices de desemprego devido a várias barreiras. Uma alternativa para facilitar a inclusão dessas pessoas é a criação de Centros de Trabalho para pessoas com Deficiência (CTD's) onde as pessoas com deficiência tenham a oportunidade de experimentar um ambiente de trabalho real antes de irem para um emprego "normal". Neste tipo de ambiente, onde é impossível ao gestor prever quais trabalhadores estarão disponíveis a cada dia devido às altas taxas de absenteísmo, há a necessidade de se definir uma organização mais produtiva diariamente. Neste contexto se torna oportuna a utilização do Problema de Balanceamento de Linha e Designação de Trabalhadores (em inglês ALWABP), onde se busca minimizar o tempo de ciclo a partir de um dado número de trabalhadores, alocando tarefas às estações de trabalho e trabalhadores às estações, tendo em vista que alguns trabalhadores podem ser muito lentos para executar certas tarefas ou até incapazes, devido a alguma deficiência que eles apresentam, e muito eficientes na execução de outras. O objetivo geral desta dissertação consiste em empregar diferentes meta-heurísticas para resolver o ALWABP, comparando com os melhores resultados das instâncias encontradas na literatura. Dentre várias meta-heurísticas disponíveis na literatura foram utilizados o Harmony Search (HS), o Adaptive Large Neighborhood Search (ALNS) e o Clustering Search (CS) utilizando o HS e o ALNS como heurísticas geradoras de soluções. Cada uma das quatro implementações foram testadas em 320 instâncias propostas na literatura divididas em quatro famílias. Os experimentos computacionais mostraram bons resultados... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The International Labour Organization estimates that there are approximately 650 million disabled people in working age. However, this population presents high rates of unemployment due to numerous barriers. An alternative to facilitate the inclusion of these people is the establishment of Centers for Working People with Disabilities where people with disabilities have the opportunity to experience a real work environment before going to a "normal" job. In this type of environment, where it is impossible to predict which workers will be available each day due to high rates of absence in this population, there is a need to define a more productive organization on a daily basis. In this context it becomes appropriate to use the Assembly Line Worker Assignment and Balancing Problem (ALWABP), which seeks to minimize the cycle time for a given number of workers, assigning tasks to workstations and workers to stations, considering that some workers may be too slow to perform certain tasks, or even unable due to some deficiency they present, and very efficient in performing others. The aim of this dissertation is to employ different meta-heuristics to solve the ALWABP, comparing with the best results of instances found in the literature. Among several meta-heuristics available in the literature were used Harmony Search (HS), Adaptive Large Neighborhood Search (ALNS) and Clustering Search (CS) using the HS and ALNS as heuristics for the generation of solutions. Each of the four implementations has been tested in 320 instances proposed in the literature, classified into four families. The computational experiments showed good results, and in some instances obtaining better solution values best known. Conclusions regarding... (Complete abstract click electronic access below) / Mestre

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T05:53:35Z (GMT). No. of bitstreams: 1 Prado_DanielFernandoMechlin_M.pdf: 451492 bytes, checksum: 0350938f30a018718f3b59654e155a93 (MD5) Previous issue date: 2007 / Resumo: Localização de facilidades é uma das atividades da área de logística que envolve decisões do número, localização e tamanho das facilidades a serem usadas. A localização de facilidades é uma questão central no planejamento estratégico de empresas públicas e privadas e está associada à variação da população em uma região, capital de investimento e estimativa de clientes que podem ser servidos. Este trabalho aborda o problema de localização de facilidades com restrições de capacidade e fonte única para atender a demanda de clientes. A fonte única impõe que um cliente seja atendido por uma única facilidade, e o objetivo é minimizar os custos de instalação e atendimento dos clientes. Este problema tem diversas aplicações, incluindo a localização de concentradores em redes de telecomunicações. Trata-se de um problema complexo de otimização combinatória, em que métodos exatos não produzem uma solução ótima em tempo viável, e portanto o uso de métodos heurísticos é pertinente. O objetivo deste trabalho é o desenvolvimento e implementação de um algoritmo de busca tabu para o problema, e comparação de seu desempenho com outros métodos apresentados na literatura. Palavras-chave: Localização de Facilidades, Otimização Combinatória, Heurística, Busca Tabu / Abstract: Facility location is a logistic problem that involves the decision on the number, location and capacity of facilities to be opened. Facility location is an important area in the strategic planning of public and private companies and is associated with population changes, money availability for investment and the estimation of the number of customers to be served. This work addresses on single source capacitated facility location problem. Single source imposes that each customer must be assigned to only one facility, and the objective is to minimize the installation and transportation costs. This problem has several applications, including the network concentrator location problem. It is a complex combinatorial optimization problem, which cannot be solved by exact methods in small computational times; therefore, heuristics methods are indicated. The objective of this thesis is the development and implementation of a tabu search algorithm for the problem and a comparative analysis with other methods available in the literature. Keywords: Facility location, Combinatorial Optimization, Heuristic, Tabu Search / Mestrado / Automação / Mestre em Engenharia Elétrica

Understanding and characterizing the processes driving social interactions is one of the fundamental problems in social network research. A particular instance of this problem, known as link prediction, has recently attracted considerable attention in various research communities. Link prediction has many important commercial applications, e.g., recommending friends in an online social network such as Facebook and suggesting interesting pins in a collection sharing network such as Pinterest. This work is focused on the temporal link prediction problem: Given a sequence of graph snapshots G1, · ··, Gt from time 1 to t, how do we predict links in future time t + 1? To perform link prediction in a network, one needs to construct models for link probabilities between pairs of nodes. A temporal latent space model is proposed that is built upon latent homophily assumption and temporal smoothness assumption. First, the proposed modeling allows to naturally incorporate the well-known homophily effect (birds of a feather flock together). Namely, each dimension of the latent space characterizes an unobservable homogeneous attribute, and shared attributes tend to create a link in a network.

We have implemented and benchmarked an FPT-algorithm, that has two input parameters, k and w besides the input problem instance, which is a planing instance, in this thesis. The algorithm has an exponential running time as a function of these two parameters. The implemented algorithm computes the heuristic value h^+(s) of a state s that belongs to a state space, which originates from a strips instance. The purpose of the project was to test if the algorithm can be used to compute the heuristic function h^+, i.e. the delete-relaxation heuristic, in practice. The delete-relaxation heuristic value for some state is the length of the optimal solution from the state to a goal in the delete-relaxed-instance, which is the original instance without all its negative effects. Planning instances was benchmarked with the search algorithm A^* to test the algorithms practical value. The heuristic function blind was benchmarked together with A^* with the same instances so that we could compare the quality of the benchmark result for the implemented algorithm. The conclusion of the project was that the implemented algorithm is too slow to be used in practise.

Entrepreneurs have to constantly make decisions about the various opportunities available to them. Bad decisions can lead to the failure of a business while good decisions will enable the business to grow and make a positive contribution to society and the economy. Understanding how successful entrepreneurs make decisions about business opportunities will assist other entrepreneurs because this knowledge will equip them to run their own businesses more successfully. In this particular research study, twelve successful entrepreneurs were interviewed and asked about the way in which they make decisions about business opportunities. Through a process of thematic analysis, the data collected was woven into an innovative Grounded Theory that identified and explained the heuristics entrepreneurs use when making decisions about opportunities. Seven heuristics emerged from the data and were ordered according to the frequency of observation. The two most common heuristics included inputs required/outcomes desired and formal/emotional processes. The five less frequent heuristics were classified as influence, environmental factors, risk and control, commitment and balance. An additional insight that was gained through the research process was that the entrepreneurial idea itself contributes little to the overall success of the business and an “action-orientated” focus was a far better contributor to ultimate success / Dissertation (MBA)--University of Pretoria, 2013. / zkgibs2014 / Gordon Institute of Business Science (GIBS) / MBA / Unrestricted

O Problema de Minimização do Número Máximo de Pilhas Abertas (MOSP, do inglês minimization of open stacks problem) é um problema de otimização combinatória da família NP-Difícil que vem recebendo grande atenção na literatura especializada. Este trabalho apresenta novas contribuições em termos de modelos e técnicas de resolução para o problema. A primeira parte deste trabalho lidou com modelos matemáticos, sendo analisados os modelos existentes que se baseiam em programação inteira mista. Variações de um modelo da literatura foram propostas, com o objetivo de tentar diminuir o tempo de execução necessário para se obter uma solução exata com a utilização de pacotes comerciais. Os resultados mostraram que as propostas são capazes de acelerar a solução de algumas classes de instâncias mas, que de maneira geral, métodos baseados em relaxação linear encontram dificuldade em provar a otimalidade devido à baixa qualidade dos limitantes inferiores. Uma outra contribuição deste trabalho foi o desenvolvimento de um modelo conjunto para o problema MOSP e para o problema de minimização da duração de pedidos (MORP, do inglês minimization of order spread problem). Este modelo propõe um framework unificado em que os dois problemas podem ser resolvidos ao mesmo tempo, tendo suas funções objetivo individuais ponderadas através de pesos definidos pelo usuário. A segunda parte do trabalho voltou-se para o desenvolvimento de métodos heurísticos para o MOSP. Duas estratégias de solução foram desenvolvidas. O primeiro método propõe uma transformação heurística entre o problema MOSP e o clássico problema do caixeiro viajente (TSP, do inglês traveling salesman problem). A partir de uma representação em grafo do MOSP, o TSP é definido por meio de uma regra de atribuição de distâncias baseadas nos graus dos nós. Nos testes computacionais, a estratégia proposta mostrou-se eficiente em relação às heurísticas específicas para o MOSP, obtendo a solução ótima do MOSP em 80,42% das instâncias testadas e sendo competitiva em termos de tempo computacional com algumas das melhores heurísticas da literatura. O segundo método heurístico proposto utilizou a ideia de decomposição. De fato, neste método, um corte no grafo associado ao problema original divide-o em problemas menores, que são resolvidos. A solução global é obtida através da junção das soluções dos subproblemas e, em alguns casos, é possível demonstrar a otimalidade da solução obtida. Testes computacionais indicam a validade da proposta e apontam caminhos para pesquisas futuras / The minimization of open stacks problem (MOSP) is a well known NP-hard combinatorial optimization problem that has been extensively discussed in the specialized literature. This study presents some new contributions in terms of models and solution methods for this problem. The first part of this thesis dealt with mathematical models. The existing mixedinteger models have been analyzed and variants of a well known model have been proposed, with the goal of reducing the time needed by commercial packages to obtain proved-optimal solutions. The results of computational tests on a widely used set of instances have indicated that the modifications proposed are able to reduce the time needed to obtain optimal solutions for some classes of instances. Nevertheless, a conclusion has been the fact that mixed-integer programming models have difficulty in obtaining convergence due to the low quality linear relaxation bounds. Another contribution of this thesis is the proposal of a single model that is able to deal with both the MOSP and with the Minimization of Order Spread Problem (MORP). This unified framework allows both problems to be jointly solved, by using a weighted objective function that included both original objectives. The second part of this thesis dealt with the development of heuristic strategies. Two solution strategies have been proposed. The first method proposes a heuristic conversion between MOSP and Traveling Salesman Problem (TSP) instances. This conversion relies the assignment distances to the TSP instance based on the degree of the vertices of the associated MOSP graph. Computational tests have shown that the proposed methodology is efficient, both in terms of solution quality (optimal solutions were obtained for 80.42% of the tested instances) and computational effort. The second method uses a decomposition idea. A cut is made in the graph associated with the original MOSP problem, yielding two smaller problems, which are solved. In some cases, the obtained combined solution can be prover optimal. Computational tests have shown the validity of the proposal and indicate new research opportunities

We introduce a new pure integer rounding heuristic, ZI Round, and compare this heuristic to recent extremely fast pure integer rounding heuristic Simple Rounding. Simple Rounding was introduced in the non-commercial code SCIP. ZI Round attempts to round each fractional variable while using row slacks to maintain primal feasibility. We use the MIPLIB 2003 library for the test set. The average time in our run per instance for both Simple Rounding and ZI Round was 0.8 milliseconds, but ZI Round found more feasible solutions with a the same or better objective value. Also the average time to solve the lp relaxation per instance was 2.2 seconds, so these two rounding heuristics are several magnitudes faster than other heuristics which must use the lp solver, including diving heuristics.We also show that ZI Round performs well on a set covering class and a railway crew scheduling class.

Abstract Home Health Care (HHC) is a health care service delivered by sending caregivers such as nurses or personal support workers (PSW) to visit patients in their homes. The assignment of patients to nurses as well as the sequencing of patients for each nurse is called the Home Health Care Scheduling and Routing Problem (HHCSRP). This thesis proposes a heuristic approach to solve HHCSRP to which it is hard and even impossible to obtain an optimal solution for relative larger instances in a reasonable amount of computational time by using an exact algorithm as HHCSRP is NP hard. In the approach, this thesis developed and contributed a heuristic partition method to partition patients into a number of single nurse groups. The computational test result shows that the proposed approach can achieve good solutions which remain within 5% of the commercial solver CPLEX’s best solution using an acceptable solution time on all test instances.

Bayesian networks are a widely used graphical model which formalize reasoning under uncertainty. Unfortunately, construction of a Bayesian network by an expert is timeconsuming, and, in some cases, all expertsmay not agree on the best structure for a problem domain. Additionally, for some complex systems such as those present in molecular biology, experts with an understanding of the entire domain and how individual components interact may not exist. In these cases, we must learn the network structure from available data. This dissertation focuses on score-based structure learning. In this context, a scoring function is used to measure the goodness of fit of a structure to data. The goal is to find the structure which optimizes the scoring function. The first contribution of this dissertation is a shortest-path finding perspective for the problem of learning optimal Bayesian network structures. This perspective builds on earlier dynamic programming strategies, but, as we show, offers much more flexibility. Second, we develop a set of data structures to improve the efficiency of many of the integral calculations for structure learning. Most of these data structures benefit our algorithms, dynamic programming and other formulations of the structure learning problem. Next, we introduce a suite of algorithms that leverage the new data structures and shortest-path finding perspective for structure learning. These algorithms take advantage of a number of new heuristic functions to ignore provably sub-optimal parts of the search space. They also exploit regularities in the search that previous approaches could not. All of the algorithms we present have their own advantages. Some minimize work in a provable sense; others use external memory such as hard disk to scale to datasets with more variables. Several of the algorithms quickly find solutions and improve them as long as they are given more resources. Our algorithms improve the state of the art in structure learning by running faster, using less memory and incorporating other desirable characteristics, such as anytime behavior. We also pose unanswered questions to drive research into the future.