O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

This report covers an investigation of the methods and algorithms required to plan and perform semi-autonomous photo missions on Apple iPad devices using data exported from Google Earth. Flight time was to be minimized, taking wind velocity and aircraft performance into account. Google Earth was used both to define what photos to take, and to define the allowable mission area for the aircraft. A benchmark mission was created containing 30 photo operations in a 250 by 500 m area containing several no-fly-areas. The report demonstrates that photos taken in Google Earth can be reproduced in reality with good visual resemblance. High quality paths between all possible photo operation pairs in the benchmark mission could be found in seconds using the Theta* algorithm in a 3D grid representation with six-edge connectivity (Up, Down, North, South, East, West). Smoothing the path in a post-processing step was shown to further increase the quality of the path at a very low computational cost. An optimal route between the operations in the benchmark mission, using the paths found by Theta*, could be found in less than half a minute using a Branch-and-Bound algorithm. It was however also found that prematurely terminating the algorithm after five seconds yielded a route that was close enough to optimal not to warrant running the algorithm to completion.

Étant donnés un graphe simple non orienté G = (V, E) et un sommet particulier r dans V appelé racine, un arbre enraciné, ou r-arbre, de G est soit le graphe nul soit un arbre contenant r. Si un vecteur de capacités sur les sommets est donné, un sous-graphe de G est dit borné si le degré de chaque sommet dans le sous-graphe est inférieur ou égal à sa capacité. Soit w un vecteur de poids sur les arêtes et p un vecteur de profits sur les sommets. Le problème du r-arbre borné maximum (MBrT, de l’anglais Maximum Bounded r-Tree) consiste à trouver un r-arbre borné T = (U, F) de G tel que son poids soit maximisé. Si la contrainte de capacité du problème MBrT est relâchée, nous obtenons le problème du r-arbre maximum (MrT, de l’anglais Maximum r-Tree). Cette thèse contribue à l’étude des problèmes MBrT et MrT.Tout d’abord, ces deux problèmes sont formellement définis et leur complexité est étudiée. Nous présentons ensuite des polytopes associés ainsi qu’une formulation pour chacun d’entre eux. Par la suite, nous proposons plusieurs algorithmes combinatoires pour résoudre le problème MBrT (et donc le problème MrT) en temps polynomial sur les arbres, les cycles et les cactus. En particulier, un algorithme de programmation dynamique est utilisé pour résoudre le problème MBrT sur les arbres. Pour les cycles, nous sommes amenés a considérer trois cas différents pour lesquels le problem MBrT se réduit à certains problèmes polynomiaux. Pour les cactus, nous montrons tout d’abord que le problème MBrT peut être résolu en temps polynomial sur un type de graphes appelé cactus basis. En utilisant une série de décompositions en sous-problèmes sur les arbres et les cactus basis, nous obtenons un algorithme pour les graphes de type cactus.La deuxième partie de ce travail étudie la structure polyédrale de trois polytopes associés aux problèmes MBrT et MrT. Les deux premiers polytopes, Bxy(G,r,c) et Bx(G,r,c) sont associés au problème MBrT. Tous deux considèrent des variables sur les arêtes de G, mais seuls Bxy(G,r,c) possède également des variables sur les sommets de G. Le troisième polytope, Rx(G,r), est associé au problème MrT et repose uniquement sur les variables sur les arêtes. Pour chacun de ces trois polytopes, nous étudions sa dimension, caractérisons certaines inégalités définissant des facettes, et présentons les moyens possibles de décomposition. Nous introduisons également de nouvelles familles de contraintes. L’ajout de ces contraintes nous permettent de caractériser ces trois polytopes dans plusieurs classes de graphes.Pour finir, nous étudions les problèmes de séparation pour toutes les inégalités que nous avons trouvées jusqu’ici. Des algorithmes polynomiaux de séparation sont présentés, et lorsqu’un problème de séparation est NP-difficile, nous donnons des heuristiques de séparation. Tous les résultats théoriques développés dans ce travail sont implémentés dans plusieurs algorithmes de coupes et branchements auxquels une matheuristique est également jointe pour générer rapidement des solutions réalisables. Des expérimentations intensives ont été menées via le logiciel CPLEX afin de comparer les formulations renforcées et originales. Les résultats obtenus montrent de manière convaincante la force des formulations renforcées. / Given a simple undirected graph G = (V, E) with a so-called root node r in V, a rooted tree, or an r-tree, of G is either the empty graph, or a tree containing r. If a node-capacity vector c is given, then a subgraph of G is said to be bounded if the degree of each node in the subgraph does not exceed its capacity. Let w be an edge-weight vector and p a node-price vector. The Maximum Bounded r-Tree (MBrT) problem consists of finding a bounded r-tree T = (U, F) of G such that its weight is maximized. If the capacity constraint from the MBrT problem is relaxed, we then obtain the Maximum r-Tree (MrT) problem. This dissertation contributes to the study of the MBrT problem and the MrT problem.First we introduce the problems with their definitions and complexities. We define the associated polytopes along with a formulation for each of them. We present several polynomial-time combinatorial algorithms for both the MBrT problem (and thus the MrT problem) on trees, cycles and cactus graphs. Particularly, a dynamic-programming-based algorithm is used to solve the MBrT problem on trees, whereas on cycles we reduce it to some polynomially solvable problems in three different cases. For cactus graphs, we first show that the MBrT problem can be solved in polynomial time on a so-called cactus basis, then break down the problem on any cactus graph into a series of subproblems on trees and on cactus basis.The second part of this work investigates the polyhedral structure of three polytopes associated with the MBrT problem and the MrT problem, namely Bxy(G, r, c), Bx(G, r, c) and Rx(G, r). Bxy(G, r, c) and Bx(G, r, c) are polytopes associated with the MBrT problem, where Bxy(G, r, c) considers both edge- and node-indexed variables and Bx(G, r, c) considers only edge-indexed variables. Rx(G, r) is the polytope associated with the MrT problem that only considers edge-indexed variables. For each of the three polytopes, we study their dimensions, facets as well as possible ways of decomposition. We introduce some newly discovered constraints for each polytope, and show that these new constraints allow us to characterize them on several graph classes. Specifically, we provide characterization for Bxy (G, r, c) on cactus graphs with the help of a decomposition through 1-sum. On the other hand, a TDI-system that characterizes Bx(G,r,c) is given in each case of trees and cycles. The characterization of Rx(G,r) on trees and cycles then follows as an immediate result.Finally, we discuss the separation problems for all the inequalities we have found so far, and present algorithms or cut-generation heuristics accordingly. A couple of branch-and-cut frameworks are implemented to solve the MBrT problem together with a greedy-based matheuristic. We compare the performances of the enhanced formulations with the original formulations through intensive computational test, where the results demonstrate convincingly the strength of the enhanced formulations.

