As cultural diversity continues to increase in U.S. urban centers, and indeed throughout the country, it becomes increasingly important to promote interaction between people of different backgrounds. Many forms of interaction, from simply seeing, to intimate conversation can increase our familiarity and acceptance of cultural differences. In addition, a greater understanding of these differences can lead to communities with a strong sense of togetherness and a vibrancy of local place. As a means of achieving this outcome, this thesis identifies ways in which urban park spaces can promote social interaction between different cultural groups and how these methods can then be used to develop a community gathering place that is welcoming to all. This thesis has developed a unique Social Space Organizational Model based on literature review findings relative to multi-cultural urban park and social space development. The model serves as a foundational framework for the creation of a collection of social spaces that function to accommodate the diverse ways in which different cultural groups use urban park spaces, as well as to provide opportunities for shared experiences that encourage community gathering and interaction between groups. Additionally, the model suggests an interconnectivity of various park spaces that promote a unified social experience throughout the park. Case studies of urban parks designed for use as social gathering places were analyzed against the model. Literature review findings on character qualities associated with social spaces as valued by multiple cultural groups were also explored in the case studies to identify design elements that encourage social interaction and foster positive experiences. Ultimately, these findings led to the creation of a neighborhood social gathering place that is welcoming to many different cultural groups and encouraging of community gathering and togetherness. The design engages multiple community groups by creating a park that is accomodative to a range of needs and uses as valued by different groups. Additionally, the design incorporates a diverse range of social opportunities and experiences that maintain flexibility in their ability to provide for individual as well as community based social experiences. / Master of Landscape Architecture

Executive functions (EFs) are foundational skills that predict academic success and develop rapidly between 3-6 years of age. By kindergarten entry, low socioeconomic status (SES) children have worse EF compared to their high SES peers. However, the nature and origins of these emerging performance gaps have not been systematically assessed. Further, little is known about the neural underpinnings of behavioral EF differences. This project assessed behavioral and neural EF measures in a socioeconomically diverse sample of children aged 4.5 to 5.5 years (N=121). The aims were to examine (1) how SES relates to multiple dimensions of EF, (2) contextual factors that may buffer EF from the impact of SES, and (3) how SES relates to neural EF processing. In study 1, I hypothesized that lower SES children would have worse EF; would especially struggle on harder working memory trials; and would show a steeper decline in performance over time compared to higher SES peers. As hypothesized, lower SES related to overall poorer EF (inhibitory control and working memory tasks). Contrary to expectations, there were no SES differences on holding two items in working memory, but lower SES children had poorer accuracy than higher SES peers when asked to remember just one item. Further, all children’s accuracy declined over time, regardless of SES. Study 2 used a bioecological approach to assess factors that may buffer children from adverse consequences of SES on EF. As hypothesized, results suggest that neighborhood quality has a buffering effect, as there was no relation between SES and child EF in low chaos neighborhoods. In high chaos neighborhoods, lower SES related to poorer EF. Study 3 examined how specific aspects of SES related to electrophysiological EF processing. As hypothesized, on an inhibitory control task, higher household income related to larger P3b amplitudes, indexing inhibition and attention allocation processes. This suggests that children from higher income families may show more mature neural processing. Unexpectedly, parent education did not relate to P3b amplitudes. Taken together, results highlight the importance of using multi- method approaches at different levels of analysis to tease apart the complexity of SES-EF relations in early childhood.

The word "context" originates in "contextus", which is Latin for "weaving." An architectural question arises as to how a building can so integrate itself with a community that is it truly woven into the urban fabric. The Shaw Neighborhood branch of the District of Columbia Public Library system closed in 2004. The building at the intersection of 7th Street and Rhode Island Avenue could no longer serve the needs of the community, and shall be replaced by a new facility on the same site. What are the needs of the community that should be addressed, and by what methods? As a civic building, what role will the new library play beyond that of a place to find books? What are the contexts that the new architecture will confront, and how does this building transcend the contexts of the present to endure as something equally valuable in the future? / Master of Architecture

