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.

Kohinan poisto spektrikuvista pehmeillä morfologisilla suodattimilla

Tämän diplomityön tavoitteena oli tutkia kohinan poistoa spektrikuvista käyttäen pehmeitä morfologisia suodattimia. Työssä painotettiin impulssimaisen kohinan suodattamista. Suodattimien toimintaa arvioitiin numeerisesti keskimääräisen itseisarvovirheen, neliövirheen sekä signaali-kohinasuhteen avulla ja visuaalisesti tarkastelemalla suodatettuja kuvia sekä niiden yksittäisiä spektritasoja. Käytettyjä suodatusmenetelmiä olivat suodatus kuvapisteittäin spektrin suunnassa, suodatus koko spektrissä sekä kuutiomenetelmä ja komponenteittainen suodatus. Suodatettavat kuvat sisälsivät joko suola ja pippuri- tai bittivirhekohinaa. Parhaimmat suodatustulokset sekä numeeristen virhekriteerien että visuaalisen tarkastelun perusteella saatiin komponenteittaisella sekä kuvapisteittäisellä menetelmällä. Työssä käytetyt menetelmät on esitetty algoritmimuodossa. Suodatinalgoritmien toteutukset ja suodatuskokeet tehtiin Matlab-ohjelmistolla.

Sadevälkkeen mallinnus ilmavalvontatutkajärjestelmää varten

Tutkat muodostavat Suomen rauhanajan ilmavalvonnan rungon. Ilmatilassa on lentokoneiden lisäksi paljon muitakin kohteita, jotka ilmavalvontatutka havaitsee. Naita ei toivottuja kaikuja kutsutaan välkkeeksi. Sadevälke on tilavuusvälkettä. Tämän työn tarkoituksena on löytää menetelmä tai malli, jolla voitaisiin mallintaa sadevälkkeen vaikutus ilmavalvontatutkassa. Toisaalta myös sadevälkkeen suodatus on työn keskeinen tavoite. Käytettyjä suodatusmenetelmiä olivat adaptiivinen suodatus ja doppler-suodatus. Suodinpankkiin eli doppler-suodatukseen lisättiin vielä CFAR Työn tuloksena voi todeta, että sadevälkkeen suodatus onnistui hyvin mutta itse sadevälkkeen mallintamista tulee kehittää edelleen. Työssä käytetyt menetelmät on esitetty algoritmimuodossa. Mittausaineiston keräys suoritettiin keskivalvontatutkalla ja SP-testerillä. Varsinaiset suodatuskokeet ja mallin testaus tehtiin Matlab-ohjelmistolla.

Multilevel converter modulation: implementation and analysis

Multilevel converters provide an attractive solution to bring the benefits of speed-controlled rotational movement to high-power applications. Therefore, multilevel inverters have attracted wide interest in both the academic community and in the industry for the past two decades. In this doctoral thesis, modulation methods suitable especially for series connected H-bridge multilevel inverters are discussed. A concept of duty cycle modulation is presented and its modification is proposed. These methods are compared with other well-known modulation schemes, such as space-vector pulse width modulation and carrier-based modulation schemes. The advantage of the modified duty-cycle modulation is its algorithmic simplicity. A similar mathematical formulation for the original duty cycle modulation is proposed. The modified duty cycle modulation is shown to produce well-formed phase-to-neutral voltages that have lower total harmonic distortion than the space-vector pulse width modulation and the duty cycle modulation. The space-vector-based solution and the duty cycle modulation, on the other hand, result in a better-quality line-to-line voltage and current waveform. The voltage of the DC links in the modules of the series-connected H-bridge inverter are shown to fluctuate while they are under load. The fluctuation causes inaccuracies in the voltage production, which may result in a failure of the flux estimator in the controller. An extension for upper-level modulation schemes, which changes the switching instants of the inverter so that the output voltage meets the reference voltage accurately regardless of the DC link voltages, is proposed. The method is shown to reduce the error to a very low level when a sufficient switching frequency is used. An appropriate way to organize the switching instants of the multilevel inverter is to make only one-level steps at a time. This causes restrictions on the dynamical features of the modulation schemes. The produced voltage vector cannot be rotated several tens of degrees in a single switching period without violating the above-mentioned one-level-step rule. The dynamical capabilities of multilevel inverters are analyzed in this doctoral thesis, and it is shown that the multilevel inverters are capable of operating even in dynamically demanding metal industry applications. In addition to the discussion on modulation schemes, an overvoltage in multilevel converter drives caused by cable reflection is addressed. The voltage reflection phenomenon in drives with long feeder cables causes premature insulation deterioration and also affects the commonmode voltage, which is one of the main reasons for bearing currents. Bearing currents, on the other hand, cause fluting in the bearings, which results in premature bearing failure. The reflection phenomenon is traditionally prevented by filtering, but in this thesis, a modulationbased filterless method to mitigate the overvoltage in multilevel drives is proposed. Moreover, the mitigation method can be implemented as an extension for upper-level modulation schemes. The method exploits the oscillations caused by two consecutive voltage edges so that the sum of the oscillations results in a mitigated peak of the overvoltage. The applicability of the method is verified by simulations together with experiments with a full-scale prototype.

