No description available.

Tvarkaraščių sudarymo uždaviniai – viena iš sunkiau sprendžiamų problemų, kylančių įvairiose gamybinėse struktūrose, grupė. Darbo pradžioje supažindinama su bendrais tvarkaraščių sudarymo uždavinių bruožais ir jų sprendimo algoritmais. Detaliau nagrinėti šiame darbe parenkamas vienas sunkiausių gamybinių tvarkaraščių ir apskritai kombinatorinių optimizavimo uždavinių – darbo fabriko uždavinys (angl. job shop scheduling problem), kuris be abejo nėra tiksliai sprendžiamas per polinominį sprendimo laiką. Šio uždavinio pradiniai duomenys yra duotos darbų ir įrenginių aibės. Kiekvienas darbas apdorojamas specifine įrenginių tvarka. Uždavinio tikslas – minimizuoti visų darbų atlikimo laiką. Šiam uždaviniui spręsti pristatėme du apytikslius tabu – atkaitinimo modeliavimo bei paieškos kintamose aplinkose algoritmus, priklausančius metaeuristinių metodų šeimai. Iš tabu – atkaitinimo modeliavimo galima nesunkiai gauti paprastą tabu paiešką, tad prie dviejų minėtų algoritmų galima pridėti ir paprastąją tabu paiešką. Šiame darbe atlikta minėtų algoritmų programinė realizacija. Pristatytų algoritmų efektyvumui įvertinti ir algoritmų parametrų parinkimo rekomendacijoms pateikti, buvo pasirinkti gerai literatūroje žinomi bei sunkiau sprendžiami etaloniniai darbo fabriko uždavinių pavyzdžiai. Darbo pabaigoje pateikiamos minėtų algoritmų parametrų parinkimo rekomendacijos ir aptariamas algoritmų efektyvumas, kuris nagrinėtuose uždaviniuose nebuvo pastovus minėtų trijų algoritmų atvejais, t... [toliau žr. visą tekstą] / At the beginning of this work we introduce to the combinatorial optimization, scheduling problems and methods used to solve them. In computer science scheduling problems is considered strongly NP-complete. The combinatorial optimization problem considered in this paper is a static job shop problem scheduling arising in the manufacturing processes. In the static job shop scheduling problem, a finite number of jobs are to be processed by a finite number of machines. Each job consists of a prederminated sequence of task operations, each of which needs to be processed without preemption for a given period of time on a given machine. Tasks of the same job cannot be processed concurrently and each job must visit each machine exactly once. A schedule is an assignment of operation to time slots on a machine. The makespan is the maximum completion time of the jobs and the objective of the job shop scheduling problem is to find a schedule that minimizes the makespan. When the size of problem increases, the computational time of the exact methods grows exponentially. Therefore, the recent research on job shop and other scheduling problems is focused on heuristic algorithms. We also presented some meta-heuristic algorithms such as Tabu search – Simulated annealing (TS/SA), Tabu Search (TS), Variable Neighborhood Search (VNS) and showed their results on some job shop instances. At the end of this work we tell recommendations about choosing suitable parameters.

Clad alloys feature one or more different alloys bonded to the outside of a core alloy, with non-equilibrium, interalloy interfaces. There is limited understanding of the recovery and recrystallization behaviour of cold rolled clad aluminum alloys. In order to optimize the properties of such alloys, new heat treatment processes may be required that differ from what is used for the monolithic alloys. This study examines the recovery behaviour of a cold rolled Novelis FusionTM alloy containing an AA6XXX core with an AA3003 cladding on one side. The bond between alloys appears microscopically discrete and continuous, but has a 30 m wide chemical gradient. The as-deformed structure at the interalloy region consists of pancaked sub-grains with dislocations at the misorientation boundaries and a lower density organized within the more open interiors. X-ray line broadening was used to extract the dislocation density from the interalloy region and an equivalently deformed AA6XXX following static annealing using a modified Williamson-Hall analysis. This analysis assumed that Gaussian broadening contributions in a pseudo-Voigt function corresponded only to strain from dislocations. The kinetics of the dislocation density evolution to recrystallization were studied isothermally at 2 minute intervals, and isochronally at 175 and 205°C. The data fit the Nes model, in which the interalloy region recovered faster than AA6XXX at 175°C, but was slower at 205°C. This was most likely caused by change in texture and chemistry within this region such as over-aging of AA6XXX . Simulation of a continuous annealing and self homogenization process both with and without pre-recovery indicates a detectable, though small change in the texture and grain size in the interalloy region. / Thesis (Master, Mechanical and Materials Engineering) -- Queen's University, 2013-10-02 10:19:10.279