In contemporary urban housing, the essence of social connection often struggles to thrive. Amidst the bustling city life, a profound sense of disconnection prevails, highlighting the limitations of traditional apartment living. Many individuals experience isolation and loneliness, yearning for social bonds with their neighbors. Modern apartment complexes, characterized by confined and unwelcoming shared spaces, fail to foster these crucial interactions. This thesis explores the cultural and structural factors contributing to this sense of isolation. Conventional living arrangements, with their impersonal spaces, serve as barriers rather than bridges to meaningful interaction. As fleeting encounters in blank hallways become the norm, a pervasive sense of disconnection undermines the fabric of communal well-being. Central to this study is the transformation of common spaces within apartment buildings into vibrant social hubs. By challenging conventional architectural norms, the project aims to create environments that encourage spontaneous encounters and meaningful connections among residents. Through thoughtful design interventions, such as emphasizing the idea of thresholds between private and communal spaces, the project seeks to blur the boundaries between individual living units and foster a collective sense of belonging. Emphasizing inclusivity, the project targets diverse resident groups, from families to students, to enhance community understanding and cohesion. The objective is to redefine physical spaces within apartment buildings and cultivate a sense of community that enriches residents' living experiences and overall well-being in urban environments. Through innovative design and a commitment to fostering social bonds, this project aims to create a blueprint for urban living that transcends the limitations of traditional apartment complexes. / I moderna urbana bostäder kämpar ofta essensen av social anknytning för att kunna frodas. Mitt i det händelserika stadslivet råder en djup känsla av frånkoppling, vilket framhäver begränsningarna med traditionellt lägenhetsboende. Många upplever isolering och ensamhet och längtar efter sociala band med sina grannar. Moderna lägenhetskomplex, som kännetecknas av trånga och ogästvänliga delade utrymmen, misslyckas med att främja dessa avgörande interaktioner. Detta projekt utforskar de kulturella och strukturella faktorer som bidrar till denna känsla av isolering. Konventionella boende arrangemang, med sina opersonliga utrymmen, fungerar som barriärer snarare än broar till meningsfull interaktion. När flyktiga möten i tomma korridorer blir normen skapas en genomgripande känsla av frånkoppling, strukturen av gemensamt välbefinnande. Centralt i denna studie är omvandlingen av gemensamma utrymmen i flerbostadshus till levande sociala knutpunkter. Genom att utmana konventionella arkitektoniska normer syftar projektet till att skapa miljöer som uppmuntrar spontana möten och meningsfulla kontakter mellan invånarna. Genom genomtänkta design interventioner, som att betona idén om övergångar mellan privata och gemensamma utrymmen, försöker projektet sudda ut gränserna mellan individuella boendeenheter och främja en kollektiv känsla av tillhörighet. Projektet betonar inkludering och riktar sig till olika invånargrupper, från familjer till studenter, för att öka förståelsen och sammanhållningen i samhället. Målet är att omdefiniera fysiska utrymmen i flerbostadshus och odla en gemenskapskänsla som berikar de boendes livskvalitet och övergripande välbefinnande i stadsmiljöer. Genom innovativ design och ett engagemang för att främja sociala band, syftar detta projekt till att skapa en plan för urbant boende som överskrider begränsningarna för traditionella lägenhetskomplex.

La présente thèse contribue à la littérature en économie urbaine sur les effets de quartiers en cherchant à répondre à trois questions liées : quelle est l’importance du territoire dans la sortie du chômage ? Peut-on parler d’effets de quartier en France ? Comment expliquer la géographie du chômage local ? La réponse à ces questions nécessite une démarche en plusieurs temps. D’abord, l’importance du territoire est analysée par une revue de littérature qui liste les différents mécanismes par lequel le contexte local peut influer sur l’accès à l’emploi des individus. Nous proposons également une analyse descriptive des disparités de chômage entre communes, en France et plus particulièrement en Ile-de-France. Les forts contrastes, qui se maintiennent même lorsque l’on considère la composition locale des demandeurs d’emplois, témoignent d’une relative importance du territoire.La thèse propose, par la suite, des analyses empiriques sur données individuelles pour démontrer l’existence d’effets de quartier en France. Nous montrons que la "qualité" du quartier et les caractéristiques qui lui sont propres déterminent le statut d’emploi des individus. Les individus qui vivent dans les quartiers les plus "défavorisés" ont moins de chances que les autres de trouver un emploi et lorsqu’ils en trouvent un, celui-ci est généralement de moindre qualité. Parmi les effets de quartiers observés, nous cherchons à mettre en évidence l’existence d’une discrimination liée au lieude résidence. Nous proposons des méthodologies distinctes mais complémentaires pour analyser l’effet de la réputation d’un quartier. Nous observons que cette dernière diminue les chances de trouver un emploi. Enfin, pour rendre compte de la géographie du chômage, la thèse propose différentes analyses à l’échelle de la commune et centrées sur la région Ile-de-France. L’objectif est de tester différents mécanismes évoqués dans la littérature en économie urbaine(ségrégation résidentielle, Spatial Mismatch, Skill Mismatch etc.) afin de voir lesquels sont les plus pertinents et lesquels doivent être considérés en priorité. Identifier les mécanismes en jeu est une étape nécessaire et importante pour orienter les politiques publiques qui chercheraient notamment à améliorer la situation des quartiers les plus défavorisés. / This thesis contributes to the literature in urban economics on neighborhood effects by answering three questions : What is the importance of territory in unemployment-to-work transitions ? Are there neighborhood effects in France ? How to explainunemployment geography ? Answering to these questions requires an approach in several steps. Firstly, the importance of the territory is analyzed by a literature review that lists the different mechanisms by which the local context can affect individuals’ access to employment. We also propose a descriptive analysis of unemployment disparities between municipalities in France and especially in the Paris region. The strong contrasts, which are maintained even when one considers the composition of local job-seekers, show the relative importance of the territory. Then, the thesis proposes empirical analysis on individual data to demonstrate the existence of neighborhood effects in France. We show that the "quality" of the neighborhood and its characteristics determine individuals’ employment status. Individuals who live in deprived neighborhoods are less likely than others to find a job and when they find it, it is generally of lower quality. Among the observed neighborhoods effects, we seek to highlight the existence of territorial discrimination. We propose different but complementary methodologies to analyze the effect of the reputation of a neighborhood. We observe that it decreases the chances of finding employment. Finally, in order to explain unemployment geography, the thesis proposes some analysisformunicipalities in Paris region. The objective is to test different mechanisms discussed in the literature in urban economics (residential segregation, Spatial Mismatch, emphSkill Mismatch etc.) to see which are most relevant and which should be considered a priority. Identify the mechanisms involved is a necessary and an important step to guide public policies that want to improve the situation of deprived neighborhoods.

