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.

Tietoverkon varmistusten simulointi ja optimointi

Tässä diplomityössä määritellään varmistusjärjestelmän simulointimalli eli varmistusmalli. Varmistusjärjestelmän toiminta optimoidaan kyseisen varmistusmallin avulla. Optimoinnin tavoitteena on parantaa varmistusjärjestelmän tehokkuutta. Parannusta etsitään olemassa olevien varmistusjärjestelmän resurssien maksimaalisella hyödyntämisellä. Varmistusmalli optimoidaan evoluutioalgoritmin avulla. Optimoinnissa on useita tavoitteita, jotka ovat ristiriidassa keskenään. Monitavoiteoptimointiongelma muunnetaan yhden tavoitteen optimointiongelmaksi muodostamalla tavoitefunktio painotetun summan menetelmän avulla. Rinnakkain edellisen menetelmän kanssa käytetään myös Pareto-optimointia. Pareto-optimaalisen rintaman pisteiden etsintä ohjataan lähelle painotetun summan menetelmän optimipistettä. Evoluutioalgoritmin toteutuksessa käytetään hyväksi varmistusjärjestelmiin liittyvää ongelmakohtaista tietoa. Työn tuloksena saadaan varmistusjärjestelmän simulointi- sekä optimointityökalu. Simulointityökalua käytetään kartoittamaan nykyisen varmistusjärjestelmän toimivuutta. Optimoinnin avulla tehostetaan varmistusjärjestelmän toimintaa. Työkalua voidaan käyttää myös uusien varmistusjärjestelmien suunnittelussa sekä nykyisten varmistusjärjestelmien laajentamisessa.

Qualitative Characteristics and Quantitative Measures of Solution's Reliability in Discrete Optimization: Traditional Analytical Approaches, Innovative Computational Methods and Applicability

The purpose of this thesis is twofold. The first and major part is devoted to sensitivity analysis of various discrete optimization problems while the second part addresses methods applied for calculating measures of solution stability and solving multicriteria discrete optimization problems. Despite numerous approaches to stability analysis of discrete optimization problems two major directions can be single out: quantitative and qualitative. Qualitative sensitivity analysis is conducted for multicriteria discrete optimization problems with minisum, minimax and minimin partial criteria. The main results obtained here are necessary and sufficient conditions for different stability types of optimal solutions (or a set of optimal solutions) of the considered problems. Within the framework of quantitative direction various measures of solution stability are investigated. A formula for a quantitative characteristic called stability radius is obtained for the generalized equilibrium situation invariant to changes of game parameters in the case of the H¨older metric. Quality of the problem solution can also be described in terms of robustness analysis. In this work the concepts of accuracy and robustness tolerances are presented for a strategic game with a finite number of players where initial coefficients (costs) of linear payoff functions are subject to perturbations. Investigation of stability radius also aims to devise methods for its calculation. A new metaheuristic approach is derived for calculation of stability radius of an optimal solution to the shortest path problem. The main advantage of the developed method is that it can be potentially applicable for calculating stability radii of NP-hard problems. The last chapter of the thesis focuses on deriving innovative methods based on interactive optimization approach for solving multicriteria combinatorial optimization problems. The key idea of the proposed approach is to utilize a parameterized achievement scalarizing function for solution calculation and to direct interactive procedure by changing weighting coefficients of this function. In order to illustrate the introduced ideas a decision making process is simulated for three objective median location problem. The concepts, models, and ideas collected and analyzed in this thesis create a good and relevant grounds for developing more complicated and integrated models of postoptimal analysis and solving the most computationally challenging problems related to it.

Structural and operational optimisation : applications in energy systems