Si l'évolution des étoiles simples est relativement bien comprise, l'étude des étoiles binaires, qui représentent la majorité des étoiles, nécessite encore des progrès majeurs, particulièrement en ce qui concerne leurs différents modes d'interactions. Dans ces systèmes, la composition de surface d'une étoile peut être altérée non seulement par l'accrétion d'éléments synthétisés au sein de l'étoile compagnon, mais également par des processus de mélanges internes induits par les forces de marées et d'un transport du moment angulaire. Plusieurs classes d'étoiles post-transfert de masse (les étoiles à baryum, CH et S) possèdent effectivement des compositions de surface caractérisées par la présence d'éléments lourds, tel que le baryum. Ces systèmes sont présumés se former au sein de systèmes binaires incluant une étoile de la branche asymptotique des géantes (appelé étoile AGB). Ces dernières sont des étoiles remarquables qui représentent l'unique site d'une nucléosynthèse particulière. En effet, elles constituent les contributeurs essentiels de la production de fluor ou de baryum. Les étoiles AGB sont également caractérisées par une importante perte de masse par vent qui éjecte progressivement leur enveloppe enrichie en ces éléments. Au sein d'un système binaire, une partie de ce vent est accréditée par l'étoile compagnon et pollue ainsi sa surface, laissant une signature spectrale distincte qui subsistera longtemps après que l'étoile AGB ait disparu. Ce scénario est suggéré comme étant responsable de la formation d'une grande variété d'étoiles chimiquement particulières, tels que les étoiles à baryum.<p>Cependant, plusieurs propriétés clés de ces systèmes, en particulier leurs distributions de périodes orbitales et d'excentricités, demeurent inexpliquées depuis des décennies. L'incapacité de nos modèles à reproduire ces propriétés orbitales met en évidence notre compréhension limitée des mécanismes d'interaction qui gouvernent l'évolution des systèmes binaires. Plus particulièrement, des mécanismes qui génèrent des orbites excentriques au sein des étoiles à baryum et des systèmes analogues sont requis. Nous examinons ainsi la possibilité qu'à sa naissance l'étoile naine blanche subisse un kick ou que la présence d'un disque entourant le système binaire soit à l'origine des fortes excentricités observées chez les étoiles à baryum. Ces deux mécanismes permettent pour la première fois depuis l'étude de ces systèmes d'apporter une solution à ces problèmes. Il est montré comment comprendre les signatures induites par un compagnon étoile AGB et les corréler avec les propriétés orbitales du système binaire est essentiel pour tester et améliorer notre connaissance de l'évolution des étoiles binaires; l'objectif de ce travail.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The increasing emphasis on mass customization, shortened product lifecycles, synchronized supply chains, when coupled with advances in information system, is driving most firms towards make-to-order (MTO) operations. Increasing global competition, lower profit margins, and higher customer expectations force the MTO firms to plan its capacity by managing the effective demand. The goal of this research was to maximize the operational profits of a make-to-order operation by selectively accepting incoming customer orders and simultaneously allocating capacity for them at the sales stage. For integrating the two decisions, a Mixed-Integer Linear Program (MILP) was formulated which can aid an operations manager in an MTO environment to select a set of potential customer orders such that all the selected orders are fulfilled by their deadline. The proposed model combines order acceptance/rejection decision with detailed scheduling. Experiments with the formulation indicate that for larger problem sizes, the computational time required to determine an optimal solution is prohibitive. This formulation inherits a block diagonal structure, and can be decomposed into one or more sub-problems (i.e. one sub-problem for each customer order) and a master problem by applying Dantzig-Wolfe’s decomposition principles. To efficiently solve the original MILP, an exact Branch-and-Price algorithm was successfully developed. Various approximation algorithms were developed to further improve the runtime. Experiments conducted unequivocally show the efficiency of these algorithms compared to a commercial optimization solver. The existing literature addresses the static order acceptance problem for a single machine environment having regular capacity with an objective to maximize profits and a penalty for tardiness. This dissertation has solved the order acceptance and capacity planning problem for a job shop environment with multiple resources. Both regular and overtime resources is considered. The Branch-and-Price algorithms developed in this dissertation are faster and can be incorporated in a decision support system which can be used on a daily basis to help make intelligent decisions in a MTO operation.

