Algorithmic Solutions for Combinatorial Problems in Resource Management of Manufacturing Environments

This thesis studies the use of heuristic algorithms in a number of combinatorial problems that occur in various resource constrained environments. Such problems occur, for example, in manufacturing, where a restricted number of resources (tools, machines, feeder slots) are needed to perform some operations. Many of these problems turn out to be computationally intractable, and heuristic algorithms are used to provide efficient, yet sub-optimal solutions. The main goal of the present study is to build upon existing methods to create new heuristics that provide improved solutions for some of these problems. All of these problems occur in practice, and one of the motivations of our study was the request for improvements from industrial sources. We approach three different resource constrained problems. The first is the tool switching and loading problem, and occurs especially in the assembly of printed circuit boards. This problem has to be solved when an efficient, yet small primary storage is used to access resources (tools) from a less efficient (but unlimited) secondary storage area. We study various forms of the problem and provide improved heuristics for its solution. Second, the nozzle assignment problem is concerned with selecting a suitable set of vacuum nozzles for the arms of a robotic assembly machine. It turns out that this is a specialized formulation of the MINMAX resource allocation formulation of the apportionment problem and it can be solved efficiently and optimally. We construct an exact algorithm specialized for the nozzle selection and provide a proof of its optimality. Third, the problem of feeder assignment and component tape construction occurs when electronic components are inserted and certain component types cause tape movement delays that can significantly impact the efficiency of printed circuit board assembly. Here, careful selection of component slots in the feeder improves the tape movement speed. We provide a formal proof that this problem is of the same complexity as the turnpike problem (a well studied geometric optimization problem), and provide a heuristic algorithm for this problem.

Algorithmic Techniques in Gene Expression Processing. From Imputation to Visualization

The amount of biological data has grown exponentially in recent decades. Modern biotechnologies, such as microarrays and next-generation sequencing, are capable to produce massive amounts of biomedical data in a single experiment. As the amount of the data is rapidly growing there is an urgent need for reliable computational methods for analyzing and visualizing it. This thesis addresses this need by studying how to efficiently and reliably analyze and visualize high-dimensional data, especially that obtained from gene expression microarray experiments. First, we will study the ways to improve the quality of microarray data by replacing (imputing) the missing data entries with the estimated values for these entries. Missing value imputation is a method which is commonly used to make the original incomplete data complete, thus making it easier to be analyzed with statistical and computational methods. Our novel approach was to use curated external biological information as a guide for the missing value imputation. Secondly, we studied the effect of missing value imputation on the downstream data analysis methods like clustering. We compared multiple recent imputation algorithms against 8 publicly available microarray data sets. It was observed that the missing value imputation indeed is a rational way to improve the quality of biological data. The research revealed differences between the clustering results obtained with different imputation methods. On most data sets, the simple and fast k-NN imputation was good enough, but there were also needs for more advanced imputation methods, such as Bayesian Principal Component Algorithm (BPCA). Finally, we studied the visualization of biological network data. Biological interaction networks are examples of the outcome of multiple biological experiments such as using the gene microarray techniques. Such networks are typically very large and highly connected, thus there is a need for fast algorithms for producing visually pleasant layouts. A computationally efficient way to produce layouts of large biological interaction networks was developed. The algorithm uses multilevel optimization within the regular force directed graph layout algorithm.

Flow injection analysis (FIA) determination of lead by hydride generation in banded coral skeletons /

A flow injection hydride generation direct current plasma atomic emission spectrometric (FI-HG-DCP-AES) method was developed for the determination of lead at ng.ml-l level. Potassium ferricyanide (K3Fe(CN)6) was used along with sodium tetrahydroborate(III) (NaBH4) to produce plumbane (PbH4) in an acid medium. The design of a gas-liquid separator (hydride generator) was tested and the parameters of the flow injection system were optimized to achieve a good detection limit and sample throughput. The technique developed gave a detection limit of 0.7 ng.ml-l(3ob). The precision at 20 ng.ml"* level was 1.6 % RSD with 1 1 measurements (n=l 1). Volume of sample loop was 500 |J.l. A sample throughput of 120 h"^ was achieved. The transition elements, Fe(II), FeOH), Cd(n), Co(II), Mn(n), Ni(II) and Zn(n) do not interfere in this method but 1 mg,l'l Cu(II) will suppress 50 % of the signal from a sample containing 20 ng.ml'l Pb. This method was successfully applied to determine lead in a calcium carbonate (CaC03) matrix of banded coral skeletons from Si-Chang Island in Thailand.

