No description available.

Heap models in the max-plus algebra are interesting dynamical systems that can be used to model a variety of tetris-like systems, such as batch flow shops for manufacturing models. Each heap in the model can be identified with a single product to manufacture. The objective is to manufacture a group of products in such an order so as to minimize the total manufacturing time. Because this scheduling problem reduces to a variation of the Traveling Salesman Problem (known to be NP-complete), the optimal solution is computationally infeasible for many real-world systems. Thus, a feasible approximation method is needed. This work builds on and expands the existing heap model in order to more effectively solve the scheduling problems. Specifically, this work:1. Further characterizes the admissible products to these systems.2. Further characterizes sets of admissible products. 3. Presents a novel algorithm, the asynchronous $t$-step approximation, to approximate these systems.4. Proves error bounds for the system approximation, and show why these error bounds are better than the existing approximation.

Discrete event systems (DES) are a special class of dynamical systems with discrete-valued state space and event-driven transitions. DES are ubiquitous in today's world and are used in different sectors such as manufacturing systems, transport networks and computer networks. They offer unique capabilities, such as flexibility and adaptability; at the same time, they can be challenging to model and analyze. Moreover, the complexity of DES is scaled up when disturbances are present. Many different kinds of real life DES can be modeled using dioid algebra which is a powerful tool for describing nonlinear behaviors using linear system models. Dioid algebra is an exotic algebra of formal series which can be understood as a set of only positive numbers without negatives. This special algebraic structure is useful in modeling DES because such systems feature variables that cannot be inverted with respect to some variables. Nonlinear behaviors of DES are able to be modeled as linear systems in terms of dioid algebra in order to use classical control techniques in scheduling and control of DES.This dissertation presents the scheduling and control of DES using a special dioid called max-plus algebra, which is a set of real numbers with the operation of maximum and addition replacing the usual classical operations of addition and multiplication, respectively. This dissertation also studies the behavior of DES when disturbances are present. Two different paths to the scheduling of DES are presented: using dioid algebra and using linear programming methods. The control of DES with disturbances and uncertainties is also explored, particularly, the solutions of the disturbance decoupling problem and the modified disturbance decoupling problem using various controller structures are presented. Disturbance decoupling in this dissertation means the scheduling of the DES will not not be affected by the presence of the disturbances. On the other hand, modified disturbance decoupling means the scheduling will not be worse than the delays caused by the disturbances in industrial just-in-time (JIT) standards. JIT means that the operations start with just enough time to be completed by the desired schedule in order to minimize waste and costs in work in progress and material storage.The applicability of the approach presented in this dissertation is demonstrated in real-world processes including a large-scale high throughput screening (HTS) system in drug discovery and an optimal scheduler for an airport's runways. The main contributions of this dissertation are max-plus and mathematical programming solutions for scheduling and control of discrete event systems with disturbances. The results present a theoretical scheduling prior to exhaustive scheduling algorithms in large-scaled industrial systems.

Technology scaling in the nanometer era comes with a significant amount of process variation, leading to lower yield and new types of defective parts. These challenges necessitate robust design to ensure adequate yield, and smarter testing to screen out bad chips. Statistical static timing analysis (SSTA) en- ables this but suffers from crude approximation algorithms. This dissertation first studies the underlying theories of timing graphs and proposes two fundamental techniques enhancing the core statistical timing algorithms. We first propose the refactoring technique to capture topological correlation. Static timing analysis is based on levelized breadth-first traversal, which is a fundamental graph traversal technique and has been used for static timing analysis over the past decades. We show that there are numerous alternatives to the traversal because of an algebraic property, the distributivity of addition over maximum. This new interpretation extends the degrees of freedom of static timing analysis, which is exploited to improve the accuracy of SSTA. We also propose a novel operator for computing joint probabilities in SSTA. In many SSTA applications, this is very common but is done using the max operator which results in much error due to the linear approximation. The new operator provides significantly higher accuracy at a small cost of run time. Second, based on the two fundamental studies, this dissertation devel- ops three applications. We propose a criticality computation method that is essential to robust design and test synthesis; The proposed method, combined with the two fundamental techniques, achieves drastic accuracy improvement over the state-of-the-art method, demonstrating the benefits in practical ap- plications. We formulate the statistical path selection problem for at-speed test as a gambling problem and present an elegant solution based on the Kelly criterion. To circumvent the coverage loss issue in statistical path selection, we propose a testability driven approach, making it a practical solution for coping with parametric defects. / text

