Master of Science / Department of Computing and Information Sciences / Gurdip Singh / Wireless sensor networks are characterized by severe energy constraints, one to many flows and low rate redundant data. Most of the routing algorithms for traditional networks are address centric, and the ad hoc nature of wireless sensor network makes them unsuitable for practical applications. Also the algorithms designed for mobile ad hoc networks are unsuitable for wireless sensor networks due to severe energy constraints that require nodes to perform for months with limited resources, as well as the low data rate which the constraint implies. This thesis examines a model driven data gathering algorithm framework for wireless sensor networks. It was designed with a goal to decrease the overall cost in transmission by lowering the number of messages transmitted in the network. A combination of data- centric and address-centric approaches was used as guidelines during the design process. A shortest path heuristic where intermediate nodes forward interest messages whenever it is of lower cost is one of the heuristics used. Another heuristic used is the greedy incremental approach to build a lower cost tree from a graph with various producers and consumers. A cost division heuristic is used to divide cost of shared path into distinct paths as the path forks in a tree. This thesis analyzes the effects of these heuristics on the performance of the algorithm and how it lowers the overall cost with the addition of each heuristic.

[pt] O Team Orienteering Problem é um problema de roteamento de veículos sobre um grafo com durações associadas aos arcos e prêmios atribuídos à visitação de cada vértice. Neste problema, considera-se que as visitas são realizadas por uma frota com um número fixo de veículos idênticos e que existe uma duração total máxima para as rotas serem finalizadas. Cada vértice pode ser visitado no máximo uma vez, não havendo obrigatoriedade de se visitar todos os vértices, devido à restrição que limita o tempo m´aximo de duração das rotas. O objetivo do problema é maximizar o prêmio total ganho por todas as rotas. Neste trabalho, foram propostas duas abordagens: uma exata e uma heurística. Na abordagem exata, foi desenvolvida uma formulação baseada em arcos e uma formulação estendida na qual cada arco tem um índice extra. Esse índice representa o tempo de partida de um veículo ao percorrer o arco. Através de transformações sobre a formulação estendida, foi obtida uma formulação, cuja relaxação, problema mestre restrito, foi resolvida pela técnica de geração de colunas. O subproblema de geração de colunas foi resolvido por programação dinâmica em tempo pseudo-polinomial. Este algoritmo gera rotas não elementares, que são rotas nas quais subciclos são permitidos. Com o objetivo de eliminar os subciclos das rotas não elementares, uma nova classe de desigualdades denominada min cut foi proposta. Aplicando-se um algoritmo Branch-Cut-and-Price (BCP) foram obtidos alguns novos limites superiores. A abordagem exata obteve resultados competitivos quando comparada ao melhor algoritmo exato já proposto para esse problema. Na abordagem heurística, além de uma vizinhança k-opt, foi explorada também uma busca elipsoidal que adiciona um corte à formulação do algoritmo Branch-Cut-and-Price. Esse novo corte reduz o espa¸co de busca a uma vizinhança em torno de um conjunto de soluções conhecidas. Essa busca é utilizada como um operador de crossover executado em todas as iterações de um algoritmo evolutivo. Essa abordagem converge em um tempo computacional razoável e encontra soluções ótimas ou próximas da ótima para algumas instâncias da literatura. / [en] Team Orienteering Problem is a vehicle routing problem on a graph with durations associated to the arcs and profits assigned to visiting the vertices. In this problem, a fleet with a fixed number of identical vehicles performs the visitations and there is a limited total duration for the routes to be ended up. Each vertex can be visited at most once and the solution does not have the obligation to visit all vertices, due to the constraint that limits the maximum duration of routes. The goal of the problem is to maximize the total profit gathered by all routes. In this work, two approaches have been proposed: an exact and a heuristic one. In the exact approach, we have developed an arc based formulation and an extended formulation where each arc has an extra index. This index represents the departure time of a vehicle using an arc. Through transformations on the extended formulation, we have obtained a formulation, whose relaxation - the restricted master problem - is solved using the column generation technique. A dynamic programming algorithm solves the column generation subproblem in pseudo-polynomial time. This algorithm generates non-elementary routes that allow subcycles. In order to cut off the subcycles, a new class of inequalities called min cut has been proposed.We have applied a Branch-Cut-and-Price (BCP) algorithm. This allowed finding some new upper bounds. The exact approach has achieved competitive results compared to the best exact algorithm has already proposed to this problem. In the heuristic approach, besides a kopt neighborhood, we have also exploited an ellipsoidal search that adds a new cut constraint to the formulation of Branch-Cut-and-Price algorithm. This new cut reduces the space search to a neighborhood around a known set of solutions. This search is used as a crossover operator that runs all iterations of a evolutive algorithm. This approach converges in a reasonable computational time and finds optimal or near optimal solutions for some instances in the literature.