Growth mechanism of electroplated copper columns has been systematically studied by simulations and characterizations. A two-dimensional cross-sectional kinetic Monte Carlo (2DCS-KMC) model has been developed to simulate the electrodeposition of single crystal copper. The evolution of the microstructure has been visualized. The cluster density, average cluster size, variance of the cluster size and average aspect ratio were obtained from the simulations. The growth history of the deposition from the first atom to an equivalent of 100 monolayers was reconstructed. Following the single-lattice 2DCS-KMC model for a single crystal, a two-dimensional cross-sectional poly-lattice kinetic Monte Carlo (2DCSP-KMC) model has been developed for simulation of the electrodeposition of polycrystalline copper on both a copper and a gold substrate. With this model, the early-stage nucleation and the grain growth after impingement of nuclei can be simulated; as such the entire growth history is reconstructed in terms of the evolution of microstructure, grain statistics and grain boundary misorientation. The model is capable of capturing some key aspects of nucleation and growth mechanisms including the nucleation type (e.g. homogeneous or heterogeneous), texture development, the growth of grains and higher energetic state of grain boundaries. The model has also proven capable of capturing the effects of deposition parameters including applied electrode potential, concentration of cupric ions and temperature. Their effects are largely dependent on the substrates. The early-stage electrocrystallization of Cu on polycrystalline Au has been studied by ex-situ AFM observations. The evolution of surface morphology of the electrodeposited copper on a sputtered Au seed layer from 16ms to 1000s was observed and their formation mechanism discussed. The heterogeneous nucleation phenomenon, the competitive growth both longitudinally and laterally, and the dominant growth of some nuclei were experimentally observed, which are also visualized by the relevant KMC simulation results at a smaller size scale and a shorter time scale. A heuristic model is therefore proposed to describe the mechanism of the early-stage electrocrystallization of Cu on a polycrystalline Au seed layer. Electroplated copper columns plated for different times have been characterized in terms of the evolution of their external morphology, cross-sectional microstructure and crystal structure. The microstructure of electroplated copper columns is characteristic of bi-modal or tri-modal grain size distribution. The results indicate that recrystallization has occurred during or after the plating, top-down and laterally. Slight changes of the crystal structure were observed by in-situ XRD and it was found that the changes of the (111) and (200) planes occurred at different stages of self-annealing. Finally, the results indicate the presence of organic additives is not essential for self-annealing of a copper column to occur.

Traditional clustering algorithms have different criteria and biases, and there is no single algorithm that can be the best solution for a wide range of data sets. This problem often presents a significant obstacle to analysts in revealing meaningful information buried among the huge amount of data. Ensemble Clustering has been proposed as a way to avoid the biases and improve the accuracy of clustering. The difficulty in developing Ensemble Clustering methods is to combine external information (provided by input clusterings) with internal information (i.e. characteristics of given data) effectively to improve the accuracy of clustering. The work presented in this thesis focuses on enhancing the clustering accuracy of Ensemble Clustering by employing heuristic optimisation techniques to achieve a robust combination of relevant information during the consensus clustering stage. Two novel heuristic optimisation-based Ensemble Clustering methods, Multi-Optimisation Consensus Clustering (MOCC) and K-Ants Consensus Clustering (KACC), are developed and introduced in this thesis. These methods utilise two heuristic optimisation algorithms (Simulated Annealing and Ant Colony Optimisation) for their Ensemble Clustering frameworks, and have been proved to outperform other methods in the area. The extensive experimental results, together with a detailed analysis, will be presented in this thesis.

