In semiconductor manufacturing, wafers are grouped into lots and sent to a separate facility for assembly and test (AT) before being shipped to the customer. Up to a dozen operations are required during AT. The facility in which these operations are performed is a reentrant flow shop consisting of several dozen to several hundred machines and up to a thousand specialized tools. Each lot follows a specific route through the facility, perhaps returning to the same machine multiple times. Each step in the route is referred to as a "pass." Lots in work in process (WIP) that have more than a single step remaining in their route are referred to as multi-pass lots. The multi-pass scheduling problem is to determine machine setups, lot assignments and lot sequences to achieve optimal output, as measured by four objectives related to key device shortages, throughput, machine utilization, and makespan, prioritized in this order. The two primary goals of this research are to develop a new formulation for the multipass problem and to design a variety of solution algorithms that can be used for both planning and real-time control. To begin, the basic AT model considering only single-pass scheduling and the previously developed greedy randomized adaptive search procedure (GRASP) along with its extensions are introduced. Then two alternative schemes are proposed to solve the multipass scheduling problem. In the final phase of this research, an efficient procedure is presented for prioritizing machine changeovers in an AT facility on a periodic basis that provides real-time support. In daily planning, target machine-tooling combinations are derived based on work in process, due dates, and backlogs. As machines finish their current lots, they need to be reconfigured to match their targets. The proposed algorithm is designed to run in real time. / text

This research contributes to the state of the art and state of the practice in solving a very important and computationally challenging problem in the areas of urban transportation systems, operations research, disaster management, and public policy. Being a very active topic of research during the past few decades, the problem of developing an efficient and practical strategy for evacuation of real-sized urban traffic networks in case of disasters from different causes, quickly enough to be employed in immediate disaster management scenarios, has been identified as one of the most challenging and yet vital problems by many researchers. More specifically, this research develops fast methods to find the optimal integrated strategy for traffic routing and traffic signal control to evacuate real-sized urban networks in the most efficient manner. In this research a solution framework is proposed, developed and tested which is capable of solving these problems in very short computational time. An efficient relaxation-based decomposition method is proposed, implemented for two evacuation integrated routing and signal control model formulations, proven to be optimal for both formulations, and verified to reduce the computational complexity of the optimal integrated routing and signal control problem. The efficiency of the proposed decomposition method is gained by reducing the integrated optimal routing and signal control problem into a relaxed optimal routing problem. This has been achieved through an insight into intersection flows in the optimal routing solution: in at least one of the optimal solutions of the routing problem, each street during each time interval only carries vehicles in at most one direction. This property, being essential to the proposed decomposition method, is called "unidirectionality" in this dissertation. The conditions under which this property exists in the optimal evacuation routing solution are identified, and the existence of unidirectionality is proven for: (1) the common Single-Destination System-Optimal Dynamic Traffic Assignment (SD-SODTA) problem, with the objective to minimize the total time spent in the threat area; and, (2) for the single-destination evacuation problem with varying threat levels, with traffic models that have no spatial queue propagation. The proposed decomposition method has been implemented in compliance with two widely-accepted traffic flow models, the Cell Transmission Model (CTM) and the Point Queue (PQ) model. In each case, the decomposition method finds the optimal solution for the integrated routing and signal control problem. Both traffic models have been coded and applied to a realistic real-size evacuation scenario with promising results. One important feature that is explored is the incorporation of evacuation safety aspects in the optimization model. An index of the threat level is associated with each link that reflects the adverse effects of traveling in a given threat zone on the safety and health of evacuees during the process of evacuation. The optimization problem is then formulated to minimize the total exposure of evacuees to the threat. A hypothetical large-scale chlorine gas spill in a high populated urban area (downtown Tucson, Arizona) has been modeled for testing the evacuation models where the network has varying threat levels. In addition to the proposed decomposition method, an efficient network-flow solution algorithm is also proposed to find the optimal routing of traffic in networks with several threat zones, where the threat levels may be non-uniform across different zones. The proposed method can be categorized in the class of "negative cycle canceling" algorithms for solving minimum cost flow problems. The unique feature in the proposed algorithm is introducing a multi-source shortest path calculation which enables the efficient detection and cancellation of negative cycles. The proposed method is proven to find the optimal solution, and it is also applied to and verified for a mid-size test network scenario.