Soit D un digraphe simple (sans cycle orienté de longueur 2 ). En 1990, P. Seymour a conjecturé que D a un sommet v avec un second voisinage extérieur au moins aussi grand que son (premier) voisinage extérieur [1]. Cette conjecture est connue sous le nom de la conjecture du second voisinage du Seymour (SNC). Cette conjecture, si elle est vraie, impliquerait, un cas spécial plus faible (mais important) de la conjecture de Caccetta et Häggkvist [2] proposé en 1978 : tout digraphe D avec un degré extérieur minimum au moins égale à jV (D)j=k a un cycle orienté de longueur au plus k. Le cas particulier est k = 3, et le cas faible exige les deux : le degré extérieur minimum et le degré intérieur minimum de D sont au moins égaux à jV (D)j=k. La conjecture de Seymour restreinte au tournoi est connue sous le nom de conjecture de Dean [1]. En 1996, Fisher [3] a prouvé la conjecture de Dean en utilisant un argument de probabilité. En 2003, Chen, Shen et Yuster [4] ont démontré que tout digraphe a un sommet v tel que d+(v) _ d++(v) où =0.657298..... est l'unique racine de l'équation 2x3 + x2 - 1 = 0. En 2000, Havet et Thomassé [5] ont donné une preuve combinatoire de la conjecture de Dean, en utilisant un outil appelé l'ordre médian. Ils ont démontré que le dernier sommet d'un tel ordre a toujours un second voisinage extérieur au moins aussi grand que son voisinage extérieur. En 2007, Fidler et Yuster [6] ont utilisé l'ordre médian et un autre outil qui s'appelle le digraphe de dépendance afin de prouver la conjecture de Seymour pour tout digraphe D ayant un degré minimum jV (D)j 2. Ils l'ont montré pour tout tournoi où manque un autre sous-tournoi. El Sahili a conjecturé que pour tout D, il existe un completion T de D et un ordre médian de T tel que le denier sommet a un second voisinage extérieur au moins aussi grand que son voisinage extérieur (EC). Il est clair que, EC implique SNC. Cependant, EC propose une méthode afin de résoudre la SNC. En général, on oriente les non arcs de D de manière appropriée, afin d'obtenir un tournoi T et on essaie de trouver un sommet particulier (le denier sommet d'un ordre médian) avec la propriété désirée. Clairement, grâce aux résultats de [5] et [6], la EC est valable pour tournoi, et tout tournoi où manque un autre sous-tournoi. Nous allons vérifier EC pour tout digraphe D ayant un degré minimum jV (D)j 2. Alors, EC est vraie pour tout digraphe où la SNC est déjà connue d'être vraie non trivialement. Nous sommes aussi intéressés à la version pondérée de SNC et EC. En réalité, Fidler et Yuster [6] ont utilisé les digraphes de dépendance comme un outil supplémentaire et le fait que la SNC pondérée est vraie pour les tournois afin de prouver la SNC pour tout digraphe D ayant un degré minimum1 jV (D)j 2. Nous allons définir le digraphe de dépendance de façon plus générale et qui convient à n'importe quel digraphe. Nous allons utiliser le digraphe de dépendance et l'ordre médian comme des outils dans nos contributions à cette conjecture. Suivant la méthode proposée par la EC, nous démontrons la version pondérée de EC, et par conséquent la SNC, pour les classes des digraphes suivants : Digraphes où manque une étoile généralisée, soleil, étoile, ou un graphe complété. En outre, nous prouvons la EC, et par conséquent la SNC, pour digraphes où manque un peigne et digraphe où manque un graphe complet moins 2 arêtes indépendantes ou moins les arêtes d'une cycle de longueur 5. Par ailleurs, nous prouvons la EC, et par conséquent la SNC, pour les digraphes où manque n étoiles disjointes, sous certaines conditions sur les deux degrés minimum du digraphe de dépendance. Des conditions plus faible sont exigées dans le cas n = 1; 2; 3. Dans certains cas, on trouve au moins deux sommets avec la propriété désirée. / Let D be a digraph without digons (directed cycles of length 2). In 1990, Seymour [1] conjectured that D has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. Such a vertex is said to have the second neighborhood property (SNP). This conjecture is known as the second neighborhood conjecture (SNC). This conjecture, if true, would imply a weakening of a particular case (but important) of a long standing conjecture proposed by Caccetta and H aggkvist in 1978, which states that every digraph D with minimum out-degree at least jV (D)j=k has a directed cycle of length at most k. The special case is when k = 3 and the weakening requires both minimum out-degree and minimum in-degree at least jV (D)j=k [2]. Seymour's conjecture restricted to tournaments is known as Dean's conjecture [1]. In 1996, Fisher [3] gave a probabilistic proof to Dean's conjecture. In 2003 Chen, Shen and Yuster [4] proved that every digraph contains a vertex v such that d+(v) _ d++(v), where = 0:657298::: is the unique real root of the equation 2x3 + x2 1 = 0. In 2000, another proof of Dean's conjecture was given by Havet and Thomassé using a tool called median order [5]. They proved that the last vertex of this order, called a feed vertex, has second out-neighborhood at least as large as its first out-neighborhood. Median order is found to be a useful tool not only for the class of tournaments but for other classes of digraphs. In 2007, Fidler and Yuster [6] used also median orders to prove Seymour's conjecture for the class of digraphs with minimum degree jV (D)j 2 (i.e. D is a digraph missing a matching) and tournaments minus another subtournament. El Sahili conjectured that for every digraph D there is a completion T of D and a median order of T whose feed vertex has the SNP in D. Clearly, El Sahili's conjecture (EC) implies SNC. However, as one can observe, EC suggests a method (an approach) for solving the SNC, which we will call the completion approach. In general, following this approach, we orient the missing edges of D in some 'proper' way, to obtain a tournament T. Then we consider a particular feed vertex (clearly, it has the SNP in T) and try to prove that it has the SNP in D as well. Clearly, the result of Havet and Thomassé shows that EC is true for tournaments and the result of Fidler and Yuster [6] shows that EC holds for tournaments minus another subtournament. We will verify EC for the class 1 of tournaments missing a matching. So EC is verified for all the classes of digraphs where the SNC is known to hold non trivially. We will be interested also in the weighted version of EC and SNC. In reality, Fidler and Yuster [6] used dependency digraphs as a supplementary tool for proving the SNC for digraphs missing a matching and the fact that the weighted SNC holds for tournaments. We define dependency digraphs in a more general way, which is suitable to any digraph, and use them in our contribution to Seymour's conjecture. We also use the median order as a tool in our contribution. Using these two tools, and following the completion approach, we prove the weighted version of EC, and consequently the SNC, for several classes of digraphs: Digraphs missing a generalized star, sun, star or a complete graph. In addition, we prove EC, and consequently the SNC for digraphs missing a comb, and digraphs whose missing graph is a complete graph minus two independent edges or the edges of a cycle of length five. Moreover, we prove it for digraphs missing n disjoint stars under some conditions. Weaker conditions are required for n = 1; 2; 3. In some cases, we exhibit at least two vertices with the SNP.

Especialmente nas últimas quatro décadas, muitos estudos se voltaram às variáveis determinantes para a implementação efetiva de sistemas flexíveis de manufatura, tais como seu design, sequenciamento e controle. Neste ínterim, o manejo apropriado do conjunto de ferramentas necessárias para a fabricação de um respectivo lote de produtos foi destacado como fator crucial no desempenho do sistema de produção como um todo. Neste trabalho, abordamos a otimização do número de inserções e remoções de ferramentas no magazine de uma ou mais máquinas numericamente controladas, admitindo-se que uma parcela significativa do tempo de produção é dispensada com estas trocas de ferramentas. De forma mais precisa, a minimização do número de trocas de ferramentas consiste em determinar a ordem de processamento de um conjunto de tarefas, bem como o carregamento ótimo do(s) compartimento(s) de ferramentas da(s) máquina(s), a fim de que o número de trocas seja minimizado. Como demostrado na literatura, mesmo o caso restrito à existência de apenas uma máquina de manufatura (MTSP, do inglês Minimization of Tool Switches Problem) é um problema NP-difícil, o que pode justificar o fato observado de que a maioria dos métodos de solução existentes o abordam de maneira heurística. Consequentemente, concluímos que a extensão ao contexto de múltiplas máquinas é também um problema NP-difícil, intrinsecamente complicado de se resolver. Nosso objetivo consiste em estudar formas eficientes de otimizar o número de trocas de ferramentas em ambientes equipados com máquinas flexíveis de manufatura. Para tanto, abordamos o problema básico, MTSP, e duas de suas variantes, em níveis crescentes de abrangência, que consideram o sequenciamento de tarefas em um conjunto de: (i) máquinas paralelas e idênticas (IPMTC, do inglês Identical Parallel Machines problem with Tooling Constraints); e (ii) máquinas paralelas e idênticas inseridas em um ambiente do tipo job shop (JSSPTC, do inglês Job Shop Scheduling Problem with Tooling Constraints). Classificamos as principais contribuições desta tese com respeito a três aspectos. Primeiramente, empurramos as fronteiras da literatura do MTSP propondo formulações matemáticas para os problemas IPMTC e JSSPTC. Desenvolvemos, também, algoritmos baseados em diferentes técnicas de resolução, como redução de domínio, Path relinking, Adaptive large neighborhood search e a elaboração de regras de despacho. Por último, com o intuito de bem avaliar a eficiência e o alcance de nossos métodos, propomos três novos conjuntos de instâncias teste. Acreditamos, assim, que este trabalho contribui positivamente com pesquisas futuras em um cenário abrangente dentro da minimização das trocas de ferramentas em um sistema flexível de manufatura. / Several studies, especially in the last four decades, have focused on decisive elements for the effective implementation of flexible manufacturing systems, such as their design, scheduling and control. In the meantime, the appropriate management of the set of tools needed to manufacture a certain lot of products has been highlighted as a crucial factor in the performance of the production system as a whole. This work deals with the optimization of the number of insertions and removals from the magazine of one or more numerical controlled machines, assuming that a significant part of the production time is wasted with such tool switches. More precisely, the minimization of tool switches problem (MTSP) consists on determining the processing order of a set of jobs, as well as the optimal loading of the magazine(s) of the machine(s), so that the total number of switches is minimized. As formally demonstrated in the literature, the MTSP is a NP-hard problem even when considering the existence of only one manufacturing machine, which could justify the fact that most of the solution methods tackles it heuristically. We thus conclude that its extension to the case of multiples machines is also NP-hard and, therefore, a problem intrinsically difficult to solve. Our goal consists in studying efficient ways to optimize the number of tool switches in environments equipped with flexible manufacturing machines. For that, we address the basic problem, MTSP, and two MTSP variants, in increasing levels of reach, that consider the job sequencing in a set of: (i) identical parallel machines (Identical Parallel Machines problem with Tooling Constraints, IPMTC); and (ii) identical parallel machines inserted in a job shop environment (Job Shop Scheduling Problem with Tooling Constraints, JSSPTC). The main contributions of this thesis are classified according three aspects. First, we pushed the frontier of the MTSP literature by proposing mathematical formulations for IPMTC and JSSPTC. We also developed algorithms based on different solution techniques, such as domain reduction, Path Relinking, Adaptive Large Neighborhood Search and dispatching rules. Finally, to fully evaluate the effectiveness and limits of our methods, three new sets of benchmark instances were generated. We believe that this work contributes positively to the future of research in a broad scenario inside the minimization of tool switches in flexible manufacturing systems.

[pt] A exploração e produção (EeP) offshore de óleo e gás envolve várias operações complexas e importantes, como perfuração, avaliação, completação e manutenção de poços. A maioria dessas tarefas requer o uso de sondas, um recurso custoso e escasso que as companhias de petróleo precisam planejar e programar corretamente. Na literatura, este problema é chamado de Programação de Sondas. Todavia, existem poucos estudos relacionados aos poços marítimos e às atividades de perfuração e nenhum destes com funções objetivo e restrições realistas, como orçamento. Por isso, muitas empresas de petróleo têm fortes dificuldades no planejamento das sondas, resultando em grandes custos para elas. Com o objetivo de preencher essa lacuna, esta dissertação estuda um problema de programação de sondas em uma empresa petroleira e propõe um método híbrido para determinar a frota de sondas e seu cronograma, que minimize o orçamento da empresa. Dois modelos de programação matemática – um para minimização das sondas e outro para minimizar seu orçamento com variações da unidade de tempo utilizada (dia ou semana) – e várias heurísticas – usando algoritmos de busca local e variable neighborhood descent (VND) com três estruturas de vizinhança e duas estratégias de busca (first e best improvemment) e métodos construtivos- foram desenvolvidos e testados em duas instâncias (uma pequena e uma grande), baseadas em dados reais da empresa do caso de estudo. As três estruturas de vizinhanças são baseadas em movimentos de insert, uma delas não permite alterar as datas de alocação das tarefas na solução inicial, outra permite adiar tarefas e a última as posterga.Os resultados indicaram a dificuldade no desempenho dos modelos matemáticos nas grandes instâncias e uma forte capacidade das heurísticas para encontrar soluções similares com muito menos esforço computacional. Na instância pequena, o modelo exato para minimizar o orçamento encontrou soluções um pouco melhores que a heurística (diferença de entre 0,4 por cento e 5,6 por cento), embora necessitando de mais esforço computacional, principalmente os modelos com unidades de tempo em dias. Porém, na instância maior, as soluções da programação matemática possuíram altos gap (mais de 11 por cento) e altos tempos computacionais (pelo menos 12 horas), tendo o modelo matemático mais completo sido incapaz de encontrar soluções inteiras viáveis ou limites inferiores depois de mais de um dia rodando. Enquanto isso, as heurísticas foram capazes de encontrar soluções similares ou até melhores (desvios de -6 por cento e 14 por cento em relação a melhor solução exata) em um tempo muito menor, tendo 70 das 156 heurísticas desenvolvidas superado os modelos matemáticos. Além disso, os melhores resultados heurísticos foram utilizando algoritmos de variable neighborhood descent (VND) com estruturas de vizinhanças que realizavam movimentos de insert de tarefas em sondas existentes ou novas e permitiam postergar ou adiantar as tarefas das sondas. A abordagem hibrida foi comparada também com uma abordagem puramente heurística, tendo a primeira obtido melhores resultados. Por fim, os resultados demonstram que o método híbrido proposto combinando o modelo matemático que minimiza o número de sondas com as heurísticas de busca local é uma ferramenta de suporte a decisão rápida e prática, com potencial para reduzir milhões de dólares para as empresas petroleiras do mercado offshore, com capacidade para encontrar cronogramas próximos da solução ótima com pouco esforço computacional, mesmo em instâncias grandes onde a maioria dos métodos exatos é muito complexa e lenta. / [en] The offshore exploration and production (EandP) of Oil and Gas involves several complex and important operations and relies, mostly, in the use of rigs, a scarce and costly resource that oil companies need to properly plan and schedule. In the literature, this decision is called the Rig Scheduling Problem (RSP). However, there is not any study related to offshore wells and drilling activities with realistic objective functions. Aiming to fulfill this gap, this dissertation studies a rig scheduling problem of a real offshore company and proposes a matheuristic approach to determine a rigs fleet and schedule that minimizes the budget. Two mathematical models – one for rigs fleet minimization and another one that minimizes the rigs budget – and several heuristics – using local search (LS) and variable neighborhood descent (VND) algorithms with three neighborhood structures and also constructive methods – were developed and tested in two instances based on real data of the studied company. In the small instance, the programming model found slightly better solutions than the heuristic, despite requiring more computational effort. Nevertheless, in the large instance, the mathematical programming solutions present large gaps (over 11 percent) and an elevated computational time (at least 12 hours), while the heuristics can find similar (or even better) solutions in a shorter time (minutes), having 70 of 156 heuristics outperformed the mathematical models. Last, the matheuristic combination of the simplest mathematical model with the heuristics has found the best known solutions (BKS) of the large instance with a moderate computational effort.

L'Apprentissage Supervisé est un domaine populaire de l'Apprentissage Automatique en progrès constant depuis plusieurs années. De nombreuses techniques ont été développées pour résoudre le problème de classification, mais, dans la plupart des cas, ces méthodes se basent sur la présence et le nombre de points d'une classe donnée dans des zones de l'espace que doit définir le classifieur. Á cause de cela la construction de ce classifieur est dépendante de la densité du nuage de points des données de départ. Dans cette thèse, nous montrons qu'utiliser la topologie des données peut être une bonne alternative lors de la construction des classifieurs. Pour cela, nous proposons d'utiliser les graphes topologiques comme le Graphe de Gabriel (GG) ou le Graphes des Voisins Relatifs (RNG). Ces dernier représentent la topologie de données car ils sont basées sur la notion de voisinages et ne sont pas dépendant de la densité. Pour appliquer ce concept, nous créons une nouvelle méthode appelée Classification aléatoire par Voisinages (Random Neighborhood Classification (RNC)). Cette méthode utilise des graphes topologiques pour construire des classifieurs. De plus, comme une Méthodes Ensemble (EM), elle utilise plusieurs classifieurs pour extraire toutes les informations pertinentes des données. Les EM sont bien connues dans l'Apprentissage Automatique. Elles génèrent de nombreux classifieurs à partir des données, puis agrègent ces classifieurs en un seul. Le classifieur global obtenu est reconnu pour être très eficace, ce qui a été montré dans de nombreuses études. Cela est possible car il s'appuie sur des informations obtenues auprès de chaque classifieur qui le compose. Nous avons comparé RNC à d'autres méthodes de classification supervisées connues sur des données issues du référentiel UCI Irvine. Nous constatons que RNC fonctionne bien par rapport aux meilleurs d'entre elles, telles que les Forêts Aléatoires (RF) et Support Vector Machines (SVM). La plupart du temps, RNC se classe parmi les trois premières méthodes en terme d'eficacité. Ce résultat nous a encouragé à étudier RNC sur des données réelles comme les tweets. Twitter est un réseau social de micro-blogging. Il est particulièrement utile pour étudier l'opinion à propos de l'actualité et sur tout sujet, en particulier la politique. Cependant, l'extraction de l'opinion politique depuis Twitter pose des défis particuliers. En effet, la taille des messages, le niveau de langage utilisé et ambiguïté des messages rend très diffcile d'utiliser les outils classiques d'analyse de texte basés sur des calculs de fréquence de mots ou des analyses en profondeur de phrases. C'est cela qui a motivé cette étude. Nous proposons d'étudier les couples auteur/sujet pour classer le tweet en fonction de l'opinion de son auteur à propos d'un politicien (un sujet du tweet). Nous proposons une procédure qui porte sur l'identification de ces opinions. Nous pensons que les tweets expriment rarement une opinion objective sur telle ou telle action d'un homme politique mais plus souvent une conviction profonde de son auteur à propos d'un mouvement politique. Détecter l'opinion de quelques auteurs nous permet ensuite d'utiliser la similitude dans les termes employés par les autres pour retrouver ces convictions à plus grande échelle. Cette procédure à 2 étapes, tout d'abord identifier l'opinion de quelques couples de manière semi-automatique afin de constituer un référentiel, puis ensuite d'utiliser l'ensemble des tweets d'un couple (tous les tweets d'un auteur mentionnant un politicien) pour les comparer avec ceux du référentiel. L'Apprentissage Topologique semble être un domaine très intéressant à étudier, en particulier pour résoudre les problèmes de classification...... / Supervised Learning is a popular field of Machine Learning that has made recent progress. In particular, many methods and procedures have been developed to solve the classification problem. Most classical methods in Supervised Learning use the density estimation of data to construct their classifiers.In this dissertation, we show that the topology of data can be a good alternative in constructing classifiers. We propose using topological graphs like Gabriel graphs (GG) and Relative Neighborhood Graphs (RNG) that can build the topology of data based on its neighborhood structure. To apply this concept, we create a new method called Random Neighborhood Classification (RNC).In this method, we use topological graphs to construct classifiers and then apply Ensemble Methods (EM) to get all relevant information from the data. EM is well known in Machine Learning, generates many classifiers from data and then aggregates these classifiers into one. Aggregate classifiers have been shown to be very efficient in many studies, because it leverages relevant and effective information from each generated classifier. We first compare RNC to other known classification methods using data from the UCI Irvine repository. We find that RNC works very well compared to very efficient methods such as Random Forests and Support Vector Machines. Most of the time, it ranks in the top three methods in efficiency. This result has encouraged us to study the efficiency of RNC on real data like tweets. Twitter, a microblogging Social Network, is especially useful to mine opinion on current affairs and topics that span the range of human interest, including politics. Mining political opinion from Twitter poses peculiar challenges such as the versatility of the authors when they express their political view, that motivate this study. We define a new attribute, called couple, that will be very helpful in the process to study the tweets opinion. A couple is an author that talk about a politician. We propose a new procedure that focuses on identifying the opinion on tweet using couples. We think that focusing on the couples's opinion expressed by several tweets can overcome the problems of analysing each single tweet. This approach can be useful to avoid the versatility, language ambiguity and many other artifacts that are easy to understand for a human being but not automatically for a machine.We use classical Machine Learning techniques like KNN, Random Forests (RF) and also our method RNC. We proceed in two steps : First, we build a reference set of classified couples using Naive Bayes. We also apply a second alternative method to Naive method, sampling plan procedure, to compare and evaluate the results of Naive method. Second, we evaluate the performance of this approach using proximity measures in order to use RNC, RF and KNN. The expirements used are based on real data of tweets from the French presidential election in 2012. The results show that this approach works well and that RNC performs very good in order to classify opinion in tweets.Topological Learning seems to be very intersting field to study, in particular to address the classification problem. Many concepts to get informations from topological graphs need to analyse like the ones described by Aupetit, M. in his work (2005). Our work show that Topological Learning can be an effective way to perform classification problem.