Interpreting Quantifier Scope Ambiguity: Evidence of Heuristic First, Algorithmic Second Processing

The present work suggests that sentence processing requires both heuristic and algorithmic processing streams, where the heuristic processing strategy precedes the algorithmic phase. This conclusion is based on three self-paced reading experiments in which the processing of two-sentence discourses was investigated, where context sentences exhibited quantifier scope ambiguity. Experiment 1 demonstrates that such sentences are processed in a shallow manner. Experiment 2 uses the same stimuli as Experiment 1 but adds questions to ensure deeper processing. Results indicate that reading times are consistent with a lexical-pragmatic interpretation of number associated with context sentences, but responses to questions are consistent with the algorithmic computation of quantifier scope. Experiment 3 shows the same pattern of results as Experiment 2, despite using stimuli with different lexicalpragmatic biases. These effects suggest that language processing can be superficial, and that deeper processing, which is sensitive to structure, only occurs if required. Implications for recent studies of quantifier scope ambiguity are discussed.

Algorithmic Computation of Formal Fourier Series

KAAD (Katholischer Akademischer Ausländer-Dienst)

An algorithmic approach for collaborative-based prediction of user contexts in ubiquitous environments under consideration of legal implications

Mit Hilfe der Vorhersage von Kontexten können z. B. Dienste innerhalb einer ubiquitären Umgebung proaktiv an die Bedürfnisse der Nutzer angepasst werden. Aus diesem Grund hat die Kontextvorhersage einen signifikanten Stellenwert innerhalb des ’ubiquitous computing’. Nach unserem besten Wissen, verwenden gängige Ansätze in der Kontextvorhersage ausschließlich die Kontexthistorie des Nutzers als Datenbasis, dessen Kontexte vorhersagt werden sollen. Im Falle, dass ein Nutzer unerwartet seine gewohnte Verhaltensweise ändert, enthält die Kontexthistorie des Nutzers keine geeigneten Informationen, um eine zuverlässige Kontextvorhersage zu gewährleisten. Daraus folgt, dass Vorhersageansätze, die ausschließlich die Kontexthistorie des Nutzers verwenden, dessen Kontexte vorhergesagt werden sollen, fehlschlagen könnten. Um die Lücke der fehlenden Kontextinformationen in der Kontexthistorie des Nutzers zu schließen, führen wir den Ansatz zur kollaborativen Kontextvorhersage (CCP) ein. Dabei nutzt CCP bestehende direkte und indirekte Relationen, die zwischen den Kontexthistorien der verschiedenen Nutzer existieren können, aus. CCP basiert auf der Singulärwertzerlegung höherer Ordnung, die bereits erfolgreich in bestehenden Empfehlungssystemen eingesetzt wurde. Um Aussagen über die Vorhersagegenauigkeit des CCP Ansatzes treffen zu können, wird dieser in drei verschiedenen Experimenten evaluiert. Die erzielten Vorhersagegenauigkeiten werden mit denen von drei bekannten Kontextvorhersageansätzen, dem ’Alignment’ Ansatz, dem ’StatePredictor’ und dem ’ActiveLeZi’ Vorhersageansatz, verglichen. In allen drei Experimenten werden als Evaluationsbasis kollaborative Datensätze verwendet. Anschließend wird der CCP Ansatz auf einen realen kollaborativen Anwendungsfall, den proaktiven Schutz von Fußgängern, angewendet. Dabei werden durch die Verwendung der kollaborativen Kontextvorhersage Fußgänger frühzeitig erkannt, die potentiell Gefahr laufen, mit einem sich nähernden Auto zu kollidieren. Als kollaborative Datenbasis werden reale Bewegungskontexte der Fußgänger verwendet. Die Bewegungskontexte werden mittels Smartphones, welche die Fußgänger in ihrer Hosentasche tragen, gesammelt. Aus dem Grund, dass Kontextvorhersageansätze in erster Linie personenbezogene Kontexte wie z.B. Standortdaten oder Verhaltensmuster der Nutzer als Datenbasis zur Vorhersage verwenden, werden rechtliche Evaluationskriterien aus dem Recht des Nutzers auf informationelle Selbstbestimmung abgeleitet. Basierend auf den abgeleiteten Evaluationskriterien, werden der CCP Ansatz und weitere bekannte kontextvorhersagende Ansätze bezüglich ihrer Rechtsverträglichkeit untersucht. Die Evaluationsergebnisse zeigen die rechtliche Kompatibilität der untersuchten Vorhersageansätze bezüglich des Rechtes des Nutzers auf informationelle Selbstbestimmung auf. Zum Schluss wird in der Dissertation ein Ansatz für die verteilte und kollaborative Vorhersage von Kontexten vorgestellt. Mit Hilfe des Ansatzes wird eine Möglichkeit aufgezeigt, um den identifizierten rechtlichen Probleme, die bei der Vorhersage von Kontexten und besonders bei der kollaborativen Vorhersage von Kontexten, entgegenzuwirken.