No description available.

Often mathematics is seen by high school students as a science restricted to memorizing formulas and concepts. Therefore limiting in its essence. The work seeks to reverse that view by submitting a new eld of study: Tropical Algebra. Relatively new area of mathematics that keeps the curious feature to handle the operations of addition and multiplication di erently from traditional, already presents interesting practical results. Tropical algebra will be presented in a didactic way, comparing it with the traditional algebra, showing the consequences of tropical operations in the study of polynomials, matrices and geometry, and presenting some practical applications. / Frequentemente a matemática é vista pelos alunos do ensino médio como uma ciência restrita à memorização de fórmulas e conceitos. Portanto, limitante em sua essência. O trabalho busca reverter tal visão através da apresentação de um novo campo de estudos: A Àlgebra Tropical. Área relativamente nova da matemática que guarda a curiosa característica de tratar as operações de adi- ção e multiplicação de forma diferente da tradicional, já apresenta resultados práticos interessantes. A Àlgebra Tropical será apresentada de forma didática, comparando-a com a álgebra tradicional e mostrando as consequências das operações tropicais no estudo dos polinômios, matrizes e geometria, além de apresentar algumas aplicações práticas.

Max-plus代数は，実数全体に無限小元を付加した集合に，加法として最大値をとる演算，乗法として通常の加法を考えた代数系である．本論文では，max-plus線形方程式に対するCramerの公式の類似物を用いて，線形方程式の解空間の基底が構成できることを示した．さらに固有値問題に関連して，max-plus行列の固有ベクトルの概念を2通りの観点から拡張した． / The max-plus algebra is the semiring with addition "max" and multiplication "+". In the present thesis, the author gives a combinatorial characterization of solutions of linear systems in terms of the max-plus Cramer's rule. Further, the author extends the concept of eigenvectors of max-plus matrices from two different perspectives. / 博士(理学) / Doctor of Philosophy in Science / 同志社大学 / Doshisha University

No description available.

Le travail présenté s'inscrit dans le contexte de la théorie des systèmes linéaires dans les dioïdes. La motivation initiale de cette étude a été de contribuer à l'analyse et la commande de systèmes linéaires dans max-plus en utilisant spécifiquement une approche géométrique. La contribution de cette thèse est centrée sur deux problèmes. La première partie est dédiée à l'étude de la relation entre les notions d'invariance contrôlée et d'invariance contrôlée par retour d'état dynamique dans un semi-anneau. Cette relation permet de montrer l'équivalence de ces deux notions. La deuxième partie concerne un problème original dans la théorie des systèmes linéaires dans max-plus, il s'agit de la synthèse d'une loi de commande par retour d'état, qui permette de satisfaire un ensemble de spécifications exprimées sous la forme de restrictions sur l'état du système, avec une approche géométrique. Il s'agit plus précisément de commander des systèmes à événements discrets décrits par un modèle linéaire dans max-plus. Nous définissons et caractérisons l'ensemble des conditions initiales admissibles, lesquelles sont à l'origine de solutions non décroissantes. Les restrictions temporelles imposées à l'espace d'état du système sont décrites par le semi-module défini par l'image de l'étoile de Kleene de la matrice associée aux restrictions temporelles. Les propriétés géométriques de ce semi-module permettant de garantir que l'évolution du système en boucle fermée satisfasse les restrictions sont étudiées. Des conditions suffisantes concernant l'existence d'une loi de commande causale par retour d'état statique sont présentées. Le calcul des lois de commande causales est également présenté. Pour illustrer l'application de cette approche, deux problèmes de commande sont présentés. / This work is in the context of the theory of linear Systems in the dioids. The initial motivation of this study was to contribute to the analysis and control of max-plus linear systems, specifically using a geometric approach. The contribution of this thesis focuses on two issues. The first part is dedicated to study of the relationship between the concepts of controlled invariance and dynamic state feedback controlled invariance in a semi-ring. This relationship allows us to show the equivalence of these two concepts. The second part relates to a new problem in the theory of max-plus linear systems, it is the synthesis, with a geometric approach, of a static state feedback control law, in order to satisfy a set of specifications that apply to the state space of the system. This is specifically to control of discrete event systems described by a linear model in max-plus. We define and characterize the set of admissible initial conditions, which are the cause of non-decreasing solutions. Temporal restrictions on the system state space are described by the semi-module defined by the image of the Kleene star of the matrix associated with time restrictions. The geometric properties of this semi-module are studied. Sufficient conditions for the existence of a causal control law by static feedback are presented. Calculating causal control laws is also presented. To illustrate the application of this approach, two control problems are presented.