Especialmente nas últimas quatro décadas, muitos estudos se voltaram às variáveis determinantes para a implementação efetiva de sistemas flexíveis de manufatura, tais como seu design, sequenciamento e controle. Neste ínterim, o manejo apropriado do conjunto de ferramentas necessárias para a fabricação de um respectivo lote de produtos foi destacado como fator crucial no desempenho do sistema de produção como um todo. Neste trabalho, abordamos a otimização do número de inserções e remoções de ferramentas no magazine de uma ou mais máquinas numericamente controladas, admitindo-se que uma parcela significativa do tempo de produção é dispensada com estas trocas de ferramentas. De forma mais precisa, a minimização do número de trocas de ferramentas consiste em determinar a ordem de processamento de um conjunto de tarefas, bem como o carregamento ótimo do(s) compartimento(s) de ferramentas da(s) máquina(s), a fim de que o número de trocas seja minimizado. Como demostrado na literatura, mesmo o caso restrito à existência de apenas uma máquina de manufatura (MTSP, do inglês Minimization of Tool Switches Problem) é um problema NP-difícil, o que pode justificar o fato observado de que a maioria dos métodos de solução existentes o abordam de maneira heurística. Consequentemente, concluímos que a extensão ao contexto de múltiplas máquinas é também um problema NP-difícil, intrinsecamente complicado de se resolver. Nosso objetivo consiste em estudar formas eficientes de otimizar o número de trocas de ferramentas em ambientes equipados com máquinas flexíveis de manufatura. Para tanto, abordamos o problema básico, MTSP, e duas de suas variantes, em níveis crescentes de abrangência, que consideram o sequenciamento de tarefas em um conjunto de: (i) máquinas paralelas e idênticas (IPMTC, do inglês Identical Parallel Machines problem with Tooling Constraints); e (ii) máquinas paralelas e idênticas inseridas em um ambiente do tipo job shop (JSSPTC, do inglês Job Shop Scheduling Problem with Tooling Constraints). Classificamos as principais contribuições desta tese com respeito a três aspectos. Primeiramente, empurramos as fronteiras da literatura do MTSP propondo formulações matemáticas para os problemas IPMTC e JSSPTC. Desenvolvemos, também, algoritmos baseados em diferentes técnicas de resolução, como redução de domínio, Path relinking, Adaptive large neighborhood search e a elaboração de regras de despacho. Por último, com o intuito de bem avaliar a eficiência e o alcance de nossos métodos, propomos três novos conjuntos de instâncias teste. Acreditamos, assim, que este trabalho contribui positivamente com pesquisas futuras em um cenário abrangente dentro da minimização das trocas de ferramentas em um sistema flexível de manufatura. / Several studies, especially in the last four decades, have focused on decisive elements for the effective implementation of flexible manufacturing systems, such as their design, scheduling and control. In the meantime, the appropriate management of the set of tools needed to manufacture a certain lot of products has been highlighted as a crucial factor in the performance of the production system as a whole. This work deals with the optimization of the number of insertions and removals from the magazine of one or more numerical controlled machines, assuming that a significant part of the production time is wasted with such tool switches. More precisely, the minimization of tool switches problem (MTSP) consists on determining the processing order of a set of jobs, as well as the optimal loading of the magazine(s) of the machine(s), so that the total number of switches is minimized. As formally demonstrated in the literature, the MTSP is a NP-hard problem even when considering the existence of only one manufacturing machine, which could justify the fact that most of the solution methods tackles it heuristically. We thus conclude that its extension to the case of multiples machines is also NP-hard and, therefore, a problem intrinsically difficult to solve. Our goal consists in studying efficient ways to optimize the number of tool switches in environments equipped with flexible manufacturing machines. For that, we address the basic problem, MTSP, and two MTSP variants, in increasing levels of reach, that consider the job sequencing in a set of: (i) identical parallel machines (Identical Parallel Machines problem with Tooling Constraints, IPMTC); and (ii) identical parallel machines inserted in a job shop environment (Job Shop Scheduling Problem with Tooling Constraints, JSSPTC). The main contributions of this thesis are classified according three aspects. First, we pushed the frontier of the MTSP literature by proposing mathematical formulations for IPMTC and JSSPTC. We also developed algorithms based on different solution techniques, such as domain reduction, Path Relinking, Adaptive Large Neighborhood Search and dispatching rules. Finally, to fully evaluate the effectiveness and limits of our methods, three new sets of benchmark instances were generated. We believe that this work contributes positively to the future of research in a broad scenario inside the minimization of tool switches in flexible manufacturing systems.