In this work mathematical programming models for structural and operational optimisation of energy systems are developed and applied to a selection of energy technology problems. The studied cases are taken from industrial processes and from large regional energy distribution systems. The models are based on Mixed Integer Linear Programming (MILP), Mixed Integer Non-Linear Programming (MINLP) and on a hybrid approach of a combination of Non-Linear Programming (NLP) and Genetic Algorithms (GA). The optimisation of the structure and operation of energy systems in urban regions is treated in the work. Firstly, distributed energy systems (DES) with different energy conversion units and annual variations of consumer heating and electricity demands are considered. Secondly, district cooling systems (DCS) with cooling demands for a large number of consumers are studied, with respect to a long term planning perspective regarding to given predictions of the consumer cooling demand development in a region. The work comprises also the development of applications for heat recovery systems (HRS), where paper machine dryer section HRS is taken as an illustrative example. The heat sources in these systems are moist air streams. Models are developed for different types of equipment price functions. The approach is based on partitioning of the overall temperature range of the system into a number of temperature intervals in order to take into account the strong nonlinearities due to condensation in the heat recovery exchangers. The influence of parameter variations on the solutions of heat recovery systems is analysed firstly by varying cost factors and secondly by varying process parameters. Point-optimal solutions by a fixed parameter approach are compared to robust solutions with given parameter variation ranges. In the work enhanced utilisation of excess heat in heat recovery systems with impingement drying, electricity generation with low grade excess heat and the use of absorption heat transformers to elevate a stream temperature above the excess heat temperature are also studied.

Verkostoinvestointien optimointi uuden sähkömarkkinalain ympäristössä

Vuonna 2013 uudistunut sähkömarkkinalaki toi sähköverkkoyhtiöille velvoitteen parantaa sähkönjakeluverkkojensa toimintavarmuutta suurhäiriötilanteissa. Toimenpiteet tämän velvoitteen täyttämiseksi näkyvät merkittävinä verkostoinvestointeina. Diplomityössä tarkastellaan uudistuneen sähkömarkkinalain tuomia vaikutuksia Imatran Seudun Sähkön jakeluverkkoa koskeviin verkostoinvestointeihin. Päätavoitteena on selvittää, millaisia toimenpiteitä uuden sähköntoimitusvarmuustason vaatimusten täyttämiseksi tarvitaan ja mitkä ovat optimaaliset ratkaisut näiden toimenpiteiden toteuttamiseksi. Uudella sähköntoimitusvarmuustasolla on vaikutusta jakeluverkon rakennemuutoksiin tulevien 15 vuoden aikana, mutta näiden rakennemuutosten vaikutukset kantavat useiden kymmenien vuosien päähän.

Photocatalytic oxidation of humic substances and lignins in aqueous solutions

Tässä tutkimuksessa tarkastellaan kahden yleisen, veden ympäristökuormitusta aiheuttavan kemikaaliryhmän, ligniinin ja humusaineiden, fotokatalyyttistahapetusta (photocatalytic oxidation, PCO) vesiliuoksessa. Fotokatalyyttina käytettiin titaanidioksidia, jota säteilytettiin ultraviolettivalolla. Työssä selvitettiin useiden eri olosuhdeparametrien vaikutusta fotokatalyysiin. Tutkittavia parametreja olivat mm. kontaminanttien alkukonsentraatio, pH, vetyperoksidilisäys, rauta-ionien lisäys, fotokatalyysimenetelmä, fotokatalyytin pintakonsentraatioja titaanidioksidin määrä lasisissa mikropartikkeleissa. Ultraviolettivalon lähteinä käytettiin sekä keinovaloa että auringonvaloa. Katalyytin kantoaineena käytettiin huokoisia lasisia mikropartikkeleita, joiden pintaan kiinnittynyt titaanidioksidi pystyi hyvin vähentämään kontaminanttien määrää vedessä. Fotokatalyysin tehokkuus kasvoi humusaine- ja ligniinikonsentraatioiden kasvaessa. Korkeimmat hapetustehokkuudet kumallakin kontaminantilla saavutettiin neutraaleissa jalievästi emäksisissä olosuhteissa huolimatta siitä, että paras adsorboituminen tapahtui happamissa olosuhteissa. Tämän perusteella voidaan olettaa, että humusaineiden ja ligniinin hapetus tapahtuu pääosin radikaalimekanismilla. Vetyperoksidin lisääminen humusaineliuokseen lisäsi hapettumisnopeutta, vaikka näennäinen hapetustehokkuus ei muuttunut. Tämän perusteella vetyperoksidi hapetti myös humusaineita referenssinäytteessä. Ligniinin fotokatalyyttinen hapettuminen parani vetyperoksidilisäyksellä happamissa olosuhteissa johtuen lisääntyneestä OH-radikaalien muodostumisesta. Ligniini ei hapettunut vetyperoksidilla, jos fotokatalyyttiä ei¿ollut läsnä. Rauta-ionit eivät lisänneet humushappojen fotokatalyyttistähapettumista, mutta Fe2+-ionien lisäys aina konsentraatioon 0.05 mM johti ligniinin hapettumistehokkuuden voimakkaaseen kasvuun. Rauta-ionikonsentraation kasvattaminen edelleen johti ligniinin hapetustehokkuuden alenemiseen.