L'Algèbre tropicale peut être considérée comme un domaine relativement nouveau en mathématiques. Elle apparait dans plusieurs domaines telles que l'optimisation, la synchronisation de la production et du transport, les systèmes à événements discrets, le contrôle optimal, la recherche opérationnelle, etc. La première partie de ce manuscrit est consacrée a l'étude des applications de l'algèbre tropicale à l'analyse numérique matricielle. Nous considérons tout d'abord le problème classique de l'estimation des racines d'un polynôme univarié. Nous prouvons plusieurs nouvelles bornes pour la valeur absolue des racines d'un polynôme en exploitant les méthodes tropicales. Ces résultats sont particulièrement utiles lorsque l'on considère des polynômes dont les coefficients ont des ordres de grandeur différents. Nous examinons ensuite le problème du calcul des valeurs propres d'une matrice polynomiale. Ici, nous introduisons une technique de mise à l'échelle générale, basée sur l'algèbre tropicale, qui s'applique en particulier à la forme compagnon. Cette mise à l'échelle est basée sur la construction d'une fonction polynomiale tropicale auxiliaire, ne dépendant que de la norme des matrices. Les raciness (les points de non-différentiabilité) de ce polynôme tropical fournissent une pré-estimation de la valeur absolue des valeurs propres. Ceci se justifie en particulier par un nouveau résultat montrant que sous certaines hypothèses faites sur le conditionnement, il existe un groupe de valeurs propres bornées en norme. L'ordre de grandeur de ces bornes est fourni par la plus grande racine du polynôme tropical auxiliaire. Un résultat similaire est valable pour un groupe de petites valeurs propres. Nous montrons expérimentalement que cette mise à l'échelle améliore la stabilité numérique, en particulier dans des situations où les données ont des ordres de grandeur différents. Nous étudions également le problème du calcul des valeurs propres tropicales (les points de non-différentiabilité du polynôme caractéristique) d'une matrice polynômiale tropicale. Du point de vue combinatoire, ce problème est équivalent à trouver une fonction de couplage: la valeur d'un couplage de poids maximum dans un graphe biparti dont les arcs sont valués par des fonctions convexes et linéaires par morceaux. Nous avons développé un algorithme qui calcule ces valeurs propres tropicales en temps polynomial. Dans la deuxième partie de cette thèse, nous nous intéressons à la résolution de problèmes d'affectation optimale de très grande taille, pour lesquels les algorithms séquentiels classiques ne sont pas efficaces. Nous proposons une nouvelle approche qui exploite le lien entre le problème d'affectation optimale et le problème de maximisation d'entropie. Cette approche conduit à un algorithme de prétraitement pour le problème d'affectation optimale qui est basé sur une méthode itérative qui élimine les entrées n'appartenant pas à une affectation optimale. Nous considérons deux variantes itératives de l'algorithme de prétraitement, l'une utilise la méthode Sinkhorn et l'autre utilise la méthode de Newton. Cet algorithme de prétraitement ramène le problème initial à un problème beaucoup plus petit en termes de besoins en mémoire. Nous introduisons également une nouvelle méthode itérative basée sur une modification de l'algorithme Sinkhorn, dans lequel un paramètre de déformation est lentement augmenté. Nous prouvons que cette méthode itérative(itération de Sinkhorn déformée) converge vers une matrice dont les entrées non nulles sont exactement celles qui appartiennent aux permutations optimales. Une estimation du taux de convergence est également présentée.