Teaching mathematics and programming : new approaches with empirical evaluation

Programming and mathematics are core areas of computer science (CS) and consequently also important parts of CS education. Introductory instruction in these two topics is, however, not without problems. Studies show that CS students find programming difficult to learn and that teaching mathematical topics to CS novices is challenging. One reason for the latter is the disconnection between mathematics and programming found in many CS curricula, which results in students not seeing the relevance of the subject for their studies. In addition, reports indicate that students' mathematical capability and maturity levels are dropping. The challenges faced when teaching mathematics and programming at CS departments can also be traced back to gaps in students' prior education. In Finland the high school curriculum does not include CS as a subject; instead, focus is on learning to use the computer and its applications as tools. Similarly, many of the mathematics courses emphasize application of formulas, while logic, formalisms and proofs, which are important in CS, are avoided. Consequently, high school graduates are not well prepared for studies in CS. Motivated by these challenges, the goal of the present work is to describe new approaches to teaching mathematics and programming aimed at addressing these issues: Structured derivations is a logic-based approach to teaching mathematics, where formalisms and justifications are made explicit. The aim is to help students become better at communicating their reasoning using mathematical language and logical notation at the same time as they become more confident with formalisms. The Python programming language was originally designed with education in mind, and has a simple syntax compared to many other popular languages. The aim of using it in instruction is to address algorithms and their implementation in a way that allows focus to be put on learning algorithmic thinking and programming instead of on learning a complex syntax. Invariant based programming is a diagrammatic approach to developing programs that are correct by construction. The approach is based on elementary propositional and predicate logic, and makes explicit the underlying mathematical foundations of programming. The aim is also to show how mathematics in general, and logic in particular, can be used to create better programs.

Automatisoidun kaupankäynnin vaikutukset markkinatehokkuuteen

Tutkielmassa selvitettiin algoritmisen kaupankäynnin vaikutuksia markkinatehokkuuteen. Se toteutettiin kirjallisuuskatsauksena tuoreimmista tutkimuksista. Aluksi esitellään algoritmisten kaupankäyntijärjestelmien rakenne ja tapa toimia, jonka jälkeen aiemmat tutkimukset käydään läpi. Tulokset osoittavat, että algoritminen kaupankäynti on parantanut markkinatehokkuutta hinnanmuodostuksen ja likviditeetin osalta. Merkittäviä negatiivisia vaikutuksia ei huomattu.

Disconnect.Me. User Engagement and Facebook