A mobile robot needs to know its pose (position and orientation) in order to navigate and perform useful tasks. The problem of determining this pose with respect to a global or local frame is called localisation, and is a key component in providing autonomy to mobile robots. Thus, localisation answers the question Where am I? from the robot’s perspective. Localisation involving a single robot is a widely explored and documented problem in mobile robotics. The basic idea behind most documented localisation techniques involves the optimum combination of noisy and uncertain information that comes from various robot’s sensors. However, many complex robotic applications require multiple robots to work together and share information among themselves in order to successfully and efficiently accomplish certain tasks. This leads to research in collaborative localisation involving multiple robots. Several studies have shown that when multiple robots collaboratively localise themselves, the resulting accuracy in their estimated positions and orientations outperforms that of a single robot, especially in scenarios where robots do not have access to information about their surrounding environment. This thesis presents the main theme of most of the existing collaborative, multi-robot localisation solutions, and proposes an alternative or complementary solution to some of the existing challenges in multirobot localisation. Specifically, in this thesis, a heuristically tuned Extended Kalman Filter is proposed to localise a group of mobile robots. Simulations show that when certain conditions are met, the proposed tuning method significantly improves the accuracy and reliability of poses estimated by the Extended Kalman Filter. Real world experiments performed on custom-made robotic platforms validate the simulation results.

Em uma cadeia produtiva de minério, as operações de pátio de estocagem, principalmente as de recuperação de pilhas de minério, exercem um papel fundamental por vincularem os processos de beneficiamento e de transporte. Com esta finalidade, esta dissertação propõe o sequenciamento das pilhas de minério a serem recuperadas através da adaptação de heurísticas trazidas pela literatura. Primeiramente, propõe-se uma heurística de sequenciamento para a retomada de pilhas de minério (entendidas como tarefas a serem sequenciadas) nos seus respectivos pátios através da aplicação de um índice de priorização de pilhas (IP). Tal índice apoia-se em fatores relevantes para as operações de pátios de estocagem, como capacidade das recuperadoras, qualidade e tempo de residência do minério e tempo de deslocamento entre pilhas (setup). A segunda heurística proposta, ATCSM (Apparent Tardiness Cost with Setups for mineral recovery), modifica a regra de despacho ATCS (Apparent Tardiness Cost with Setups) com vistas à sua aplicação na retomada de pilhas de minério em pátios de recuperação. O ATCSM apoia-se em fatores tidos como relevantes para as operações de pátios de estocagem, como tempo disponível para o empilhamento de um produto e data de entrega de uma pilha, entre outros. Os métodos propostos foram aplicados em um sistema de recuperação de minério composto por dois pátios, duas máquinas recuperadoras e doze pilhas. As sequências de recuperação geradas pelas heurísticas propostas foram consideradas coerentes por especialistas de pátio de estocagem de uma empresa mineradora. / In the supply chain of ore operations, stockyard operations, mainly the recovery of ore piles, play a fundamental role between beneficiation and transport processes. This thesis proposes new scheduling heuristics for sequencing ore piles recovering order. The first heuristics proposes a pile prioritization index (IP) that relies on relevant factors for stockyards operations, including machines capability, ore quality and residence time, and travel time between piles (setup). With similar purposes, the second heuristics modifies the dispatching rule ATCS (Apparent Tardiness Cost with Setups), yielding the ATCSM (Apparent Tardiness Cost with Setups for mineral recovery). The proposed ATCSM also relies on factors regarded as relevant to stockyard operations, as time available for stacking of a product and piles due date, among others. The proposed methods were applied to an ore recovery system composed of two stockyards, two recovery machines and twelve piles. The recovery sequences generated by both heuristics were considered consistent by experts from a mining company.