Algorithmic Complexity and Computability

High-level introduction for web science students, rather than for computer science students.

Algorithmic statistical analysis of electrophysiological data for the investigation of structure-activity relationship in single neurons

We are developing computational tools supporting the detailed analysis of the dependence of neural electrophysiological response on dendritic morphology. We approach this problem by combining simulations of faithful models of neurons (experimental real life morphological data with known models of channel kinetics) with algorithmic extraction of morphological and physiological parameters and statistical analysis. In this paper, we present the novel method for an automatic recognition of spike trains in voltage traces, which eliminates the need for human intervention. This enables classification of waveforms with consistent criteria across all the analyzed traces and so it amounts to reduction of the noise in the data. This method allows for an automatic extraction of relevant physiological parameters necessary for further statistical analysis. In order to illustrate the usefulness of this procedure to analyze voltage traces, we characterized the influence of the somatic current injection level on several electrophysiological parameters in a set of modeled neurons. This application suggests that such an algorithmic processing of physiological data extracts parameters in a suitable form for further investigation of structure-activity relationship in single neurons.

Investigating affect in algorithmic composition systems

There has been a significant amount of work implementing systems for algorithmic composition with the intention of targeting specific emotional responses in the listener, but a full review of this work is not currently available. This gap creates a shared obstacle to those entering the field. Our aim is thus to give an overview of progress in the area of these affectively driven systems for algorithmic composition. Performative and transformative systems are included and differentiated where appropriate, highlighting the challenges these systems now face if they are to be adapted to, or have already incorporated, some form of affective control. Possible real-time applications for such systems, utilizing affectively driven algorithmic composition and biophysical sensing to monitor and induce affective states in the listener are suggested.

An algorithmic of analog-to-digital converter using current-mode and digital CMOS process

In this paper a new algorithmic of Analog-to-Digital Converter is presented. This new topology use the current-mode technique that allows a large dynamic range and can be implemented in digital CMOS process. The ADC proposed is very small and can handle high sampling rates. Simulation results using a 1.2um CMOS process show that an 8-b ADC can support a sampling rate of 50MHz.

Automatic identification of terpenoid skeletons by feed-forward neural networks

Feed-forward neural networks (FFNNs) were used to predict the skeletal type of molecules belonging to six classes of terpenoids. A database that contains the (13)C NMR spectra of about 5000 compounds was used to train the FFNNs. An efficient representation of the spectra was designed and the constitution of the best FFNN input vector format resorted from an heuristic approach. The latter was derived from general considerations on terpenoid structures. (c) 2006 Elsevier B.V. All rights reserved.