Κατά την διάδοση του σήματος στα οπτικά δίκτυα η ποιότητα του λαμβανόμενου σήματος εξασθενεί λόγω των διαφόρων ειδών απωλειών που υπεισέρχονται κατά τη μετάδοση. Οι κυριότερες εξ’ αυτών είναι: ο θόρυβος λόγω των οπτικών ενισχυτών, η διαφωνία, η χρωματική διασπορά, η διασπορά τρόπων πόλωσης, η μείξη τεσσάρων κυμάτων, η αυτοδιαμόρφωση φάσης κτλ. Προκειμένου να επιτευχθεί αποδεκτή ποιότητα λαμβανόμενου σήματος στον δέκτη είναι απαραίτητη, ιδιαίτερα για μεγάλα μονοπάτια, η χρήση οπτικών 3R αναγεννητών σε κάποιους ενδιάμεσους κόμβους για την περιοδική αναμετάδοση του σήματος. Στην παρούσα διπλωματική εργασία σχεδιάζονται και υλοποιούνται στατικοί αλγόριθμοι δρομολόγησης και ανάθεσης μηκών κύματος για ημιδιαφανή οπτικά δίκτυα. Συγκεκριμένα, θεωρώντας μια δικτυακή τοπολογία, έναν αριθμό διαθέσιμων μηκών κύματος, μια μήτρα κίνησης και μια (αραιή) τοπολογία 3R αναγεννητών για το εξεταζόμενο δίκτυο (ή εκφράζοντάς το διαφορετικά έναν αριθμό ελεύθερων πομποδεκτών για κάθε κόμβο του δικτύου) επιχειρείται η μεγιστοποίηση του αριθμού των συνδέσεων που μπορούν να επιτευχθούν, διατηρώντας παράλληλα την επιθυμητή ποιότητα μετάδοσης. Έτσι, το πρόβλημα της επιλογής της ακολουθίας των αναγεννητών μέσα από τους οποίους θα δρομολογηθεί η κάθε αδιαφανής αίτηση σύνδεσης, μοντελοποιείται σαν ένα πρόβλημα εικονικής τοπολογίας (virtual topology problem). Στην συνέχεια το πρόβλημα αυτό επιλύεται με τη βοήθεια μιας σειράς αλγορίθμων από πολύπλοκους που βασίζονται σε σχηματισμούς ακέραιου γραμμικού προγραμματισμού (Integer Linear Programming – ILP) έως απλούστερους αλλά πάντα πρακτικούς ως προς την εύρεση λύσης, ευριστικούς αλγόριθμους. Ύστερα από την επιλογή της ακολουθίας των χρησιμοποιούμενων αναγεννητών για κάθε αδιαφανή αίτηση σύνδεσης, η μήτρα κίνησης μετασχηματίζεται σε μια ισοδύναμη διαφανή, όπου κάθε αδιαφανής αίτηση έχει αντικατασταθεί από μια σειρά διαφανών συνδέσεων που τερματίζουν και ξεκινούν από τους συγκεκριμένους 3R κόμβους αναγέννησης. Ακολούθως, εφαρμόζεται ένας διαφανής IA-RWA αλγόριθμος για τη μετασχηματισμένη μήτρα κίνησης, ενώ τυχόν συνδέσεις που μποκάρονται ύστερα από την εφαρμογή του διαφανή αλγορίθμου επαναδρομολογούνται χρησιμοποιώντας τους υπολοιπόμενους αναγεννητές. Η Ποιότητα Μετάδοσης (Quality of Transmission QoT) των δημιουργουμένων lightpaths υπολογίζεται με τη βοήθεια ενός εκτιμητή της παραμέτρου Q του κάθε lightpath. Για την μοντελοποίηση των φυσικών περιορισμών του δικτύου χρησιμοποιούνται αναλυτικές φόρμουλες. Η απόδοση του προτεινόμενου αλγορίθμου υπολογίστηκε διεξάγοντας εξομοιώσεις για μια παραλλαγή του DTnet δικτύου εισάγοντας τη μοναδιαία μήτρα κίνησης. Η απόδοση του αλγορίθμου κρίνεται ικανοποιητική όχι μόνο για μεσαία, αλλά και για μεγάλης κλίμακας δίκτυα παρέχοντας βέλτιστες λύσεις. Το μεγαλύτερο μέρος του χρόνου εκτέλεσης του αλγορίθμου, οφείλεται στον υπολογισμό του διαφανούς IA-RWA αλγόριθμου της δεύτερης φάσης. Σχετικά με την απόδοση των εξεταζόμενων αλγορίθμων της πρώτης φάσης, φαίνεται ότι ο αλγόριθμος που παρουσιάζει τα καλύτερα αποτελέσματα είναι αυτός που ελαχιστοποιεί τον μέγιστο αριθμό των χρησιμοποιούμενων αναγεννητών μεταξύ των διαφορετικών κόμβων αναγέννησης του σήματος. / Physical impairments in optical fiber transmission necessitate the use of regeneration at certain intermediate nodes, at least for certain lengthy lightpaths. We design and implement impairment-aware algorithms for routing and wavelength assignment (IA-RWA) in translucent optical networks. We focus on the offline version of the problem, where we are given a network topology, the available wavelengths, a traffic matrix and a (sparse) placement of 3R regenerators in the network (or, in a slightly different setting, the number of available transceivers at each network switch), and we aim at maximizing the number of connections served with adequate quality of transmission. We formulate the problem of choosing the sequence of regenerators to be used by non-transparent connections as a virtual topology design problem, and address it using various algorithms, ranging from an integer linear program (ILP) to simple heuristic algorithms. Once the sequence of regenerators to be used has been determined, we transform the traffic matrix by replacing non-transparent connections with a sequence of transparent connections that terminate and begin at the specified 3R intermediate nodes. Using the transformed matrix we then apply an IA-RWA algorithm designed for transparent (as opposed to translucent) networks to route the traffic. Connections that are blocked are re-routed using any remaining regenerator(s).