Este trabalho lida com o problema de balanceamento e sequenciamento de linhas de produção multi-modelo com trabalhadores deficientes, uma generalização de dois importantes problemas da literatura de linhas de produção: o Problema de Balanceamento de Linhas de Produção Multi-Modelo (MALBP) e o Problema de Balanceamento e Designação de Trabalhadores em Linhas de Produção (ALWABP). O MALBP tem sido particularmente importante nas últimas décadas, onde, em um cenário de maior competividade, cresce a necessidade de produção em larga escala de produtos customizados. O ALWABP, por sua vez, é de grande importância em Centros de Trabalhadores com Deficiências (CTDs), onde é necessário considerar as competências individuais de cada trabalhador, que se revelam nos diferentes tempos de execução de uma tarefa, segundo o trabalhador escolhido. Ao nosso conhecimento, nenhum estudo se dedicou a resolver estes dois problemas conjuntamente. Nesta dissertação, propomos modelos lineares para os problemas de balanceamento e sequenciamento de linhas de produção multi-modelo em CTDs. Para o problema de sequenciamento, limitantes inferiores e superiores e métodos heurísticos de resolução são desenvolvidos e discutidos. Testes computacionais foram efetuados e os resultados sugerem que os métodos desenvolvidos são eficientes / This study addresses the Mixed Assembly Line and Worker Assignment Balancing Problem, which generalizes two classical problems in the assembly line literature: the Mixed Assembly Line Balancing Problem (MALBP) and the Assembly Line Worker Assignment and Balacing Problem (ALWABP). The MALBP has been considered particularly important in the last two decades, when, in the context of more competitive scenarios, there is a growing need of producing customized products in large scale. On the other hand, the ALWABP is of interest in Sheltered Work centers for the Disabled (SWD). In this situation, we must consider each worker individual abilities, which results in task duration times that are dependent on the workers selected for their execution. To the best of our knowledge, there has been no effort to solve these problems jointly. We propose linear models for both balancing and sequencing multimodels assembly lines commonly found in SWD. Lower and upper bounds and also heuristic methods are proposed and discussed for the sequencing problem. The results obtained by computational experiments suggest the heuristic methods can efficiently solve the MALWABP

This thesis explores boosting to improve decision-making in the context of the COVID-19 pandemic using a structured introspection. Structured introspection is an intervention where individuals are prompted with and are asked to estimate the importance of a set of attributes relevant to the decision in order to limit the prevalence of potential cognitive biases. To test the intervention, 281 participants divided into an intervention and control group answered an online survey with a dilemma about COVID-19. The dilemma was whether Sweden should shut down the economy or keep it open during the COVID-19 pandemic. The intervention group was asked to rate how important the attributes “saving lives”, “saving the economy”, “concern for the health of the elderly and risk groups”, and “concern for the quality of life and well-being of all citizens” should be for their decision. The control group was only prompted with the question and asked to think carefully. All participants were asked a set of control variables such as risk perception for self and others and emotions when thinking about COVID-19. The results did not show a significant influence on choice on decisions based on the intervention. They did however show a significant correlation with choice on risk perception as well as a correlation between choice on the dependent variable and the attributes in the intervention group.             The conclusion of the thesis is that structured introspection may not be suitable on a contemporary issue affecting participants directly, as they may already have strong opinions about the issue. Further and broader research needs to be conducted to determine in which circumstances this boost can be effective.

Democracy in the United States operates under two contradictory norms: that it is a civic duty to vote, and that it is irresponsible to cast an uninformed vote. Do these contrasting norms suppress voter turnout? Why do some uninformed Americans turn out to vote while others do not? This study seeks to understand the information barriers that Americans perceive to be in the way of voting by studying how voters and nonvoters differ in their perceptions of the importance of various heuristics. By analyzing a 2012 Cooperative Congressional Election Study survey question that measures respondents’ prioritization of these information shortcuts, this study is able to understand how the prioritization of certain heuristics is associated with turnout rates. I find that high prioritization of the partisan identification heuristic and the heuristic based on the candidate a respondent’s friend supports is associated with higher turnout rates. I argue that this is because of the density of information offered by each heuristic and their usefulness in aiding in the decision-making process for potential voters. I conclude that perception of the usefulness of heuristics matters to turnout, and that this is a start to understanding how information costs may hinder turnout where it would otherwise exist.

The planning process of public transit systems have for long been a subject treated in operations research. In recent years, research within the public transit area focus on adapting this planning process for electric vehicles. This thesis evaluates a heuristic approach to the vehicle scheduling problem for electrical buses without the use of any licensed software. Among the previous research is an article that presents a mathematical model for scheduling of electrical buses using AMPL and CPLEX. However, due to not finding optimal solutions for all instances of the problem, the question of a heuristic approach is raised. Literature studies indicate that large neighbourhood search (LNS)-based heuristics have shown previous success for scheduling of vehicles. Results from the implementation of a constructive heuristic combined with an LNS-heuristic are compared with the results from the mathematical model and CPLEX. We see some success using the heuristic approach. However, the method we compare against still provide better solutions for almost all instances. More specifically, the difference between the results (number of buses needed) increases with an increasing complexity of the problem. Finally, due to the lacking results, some recommendations are given for improving the performance of the heuristic.