In Canada’s western Arctic, perennial discharge from permafrost watersheds is the surface manifestation of active groundwater flow systems, yet understanding the mechanisms of groundwater recharge and flow in periglacial environments remains enigmatic. This thesis addresses questions on how and where groundwater recharge occurs. Watersheds were selected in Yukon (Fishing Branch River at Bear Cave Mountain) and the Northwest Territories at latitudes spanning from continuous to discontinuous permafrost (five tributary rivers to the Mackenzie River from Wrigley to Aklavik). All are characterized by perennial flow with open water in the winter, and discharge from sedimentary formations of karstic carbonates and evaporate rocks. Determinations of groundwater contributions to discharge, mixing, recharge conditions and circulation times were made on the basis of a suite of analytical approaches involving measurements of major dissolved ions, δ18O, δD, δ13CDIC, 3H, noble gases and flow gauging was conducted at some sites. The application of these tracers show that hydrogeological conditions and flow paths in permafrost terrains are surprisingly similar to those of temperate regions. Groundwater recharge was determined to be a mix of annual precipitation with contributions from snowmelt and precipitation. All systems investigated show that groundwaters have recharged through organic soils with elevated PCO2, which suggests that recharge occurs largely during summer when biological activity is high. Noble gas concentrations show that the recharge temperature was between 0 and 6 °C, which, when considered in the context of discharge temperatures, suggests that there is no significant imbalance of energy flux into the subsurface. Groundwater ages were found using the 3H-3He method and were dependent on flow path. By characterizing groundwater and surface water chemistry, the proportion of groundwater was found in numerous water courses. The possible impact of ground ice formation and melting on noble gas concentrations in groundwater was considered. To assess this link, a new method to measure the noble gas composition of ground ice bodies was developed. The method can be used to determine the origin of ice, based on changes in noble gas ratios between ice originating from compaction of snow (e.g. glacier ice) vs. ice originating from freezing of water. No significant fractionation of noble gases during groundwater freezing and ground ice formation was identified. Applied to determination of the origin of ground ice bodies, the method was shown to be both diagnostic of ice origin and un-encumbered by reactivity in the subsurface, which compromises the use of the dominant atmospheric gases (O2 and N2).   Résumé Dans l’Ouest de l'Arctique canadien, la décharge pérenne dans certaines rivières en région de pergélisol est la manifestation en surface d’une circulation d’eau souterraine; cependant la compréhension des mécanismes d’écoulement et de recharge des eaux souterraines en région de pergélisol demeure énigmatique. Cette thèse s’intéresse à la question de savoir comment et où la recharge des eaux souterraines se produit. Des bassins versants ont été choisis au Yukon (Rivière Fishing Branch à Bear Cave Mountain) et dans les Territoire du Nord-Ouest à des latitudes s’étendant du pergélisol discontinu au pergélisol continu (cinq tributaires du Mackenzie entre Wrigley et Aklavik). Toutes ces rivières ont un écoulement d’eau pérenne avec des zones non gelées et une décharge dans des formations sédimentaires de roches carbonatées et d‘évaporites. L’identification des contributions des eaux à la décharge, les mélanges, les conditions de recharge, et les temps de circulation ont été faits à partir d’analyses qui ont inclus les concentrations en éléments majeurs, leur valeur isotopique (δ18O, δD, δ13C, 3H), ainsi que leur teneur en gaz rares. A certain des sites analysés des mesures d’écoulement ont été prises. L’application de ces traceurs montre que les conditions hydrauliques et le chemin des écoulements en région de pergélisol sont similaires à ceux des régions tempérées. La recharge en eau souterraine a été identifiée comme étant un mélange de précipitations annuelles, avec des contributions de neige et de pluies. Tous les systèmes étudiés montrent que les eaux souterraines se sont rechargées en traversant des sols organiques avec une PCO2 élevée, ce qui suggère que la recharge se produire largement durant l’été quand l’activité biologique est élevée. Cependant, les concentrations en gaz nobles montre que la température de recharge des eaux souterraines était entre 0 et 6 °C ce qui indique qu’il n’y a pas de déséquilibre de flux d’énergie à l’intérieur de la zone proche de la surface. L’âge des eaux a été déterminé par la méthode 3H-3He et cet âge est dépendant du chemin d'écoulement. En caractérisant les paramètres chimiques des eaux de surface et des eaux souterraines, il a été possible de trouver la contribution des eaux souterraines aux eaux surface. Le possible impact de la formation et de la fonte de la glace souterraine sur les concentrations des gaz nobles a été considéré. Pour déterminer s’il y a un lien entre ceux-ci, une nouvelle méthode pour mesurer la concentration en gaz nobles dans les glaces souterraines a été développée. La méthode peut être utilisée pour déterminer l’origine de la glace; elle est basée sur les changements dans les rapports des gaz nobles entre la glace issue de la compaction de la neige (c’est-à-dire la glace de glacier) par opposition à la glace issue du gel de l’eau. Aucun fractionnement significatif des gaz nobles durant l’engel des eaux souterraines et la formation de glaces souterraines n’a été identifié. Appliquée à l’identification de l’origine des masses de glace enfouies, on a montré que la méthode pouvait permettre d’identifier l’origine des glaces souterraines sans qu’elle soit affectée par des réactions biologiques de sub-surface, lesquelles rendent inutilisables les gaz atmosphériques (O2, and N2).