Developing customer-based e-solutions

Logistiikkapalveluiden markkinat ovat viime vuosina muuttuneet. Kilpailtu toimiala ja asiakasvaatimusten muuttuminen ovat pakottaneet yritykset pyrkimään entistä tehokkaampaan jakeluketjuun. Työn tarkoituksena oli tutkia sähköisten asiakasliittymien toimivuutta asiakkaan näkökulmasta Euro Express tuotannossa ja prosessissa. Tarkoituksena oli selvittää eri sidosryhmien vaatimukset prosessille huomioiden sähköisen liiketoiminnan tuomat edut ja ominaispiirteet. Tavoitteena oli kuvata olemassa oleva prosessi ja tutkia prosessin rajapinnat –asiakas, tuotanto ja ulkoiset sidosryhmät. Tutkielmassa sähköisten ratkaisujen ominaispiirteet on käyty läpi ja tulevaisuuden kehitysnäkökulmista keskusteltu. Kehittyneiden tietoteknisten ratkaisujen avulla jatkuva prosessien uudistaminen (Business Process Reengineering) on mahdollista. Yleisesti epäolennaisuudet asiakasrajapinnassa, informaation kulussa ja yhteyksissä eri järjestelmien välillä aiheuttavat ongelmia sähköisten ratkaisujen toteuttamisessa. Tulevaisuudessa logistiikka yritykset ottavat entistä enemmän käyttöönsä uudenaikaisia teknologisia ratkaisuja tilaukseen, tuotantoon ja asiakaspalveluun. Näiden uudenlaisten ratkaisujen kehittämisestä on hyötyä sekä käyttäjälle että tarjoajalle, mutta ne ovat myös pakollisia palveluntarjoajalle kehittyäkseen markkinoilla. Tulevaisuudessa kilpailun tiivistyessä ja asiakkaiden vaatimusten kasvaessa on kiinnitettävä entistä suurempaa huomiota koko prosessiketjun toimivuuteen. Uudet teknologiset ratkaisut ja niiden käyttäminen tehokkaasti tuovat yrityksille kilpailuetuja, joita ei muuten olisi saavutettavissa.

Communication Solutions for LVDC Island Networks

Production and generation of electrical power is evolving to more environmental friendly technologies and schemes. Pushed by the increasing cost of fossil fuels, the operational costs of producing electrical power with fossil fuels and the effect in the environment, like pollution and global warming, renewable energy sources gain con-stant impulse into the global energy economy. In consequence, the introduction of distributed energy sources has brought a new complexity to the electrical networks. In the new concept of smart grids and decen-tralized power generation; control, protection and measurement are also distributed and requiring, among other things, a new scheme of communication to operate with each other in balance and improve performance. In this research, an analysis of different communication technologies (power line communication, Ethernet over unshielded twisted pair (UTP), optic fiber, Wi-Fi, Wi-MAX, and Long Term Evolution) and their respective characteristics will be carried out. With the objective of pointing out strengths and weaknesses from different points of view (technical, economical, deployment, etc.) to establish a richer context on which a decision for communication approach can be done depending on the specific application scenario of a new smart grid deployment. As a result, a description of possible optimal deployment solutions for communication will be shown considering different options for technologies, and a mention of different important considerations to be taken into account will be made for some of the possible network implementation scenarios.