In the beginning of its 10th year of existence Facebook has engaged and connected 1.2 billion monthly active users. This article-based dissertation Disconnect.Me – User Engagement and Facebook approaches this engagement from the opposite direction: disconnection. The research articles focus on social media specific phenomena including leaving Facebook, tactical media works such as Web 2.0 SuicideMachine, memorializing dead Facebook users and Facebook trolling. The media theoretical framework for this study is built around affect theory, software studies, biopolitics as well as different critical studies of new media. The argument is that disconnection is a necessary condition of social media connectivity and exploring social media through disconnection – as an empirical phenomenon, future potential and theoretical notion – helps us to understand how users are engaged with social media, its uses and subsequent business models. The results of the study indicate that engagement is a relation that precedes user participation, a notion often used to conceptualize social media. Furthermore, this engagement turns the focus from users’ actions towards the platform and how the platform actively controls users and their behavior. Facebook aims to engage new users and maintain the old ones by renewing its platform and user interface. User engagement with the platform is thus social but also technical and affective. When engaged, the user is positioned to algorithmic connectivity where machinc processes mine user data. This data is but sold also used to affect and engage other users. In the heart of this study is the notion that our networked engagements matter and disconnection can bring us to the current limits of network culture.

Design and validation of stateful composite RESTful web services

A web service is a software system that provides a machine-processable interface to the other machines over the network using different Internet protocols. They are being increasingly used in the industry in order to automate different tasks and offer services to a wider audience. The REST architectural style aims at producing scalable and extensible web services using technologies that play well with the existing tools and infrastructure of the web. It provides a uniform set of operation that can be used to invoke a CRUD interface (create, retrieve, update and delete) of a web service. The stateless behavior of the service interface requires that every request to a resource is independent of the previous ones facilitating scalability. Automated systems, e.g., hotel reservation systems, provide advanced scenarios for stateful services that require a certain sequence of requests that must be followed in order to fulfill the service goals. Designing and developing such services for advanced scenarios with REST constraints require rigorous approaches that are capable of creating web services that can be trusted for their behavior. Systems that can be trusted for their behavior can be termed as dependable systems. This thesis presents an integrated design, analysis and validation approach that facilitates the service developer to create dependable and stateful REST web services. The main contribution of this thesis is that we provide a novel model-driven methodology to design behavioral REST web service interfaces and their compositions. The behavioral interfaces provide information on what methods can be invoked on a service and the pre- and post-conditions of these methods. The methodology uses Unified Modeling Language (UML), as the modeling language, which has a wide user base and has mature tools that are continuously evolving. We have used UML class diagram and UML state machine diagram with additional design constraints to provide resource and behavioral models, respectively, for designing REST web service interfaces. These service design models serve as a specification document and the information presented in them have manifold applications. The service design models also contain information about the time and domain requirements of the service that can help in requirement traceability which is an important part of our approach. Requirement traceability helps in capturing faults in the design models and other elements of software development environment by tracing back and forth the unfulfilled requirements of the service. The information about service actors is also included in the design models which is required for authenticating the service requests by authorized actors since not all types of users have access to all the resources. In addition, following our design approach, the service developer can ensure that the designed web service interfaces will be REST compliant. The second contribution of this thesis is consistency analysis of the behavioral REST interfaces. To overcome the inconsistency problem and design errors in our service models, we have used semantic technologies. The REST interfaces are represented in web ontology language, OWL2, that can be part of the semantic web. These interfaces are used with OWL 2 reasoners to check unsatisfiable concepts which result in implementations that fail. This work is fully automated thanks to the implemented translation tool and the existing OWL 2 reasoners. The third contribution of this thesis is the verification and validation of REST web services. We have used model checking techniques with UPPAAL model checker for this purpose. The timed automata of UML based service design models are generated with our transformation tool that are verified for their basic characteristics like deadlock freedom, liveness, reachability and safety. The implementation of a web service is tested using a black-box testing approach. Test cases are generated from the UPPAAL timed automata and using the online testing tool, UPPAAL TRON, the service implementation is validated at runtime against its specifications. Requirement traceability is also addressed in our validation approach with which we can see what service goals are met and trace back the unfulfilled service goals to detect the faults in the design models. A final contribution of the thesis is an implementation of behavioral REST interfaces and service monitors from the service design models. The partial code generation tool creates code skeletons of REST web services with method pre and post-conditions. The preconditions of methods constrain the user to invoke the stateful REST service under the right conditions and the post condition constraint the service developer to implement the right functionality. The details of the methods can be manually inserted by the developer as required. We do not target complete automation because we focus only on the interface aspects of the web service. The applicability of the approach is demonstrated with a pedagogical example of a hotel room booking service and a relatively complex worked example of holiday booking service taken from the industrial context. The former example presents a simple explanation of the approach and the later worked example shows how stateful and timed web services offering complex scenarios and involving other web services can be constructed using our approach.