Kesterite Cu2ZnSnS4 (CZTS) is interesting as a sustainable photovoltaic technology due to its earth-abundant elements and suitable semiconducting properties. To date, a record efficiency of 12.6% has been achieved but further improvements are required to reach high efficiency for industrial implementation. Among the limiting issues is the understanding of the annealing process, which is crucial in promoting high material quality. In particular, the knowledge of the effects of segregated secondary compounds on solar cell performance is lacking. In contrast to formation of ZnS particles throughout CZTS film, it is notable that SnS forms and usually segregates on the CZTS top and rear surfaces. The influence of SnS on CZTS solar cells was studied by electron beam induced current measurements. It is found that SnS presence on the CZTS surfacecan introduce “dead area”, whereas it seems beneficial for solar cell current when accumulates on the CZTS rear. For SnS passivation and from investigation of the passivation effect from an Al2O3 thin layer at the CZTS rear, improvement in overall device performance could not be demonstrated, due to either poor CZTS bulk or non-optimal device structure. The limitation in CZTS bulk quality was shown from a thickness study where carrier collection saturated already about 700-1000 nm CZTS thickness. Formation of SnS alongside CZTS implies the anneal is limited by a deficient sulfur partial pressure (PS2). By looking into Sn-S phase transformations in SnS2 films after annealing, we find that PS2 drops rapidly over the annealing time, which could be well-correlated to a series of changes in CZTS material quality including secondary phase formations and defect modifications. It is shown that annealing CZTS under sufficiently high PS2 is critical for CZTS solar cells with high open circuit voltage (upto 783mV was reached), possibly due to the defect modification. Besides SnS, it is observed that NaxS compounds are also readily formed on CZTS surfaces, due to Na diffusion from the glass substrate during annealing. NaxS negatively affects the formation of the CdS/CZTS interface during chemical bath deposition. It can be removed by an oxidation process or wet chemical etching.

Les génomes de bactériophages ont une capacité remarquable d’évolution. L’objectif de ma thèse a été d’étudier le rôle des recombinases de bactériophages dans cette évolution. Notre hypothèse était que les recombinases phagiques diffèrent de la recombinase bactérienne RecA par une fidélité relâchée lors de la réaction de recherche d’homologie, qui pourrait expliquer en partie la très grande plasticité des génomes de bactériophages. Nous avons tout d’abord utilisé une approche bioinformatique basée sur la recherche d’homologies lointaines pour prédire un maximum de gènes de recombinases dans les génomes entièrement séquencés, puis nous avons confirmé l’activité de recombinaison de certaines d’entre elles, par un test d’appariement d’ADN simple brin entre séquences identiques in vivo. Ceci nous a permis de conclure qu’il existait trois superfamilles de recombinases chez les bactériophages, de type Rad52, Rad51/RecA et Gp2.5, présentes dans 42% des 465 génomes analysés. Dans un deuxième temps, nous avons comparé six de ces recombinases à RecA et avons montré que toutes étaient capables de faire de l’appariement simple brin in vivo, contrairement à RecA. Pour deux d’entre elles, Redβ de Lambda (type Rad52) et Sak4 de HK620 (type Rad51/RecA), nous avons observé que l’appariement simple brin continuait à se produire, avec une efficacité diminuée, jusqu’à 13% de divergence entre les séquences. L’appariement d’ADN simple brin est donc une propriété commune aux recombinases de bactériophages qui les distingue de RecA, et semble pouvoir se maintenir pour un niveau élevé de divergence, ce qui soutient l’hypothèse d’une recombinaison homologue différente et plus relâchée dans sa fidélité chez les bactériophages. / Bacteriophage genomes have a remarkable ability to evolve. The aim of my thesis was to study the role of bacteriophage recombinases in this evolution. Our hypothesis was that such recombinases differ from the bacterial RecA recombinase by a relaxed fidelity during homology search, which may partly explain the high plasticity of bacteriophage genomes. We first used a bioinformatics approach based on remote homology search to predict a maximum of recombinase genes in completely sequenced genomes, and confirmed the recombination activity of some of them by a single-strand DNA annealing assay between identical sequences in vivo. This allowed us to conclude that there were three superfamilies of bacteriophage recombinases, Rad52-like, Rad51/RecA-like and Gp2.5-like, which were present in 42% of the 465 genomes analyzed. In a second step, we compared six of these recombinases to RecA and showed that all were able to anneal single-stranded DNA in vivo, in contrast to RecA. For two of them, Redβ of Lambda (Rad52-like) and Sak4 of HK620 (Rad51/RecAlike), we also observed that they were able to anneal non identical (13% of divergence) single-stranded DNA, with a reduced efficiency. We conclude that the single-stranded DNA annealing is a property common to recombinases of bacteriophages, which is absent in RecA, and seems to tolerate diverged sequences. This supports the hypothesis of a different and more relaxed recombination in bacteriophages.

Call number: LD2668 .T4 1986 Y36 / Master of Science / Physics