Suunnittelulla ja ruo´on hyötykäytöllä tehokkuutta rantojen hoitoon : Tuloksia ja kokemuksia VELHO-hankkeesta

Varsinais-Suomen ELY-keskuksen toteuttamassa VELHO-hankkeessa kehitettiin kustannustehokkaita ratkaisuja ranta-alueiden umpeenkasvun aiheuttamiin ongelmiin luomalla uusi konsepti ranta-alueiden monikäyttösuunnitteluun, edistämällä järviruo’on hyötykäyttöä ja valmistelemalla esityksiä uuteen maaseudun kehittämisohjelmaan. Tässä julkaisussa esitellään työn tulokset ja johtopäätökset. Hankkeessa laadittiin kolme ranta-alueiden monikäyttösuunnitelmaa: Mynälahden Sarsalanaukko ja Musta-aukko, Oukkulanlahti – Naantalinaukko ja Eurajoen - Luvian rannikko. Suunnitelmissa sovitettiin yhteen ranta-alueiden eri käyttömuotoja ja pyrittiin löytämään optimaalinen verkosto hyötykäyttöön leikattavien ruovikoiden, avoimena pidettävien merenrantaniittyjen ja säilytettävien ruovikoiden välille. Kustannustehokkuuteen pyrittiin kohdentamalla hoitotoimet laajoihin kokonaisuuksiin sekä järviruo’on hyötykäytöllä. Suunnitelmat laadittiin laajassa osallistavassa prosessissa. Hankkeessa laadituissa ranta-alueiden monikäyttösuunnitelmissa esitettiin erilaisia maankäyttötavoitteita ja hoitosuosituksia yli 2000 hehtaarille. Ruovikoiden ja rantaniittyjen lisäksi suunnittelun kohteena olivat myös rantojen läheiset peltoalueet, reunavyöhykkeet ja muut perinnebiotoopit. Hoitotoimilla tavoitellaan alueiden luonnon monimuotoisuuden ja vesien tilan paranemista, maiseman avartumista ja virkistyskäytön helpottumista. Ruovikoiden erilaisia leikkuumenetelmiä (talvileikkuut, vesileikkuut, maaleikkuut) testattiin 90 hehtaarin alalla. Rantaniittyjen kunnostuksessa testattiin maaleikkuun lisäksi ruovikon niittomurskausta. Ruokomassan hyötykäyttökokeissa testattiin kahden eri ruokolaadun eli tuoreen kesäruo’on ja kuivan talviruo’on esikäsittelyä ja hyötykäyttöä energiantuotannossa (poltto, biokaasutus) ja maataloudessa (maanparannusaine, viherlannoite, kuivike, katemateriaali). Maaseudun kehittämisohjelmaan tehtiin esityksiä tukimuotojen kehittämiseksi: rantaniittyjen kunnostuksen lisääminen ja hoidon laadun parantaminen, ruovikoiden vesileikkuut ravinteiden poistajina sekä ruokomassojen käyttö maan orgaanisen aineen lisääjänä. Hankkeen kokemusten mukaan yksi kustannustehokkaimmista hoito- ja käyttöketjuista on ruovikon leikkuu loppukesällä ja siitä kertyvän massan käyttö ranta-alueiden läheisillä pelloilla viherlannoitteena ja maanparannusaineena. Yhden hehtaarin ruovikon kesäleikkuulla poistetaan keskimäärin 80 kg typpeä ja 7 kg fosforia. Vesiensuojelullisten hyötyjen lisäksi leikkuulla parannetaan umpeenkasvusta kärsivien lajien elinoloja, lisätään rantojen vetovoimaisuutta ja edistetään luonnonhoitoyrittäjyyden edellytyksiä. Peltokäytössä käsittelyketju on lyhyt eikä se vaadi pitkiä kuljetusmatkoja. Ruokomassa kierrättää ravinteita takaisin pelloille ja parantaa maan rakennetta. Järviruo’on hyötykäytöllä ei pystytä kattamaan koko leikkuu- ja käyttöketjun kustannuksia. Leikkuusta ja hyötykäytöstä saatavien monien eri aineellisten ja aineettomien ekosysteemipalveluhyötyjen vuoksi toimintaan on tarpeen suunnata yhteiskunnan tukea ja luoda käytännön toteutusta edistäviä tukimuotoja. Kustannustehokkuutta voidaan edelleen parantaa laitteita ja menetelmiä kehittämällä.