The aim of this thesis was provision of authoritative document on which the company could comprehensively evaluate a given business opportunity and decide on its acceptance or rejection, or basis for further analysis. For this purpose I created a business plan according to current recommendations. In selected organizations I prepared analysis of internal and external environment to get the information necessary for the decision.

Dissertation interfaces juristic, tax and accounting questions of business of foreign person in Czech republic.

The major goal of this work is to compare positions of different institutional types active in the banking sector in the Czech Republic. The emphasis is being given to the description of gradual mutual convergence and interactions of particular institutional types in the context of changes undergoing in a transition economy since 1990. The second part of this work analyses the framework for the operation of different institutional types and compares their positions against clients, owners and supervisor. The last part of the work is a comparative analysis of economic indicators for each institutional type in the context of changes in the market and legal environment since 2004.

The thesis on the Recruitment problems in foreign branches of global company is described specific Prague developer company, its projects and its experience in personnel policy. The aim of this work is to define the main problems of staff recruitment and the development of measures to improve these processes. This thesis will consist of several parts. the first part describes the company, its typical projects, strategy and preparation of its expansion into Kazakhstan. The following are the main aspects of the relationship between headquarters and its branches. In the third part are mentioned and characterized approaches to management and recruitment of personnel in foreign branches. Description of the organizational structure of the company is the fourth part of this work. Followed by a description of the current human resources management process at the branch and identifying problems of staff recruitment. The last part is focused on the inventing of the measures to improve these processes.