The main problem analyzed in this work was the need to design and create an internal management system for small and medium enterprices, that would meet their particular requests on usability, extensibility and adaptability at available costs. As solution to this problem was deep analysis of available systems of that kind, and creation of our own system, that had met necessary requirements and even more – had some technological improvements, such as reduced number of users actions, necessary to make things done. This was implemented with the help of AJAX programming technique and a special framework, created for this system. This system can be used to manage projects in a small or medium enterprice, collect statistics about projects, staff work, distribute project tasks to staff and monitor the implementation. There also is an oportunity to generate various reports, such as summary of accomplished tasks for every employee, lists of project tasks and their status and so on. This system can be easily installed in any enterprice because of it‘s client – server architecture, where client connects to the server with the help of a web browser, that can be found in every computer, so there is no need to install system in all computers in enterprice. In that way maintenance costs are reduced, because all you have to look after is server with a system on it.

Automation has become increasingly prevalent in all forms of society. Activities that are too difficult for a human or to dangerous can be done by machines which do not share those downsides. In addition, tasks can be scheduled more precisely and accurately. Increases in the autonomy have allowed for a new level of tasks which are completed by teams of automated agents rather than a single one, called cooperative control. This has many benefits; but comes at the cost of increased complexity and coordination. The main thrust of research in this field is problem based, considering communication issues as a secondary feature. There is a gap considering problems in which many changes occur as rapidly as communication and the issues that arise as a result. This is the main motivation. This research presents an approach to cooperative control in highly variable systems and tackles some of the issues present in such a system. One of the most important issues is the communication network itself, which is used as an indicator for how healthy the system is an how well it may react to future changes. Therefore using the network as an input to control allows the system to navigate between conservative and aggressive techniques to improve performance while still maintaining robustness. Results are based on a test bed designed to simulate a wide variety of problem types based on: network type; numbers of actors; frequency of changes; impact of changes and method of change. The developed control method is compared to the baseline case ignoring cooperation as well as an idealized case assuming perfect system knowledge. The baseline represents sacrifices coordination to achieve a high level of robustness at reduced performance while the idealized case represents the best possible performance. The control techniques developed give a performance at least as good as the baseline case if not better for all simulations.