Mathematical modeling and optimal control of malaria

Malaria continues to infect millions and kill hundreds of thousands of people worldwide each year, despite over a century of research and attempts to control and eliminate this infectious disease. Challenges such as the development and spread of drug resistant malaria parasites, insecticide resistance to mosquitoes, climate change, the presence of individuals with subpatent malaria infections which normally are asymptomatic and behavioral plasticity in the mosquito hinder the prospects of malaria control and elimination. In this thesis, mathematical models of malaria transmission and control that address the role of drug resistance, immunity, iron supplementation and anemia, immigration and visitation, and the presence of asymptomatic carriers in malaria transmission are developed. A within-host mathematical model of severe Plasmodium falciparum malaria is also developed. First, a deterministic mathematical model for transmission of antimalarial drug resistance parasites with superinfection is developed and analyzed. The possibility of increase in the risk of superinfection due to iron supplementation and fortification in malaria endemic areas is discussed. The model results calls upon stakeholders to weigh the pros and cons of iron supplementation to individuals living in malaria endemic regions. Second, a deterministic model of transmission of drug resistant malaria parasites, including the inflow of infective immigrants, is presented and analyzed. The optimal control theory is applied to this model to study the impact of various malaria and vector control strategies, such as screening of immigrants, treatment of drug-sensitive infections, treatment of drug-resistant infections, and the use of insecticide-treated bed nets and indoor spraying of mosquitoes. The results of the model emphasize the importance of using a combination of all four controls tools for effective malaria intervention. Next, a two-age-class mathematical model for malaria transmission with asymptomatic carriers is developed and analyzed. In development of this model, four possible control measures are analyzed: the use of long-lasting treated mosquito nets, indoor residual spraying, screening and treatment of symptomatic, and screening and treatment of asymptomatic individuals. The numerical results show that a disease-free equilibrium can be attained if all four control measures are used. A common pitfall for most epidemiological models is the absence of real data; model-based conclusions have to be drawn based on uncertain parameter values. In this thesis, an approach to study the robustness of optimal control solutions under such parameter uncertainty is presented. Numerical analysis of the optimal control problem in the presence of parameter uncertainty demonstrate the robustness of the optimal control approach that: when a comprehensive control strategy is used the main conclusions of the optimal control remain unchanged, even if inevitable variability remains in the control profiles. The results provide a promising framework for the design of cost-effective strategies for disease control with multiple interventions, even under considerable uncertainty of model parameters. Finally, a separate work modeling the within-host Plasmodium falciparum infection in humans is presented. The developed model allows re-infection of already-infected red blood cells. The model hypothesizes that in severe malaria due to parasite quest for survival and rapid multiplication, the Plasmodium falciparum can be absorbed in the already-infected red blood cells which accelerates the rupture rate and consequently cause anemia. Analysis of the model and parameter identifiability using Markov chain Monte Carlo methods is presented.