Pairs trading profitability in the Finnish stock market: A comparison between three methods

Pairs trading is an algorithmic trading strategy that is based on the historical co-movement of two separate assets and trades are executed on the basis of degree of relative mispricing. The purpose of this study is to explore one new and alternative copula-based method for pairs trading. The objective is to find out whether the copula method generates more trading opportunities and higher profits than the more traditional distance and cointegration methods applied extensively in previous empirical studies. Methods are compared by selecting top five pairs from stocks of the large and medium-sized companies in the Finnish stock market. The research period includes years 2006-2015. All the methods are proven to be profitable and the Finnish stock market suitable for pairs trading. However, copula method doesn’t generate more trading opportunities or higher profits than the other methods. It seems that the limitations of the more traditional methods are not too restrictive for this particular sample data.

Secular Possession: Cinematic Iconography of Addiction

Addiction, and the experience of being addicted, is notoriously difficult to describe verbally and explain rationally. Would multifaceted and multisensory cinematic images work better in making addiction understandable? This study enquires how cinematic expression can render visible the experience of being addicted which is invisible as such. The basic data consists of circa 50 mainly North American and European fiction films from the early 1900s to the early 2000s that deal with addictive disorders as defined in the psychiatric DSM-V classification (substance dependence- and gambling disorders). The study develops an approach for analyzing and interpreting a large volume of digital film data: digital cinematic iconography is a framework to study the multifaceted cinematic images by processing and viewing them in the “digital image-laboratory” of the computer. Images are cut and classified by editing software and algorithmic sorting. The approach draws on early 1900s German art historian Aby Waburg’s image research and media archaeology, that are connected to film studies inspired by the phenomenology of the body and Gilles Deleuze’s film-philosophy. The first main chapter, “Montage”, analyses montage, gestural and postural images, and colors in addiction films. The second main chapter, “Thingness”, focuses on the close-ups of material objects and faces, and their relation to the theme of spirituality in cinema and art history, The study argues that the cinema engages the spectator to "feel" what addiction is through everyday experience and art historical imagery. There is a particular, historically transmitted cinematic iconography of addiction that is profane, material, thing-centered, abject, and repetitive. The experience of being addicted is visualized through montages of images characterized by dark and earthy colors, horizontal compositions and downward- directed movements. This is very profane and secular imagery that, however, circulates image-historical traces of Christian iconography, such as that of being in the grip of an unknown power.

Optimizing last mile delivery using public transport with multiagent based control

The majority of research work carried out in the field of Operations-Research uses methods and algorithms to optimize the pick-up and delivery problem. Most studies aim to solve the vehicle routing problem, to accommodate optimum delivery orders, vehicles etc. This paper focuses on green logistics approach, where existing Public Transport infrastructure capability of a city is used for the delivery of small and medium sized packaged goods thus, helping improve the situation of urban congestion and greenhouse gas emissions reduction. It carried out a study to investigate the feasibility of the proposed multi-agent based simulation model, for efficiency of cost, time and energy consumption. Multimodal Dijkstra Shortest Path algorithm and Nested Monte Carlo Search have been employed for a two-phase algorithmic approach used for generation of time based cost matrix. The quality of the tour is dependent on the efficiency of the search algorithm implemented for plan generation and route planning. The results reveal a definite advantage of using Public Transportation over existing delivery approaches in terms of energy efficiency.