Technologijų pamokose didelė pamokos laiko dalis yra skiriama praktinių užduočių atlikimams. Dėl skirtingo mokinių praktinių gebėjimų lygio atliekamų užduočių mokytojams tampa sunku apibrėžti konkrečius vertinimo kriterijus, skirtus kūrybinių užduočių atlikimo sėkmei ir mokinių pasiekimams pamatuoti. Todėl konstruojant užduočių vertinimo kriterijus, kurie remiasi tarpusavio mokytojo ir mokinio lygiateisiais santykiais, išvengiama neaiškaus vertinimo kriterijų formulavimo. Esant lygiateisiams santykiams mokymas tampa lankstesnis, atsiranda galimybė mokiniams rinktis, daugiau atsakomybės perleidžiama mokiniui, mokymasis tampa sąmoningas, kyla vidinė motyvacija, mokiniai įtraukiami į vertinimą. Užduočių vertinimo kriterijų konstravimo įgyvendinimo galimybės turi būti sudarytos, remiantis vadybine vertinimo komponentų struktūra. Tyrimo problema: užduočių vertinimo kriterijų konstravimas vadybos požiūriu. Darbo tikslas: įvertinti mokytojo ir mokinių užduočių vertinimo kriterijų konstravimą, remiantis vadybine vertinimo komponentų struktūra, technologijų pamokose. Siekiant įgyvendinti darbe iškeltą tikslą ir uždavinius buvo taikomi šie tyrimo metodai: 1. Teoriniai: kontentanalizė – mokslinės, metodologinės literatūros, švietimo dokumentų nagrinėjamos problemos aspektu analizė. 2. Kiekybiniai (T tipo duomenų rinkimo): žvalgomasis tyrimas (klausimynų tikslinimui), anketinė apklausa. 3. Kokybiniai (L tipo duomenų rinkimo): technologijų mokytojų interviu ir atviro tipo klausimai... [toliau žr. visą tekstą] / The practical assignments are given more time at technology classes. Since the level of practical capabilities of students is different, it is difficult for teachers to define criteria to assess assignments designed to measure success and progress of students when they implement creative assignments. Therefore in order to design the assignment assessment criteria based on mutual equal relationship between teacher and student, it is required to avoid formulating criteria the assessment under which is not definite. In case of equal relationships the learning becomes more flexible, Students enable to choose, more responsibility is transferred to student, their learning becomes more sensible, internal motivation gets improved and students are involved into assessment. The capabilities and conditions required to put into practice the assignment assessment criteria shall be defined based on the managing structure for assessing management components. Investigation issue: designing the assignment assessment criteria from the point of management. Work purpose: assessing the designing of the assignment assessment criteria for teacher and students at technology classes to be based on the management structure for assessing the management components. The following investigation methods have been applied to meet the purpose and to implement the tasks defined: 1.Theoretical: content–analysis is to analyze scientific, methodological papers, education documents with reference to the issue... [to full text]