Maintaining composition studies and creative writing as discrete disciplines may not be in the best interests of either field. But so long as the majority of scholars and practitioners of either field remain largely uninformed about one another, it is unlikely that any progress toward conjoining the two fields will occur. Various important and constructive efforts have been made for more than thirty years to establish a scholarly, interdisciplinary community that dedicates itself to examining points of intersection between composition and creative writing. Initially, such efforts appear to attract the attention from the broader communities of each discipline. Before long, however, participation in such scholarly discussions diminishes, as do most prospects for integrating changes inspired by the collaborative exchange-let alone any prospects for merging composition studies and creative writing into a single discipline. Critical examinations of commonalities between composition studies and creative writing, while crucially important, cannot lead to a greater alliance between the two fields unless each field incorporates aspects of one another's disciplinary identity into its own. Chapter One introduces my study and considers the disciplinary histories of composition and creative writing, histories that reveal when and how they came to be separated even as they consistently were (and are) situated in the same department, the department of English. Chapter Two investigates how inventional techniques that have been conceptualized primarily in the field of composition studies can assist creative writing students in developing insights about their writing. Chapter Three extends this conversation by considering the social and collaborative techniques that can benefit the creative writing workshop. Chapter Four considers how a writing classroom can integrate genres traditionally associated with either composition or creative writing to allow students to develop a broader writing repertoire and, perhaps, an enhanced commitment to its continued development.

<p>My dissertation forges a response that continues and expands discussions of entrepreneurialism in the 21^st century. I seek to answer Welter and colleagues’ call to embrace the entrepreneurial diversity offered by the folks that are embedded in local communities. I argue for a reframing of entrepreneurship that acknowledges the work of everyday-entrepreneurs — people that operate in mundane contexts, beyond capitalist agendas, guided by socially aware objectives seeking to promote equity for the greater good. This undertaking is stretched across a three part study informed by feminist perspectives. Tracing the narratives belonging to women of historically marginalized identities reveals not only the exclusionary aspects of mainstream entrepreneurship, but also the innovative practices these women embody as they balance the social variables of identity politics within and across their communities. The participants of this study demonstrate entrepreneurial citizenship, a term I propose as the many ways everyday-entrepreneurs contribute to world-building and history-making for each of the different communities they belong to. Chapter one establishes the exigence for this work and provides commentary on the cultural framework from which entrepreneurship emerged. Chapter two offers a survey of the surrounding literature, and addresses how a bridging of interdisciplinary gaps helps scholars better understand everyday-entrepreneurship. Chapter three presents a case for taking an interdisciplinary approach towards diversifying entrepreneurial scholarship. Chapter four outlines the study design, methods, and methodology. In Chapter five, I present empirical observations that quantify the qualitative data collected for the study. And, finally, chapter six presents participant profiles in conjunction with case study vignettes that highlight snapshots of everyday-entrepreneurship in practice. Ultimately, this project seeks to show that there is much to be learned from the lived realities of everyday-entrepreneurs; widening discourse on entrepreneurship to include these individuals: (1) dismantles grand narratives of entrepreneurship that are intrinsically oppressive, especially for those with intersectional identities, (2) exposes interlocking forms of oppression operating within the obscure, shadowed margins of familiar spaces that render individuals invisible, (3) contributes to new models of entrepreneurial identity, and (4) diversifies entrepreneurial scholarship. </p> @font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-536870145 1107305727 0 0 415 0;}@font-face {font-family:"Times New Roman \(Body CS\)"; panose-1:2 2 6 3 5 4 5 2 3 4; mso-font-alt:"Times New Roman"; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:auto; mso-font-signature:0 0 0 0 0 0;}@font-face {font-family:"Malgun Gothic"; panose-1:2 11 5 3 2 0 0 2 0 4; mso-font-charset:129; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-1879048145 701988091 18 0 524289 0;}@font-face {font-family:"\@Malgun Gothic"; mso-font-charset:129; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-1879048145 701988091 18 0 524289 0;}p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0in; line-height:150%; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman",serif; mso-fareast-font-family:"Malgun Gothic"; mso-fareast-theme-font:minor-fareast; mso-bidi-font-family:"Times New Roman \(Body CS\)"; color:black; mso-themecolor:text1; mso-fareast-language:KO;}.MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; mso-fareast-font-family:"Malgun Gothic"; mso-fareast-theme-font:minor-fareast; mso-bidi-font-family:"Times New Roman \(Body CS\)"; color:black; mso-themecolor:text1; mso-fareast-language:KO;}.MsoPapDefault {mso-style-type:export-only; line-height:150%;}div.WordSection1 {page:WordSection1;}