A dissertation submitted in partial ful lment of the degree of Master of Science in Engineering (Electrical) (50/50) in the Faculty of Engineering and the Built Environment Department of Electrical and Information Engineering May 2017 / Numerous applications in a wide variety of elds has resulted in a rich history of research into optimisation for scheduling. Although it is a fundamental form of the problem, the single machine scheduling problem with two or more objectives is known to be NP-hard. For this reason we consider the single machine problem a good test bed for solution algorithms. While there is a plethora of research into various aspects of scheduling problems, little has been done in evaluating the performance of the Simulated Annealing algorithm for the fundamental problem, or using it in combination with other techniques. Speci cally, this has not been done for minimising total weighted earliness and tardiness, which is the optimisation objective of this work. If we consider a mere ten jobs for scheduling, this results in over 3.6 million possible solution schedules. It is thus of de nite practical necessity to reduce the search space in order to nd an optimal or acceptable suboptimal solution in a shorter time, especially when scaling up the problem size. This is of particular importance in the application area of packet scheduling in wireless communications networks where the tolerance for computational delays is very low. The main contribution of this work is to investigate the hypothesis that inserting a step of pre-sampling by Markov Chain Monte Carlo methods before running the Simulated Annealing algorithm on the pruned search space can result in overall reduced running times. The search space is divided into a number of sections and Metropolis-Hastings Markov Chain Monte Carlo is performed over the sections in order to reduce the search space for Simulated Annealing by a factor of 20 to 100. Trade-o s are found between the run time and number of sections of the pre-sampling algorithm, and the run time of Simulated Annealing for minimising the percentage deviation of the nal result from the optimal solution cost. Algorithm performance is determined both by computational complexity and the quality of the solution (i.e. the percentage deviation from the optimal). We nd that the running time can be reduced by a factor of 4.5 to ensure a 2% deviation from the optimal, as compared to the basic Simulated Annealing algorithm on the full search space. More importantly, we are able to reduce the complexity of nding the optimal from O(n:n!) for a complete search to O(nNS) for Simulated Annealing to O(n(NMr +NS)+m) for the input variables n jobs, NS SA iterations, NM Metropolis- Hastings iterations, r inner samples and m sections. / MT 2017

Os problemas de corte e empacotamento são muito comuns nas indústrias e na logística. Dado um conjunto de N itens com diferentes pesos e um conjunto de M contentores com capacidade C, o problema de empacotamento unidimensional consiste em determinar o menor número de contentores a serem utilizados para alocar todos os itens respeitando a restrição de capacidade dos contentores. Nesse estudo pretende-se resolver o problema com instâncias benchmark da literatura, por meio de sessenta heurísticas diferentes, que são comparadas a quatro limitantes inferiores propostos na literatura com o intuito de avaliar a qualidade da solução heurística. Quatro limitantes inferiores e dez heurísticas construtivas diferentes foram programados em C++ num mesmo ambiente computacional, permitindo sua comparação tanto em termos de qualidade das soluções, quanto em termos dos tempos de processamento. Uma heurística simples de troca de itens entre contentores chamada Diferença-de-Quadrados foi proposta para melhorar as soluções iniciais do problema. A metaheurística simulated annealing foi acionada para melhorar a solução inicial quando o limitante inferior não foi atingido. Os parâmetros dos simulated annealing foram determinados com os dados das instâncias de forma diferente da utilizada na literatura. As combinações entre as dez soluções iniciais, a heurística Diferença-de-Quadrados e o simulated annealing geraram um conjunto de sessenta heurísticas diferentes. Os resultados mostraram que o algoritmo proposto é eficiente para resolver o problema com tempos de processamento adequados a tomada de decisão. / Cutting and packing problems are very common in industries and logistics. Given a set of N items with different weights and a set of M bins with full capacity C, the one-dimensional bin packing problem consists of determining the smallest number of bins capable to allocate all items respecting the capacity constraint of the bins. that impose that the sum of the weights of the items allocated to the bin is less than or equal to their capacity. In this study we intend to solve the problem with benchmark instances of the literature, by means of sixty different heuristics, which are compared to four lower bounds proposed in the literature in order to evaluate the quality of the heuristic solution. Four lower bounds and ten different constructive heuristics were programmed in C++ in the same computational environment, allowing their comparison both in terms of the quality of the solutions and in terms of processing times. A simple heuristic of item exchange between bins called Difference-of-Squares was proposed to improve the initial solutions of the problem. The simulated annealing metaheuristic was triggered to improve the initial solution when the lower bounds was not reached. The parameters of the simulated annealing were determined with the data of the instances differently from that used in the literature. The combinations of the ten initial solutions, the Difference-of-Squares heuristic and the simulated annealing generated a set of sixty different heuristics. The results showed that the proposed algorithm is efficient to solve the problem with adequate processing times for decision making.