Les problèmes d’optimisation discrète sont pour beaucoup difficiles à résoudre, de par leur nature combinatoire. Citons par exemple les problèmes de programmation linéaire en nombres entiers. Une approche couramment employée pour les résoudre exactement est l’approche de Séparation et Évaluation Progressive. Une approche différente appelée « Resolution Search » a été proposée par Chvátal en 1997 pour résoudre exactement des problèmes d’optimisation à variables 0-1, mais elle reste mal connue et n’a été que peu appliquée depuis. Cette thèse tente de remédier à cela, avec un succès partiel. Une première contribution consiste en la généralisation de Resolution Search à tout problème d’optimisation discrète, tout en introduisant de nouveaux concepts et définitions. Ensuite, afin de confirmer l’intérêt de cette approche, nous avons essayé de l’appliquer en pratique pour résoudre efficacement des problèmes bien connus. Bien que notre recherche n’ait pas abouti sur ce point, elle nous a amené à de nouvelles méthodes pour résoudre exactement les problèmes d’affectation généralisée et de localisation simple. Après avoir présenté ces méthodes, la thèse conclut avec un bilan et des perspectives sur l’application pratique de Resolution Search. / The combinatorial nature of discrete optimization problems often makes them diffi- cult to solve. Consider for instance integer linear programming problems, which are commonly solved using a Branch-and-Bound approach. An alternative approach, Resolution Search, was proposed by Chvátal in 1997 for solving 0-1 optimization problems, but remains little known to this day and as such has seen few practical applications. This thesis attempts to remedy this state of affairs, with partial success. Its first contribution consists in the generalization of Resolution Search to any discrete optimization problem, while introducing new definitions and concepts. Next, we tried to validate this approach by attempting to solve well-known problems efficiently with it. Although our research did not succeed in this respect, it lead us to new methods for solving the generalized assignment and uncapacitated facility location problems. After presenting these methods, this thesis concludes with a summary of our attempts at practical application of Resolution Search, along with further perspectives on this matter. / Thèse réalisée en cotutelle avec l'Université d'Avignon.

Today, many small aerodromes have a hard time surviving economically, and amongst the largest cost is air traffic control. Airlines are cutting costs where they can, and many times this affects the aerodromes as well, e.g. when airlines decide to park remotely instead of at the gate. The project called Remotely Operated Towers, initiated by SESAR and run by Saab and LFV, is aiming to address this problem. The project revolves around remotely providing ATS to aerodromes where it is deemed suitable. A big challenge in this project is how to assign aerodromes to remote tower modules in the remote control centre. There are many ways to do this, but there is only a few ways to do it to achieve the least amount of modules. This thesis aims to find an optimal solution to the challenge mentioned above. The thesis resulted in a model where the user can provide the input of choice, i.e. aerodromes with associated ATS operating hours and movements, for a specific period – and receive the assignment schedule for the modules, saying exactly which aerodrome are to be controlled by which module at what time.

The isoquinoline-catalyzed synthesis of pretended 1H-azirines from phenacyl bromides and N,N\'-dialkylcarbodiimides was repeated. The products do not possess the structure of antiaromatic 1H-azirines, but simple N-acyl-N,N\'-dialkylureas were formed instead. This structural corrigendum was confirmed by the independent synthesis of the known ureas and comparison of their 1H NMR and 13C NMR spectroscopic data in the case of six compounds. Thus,1H-azirines keep their classification as very short-lived intermediates.

Inferring Genetic Regulatory Networks (GRN) from multiple data sources is a fundamental problem in computational biology. Computational models for GRN range from simple Boolean networks to stochastic differential equations. To successfully model GRN, a computational method has to be scalable and capable of integrating different biological data sources effectively and homogeneously. In this thesis, we introduce a novel method to model GRN using Cost-Based Abduction (CBA) and study the relation between CBA and Bayesian inference. CBA is an important AI formalism for reasoning under uncertainty that can integrate different biological data sources effectively. We use three different yeast genome data sources—protein-DNA, protein-protein, and knock-out data—to build a skeleton (unannotated) graph which acts as a theory to build a CBA system. The Least Cost Proof (LCP) for the CBA system fully annotates the skeleton graph to represent the learned GRN. Our results show that CBA is a promising tool in computational biology in general and in GRN modeling in particular because CBA knowledge representation can intrinsically implement the AND/OR logic in GRN while enforcing cis-regulatory logic constraints effectively, allowing the method to operate on a genome-wide scale.Besides allowing us to successfully learn yeast pathways such as the pheromone pathway, our method is scalable enough to analyze the full yeast genome in a single CBA instance, without sub-networking. The scalability power of our method comes from the fact that our CBA model size grows in a quadratic, rather than exponential, manner with respect to data size and path length. We also introduce a new algorithm to convert CBA into an equivalent binary linear program that computes the exact LCP for the CBA system, thus reaching the optimal solution. Our work establishes a framework to solve Bayesian networks using integer linear programming and high order recurrent neural networks through CBA as an intermediate representation.