Abstract This thesis deals with the pump schedule optimisation of regional water distribution systems. The aims and the possible applications of the presented methods differ from each other; all of them are intended to solve a particular but realistic problem. The developed techniques use the capacity of the water reservoirs in order to find the optimal pump-schedule of the system. The optimisation task is always deterministic and discrete in time; the stochastic behaviour of the water consumptions is approximated by expected values. A so-called neutral genetic algorithm equipped with new constraint handling is presented first. The method is able to solve the scheduling problems of real-size and complex networks, e.g. the network of Budapest with coupled hydraulic simulations where both variable and fixed speed pumps are in the network. The results are compared to other ones obtained by widely used genetic algorithms and state-of-the-art general purpose optimisation solvers. A dynamic programming based method was also carried out which provides the global optimum of the so-called ’combinatorial’ pump scheduling problems. This modelling type is very common in the industry, which can be used if the operation points of the pumps take discrete values. The basic idea of the method is exploiting the ’permutational invariance’ of the model which results in a perfect discretisation of the state space without any loss of information. An approximate dynamic programming technique is also presented which solves the same type of problems as the formerly mentioned genetic algorithm does. The technique splits the water network model into smaller units, namely into the so-called well fields and the main distribution system. The state space of the main distribution system was further decreased while the quality of the results does not decay. A part of the test examples is the same as in the case of the former presented genetic algorithm; thus, the two methods can be compared. Finally, a small water network fed by a single variable speed pump was investigated. The presented methods are based on the minimisation of the specific energy consumption. The gained results are compared to ones obtained using a high-resolution discrete dynamic program. Novel optimisation techniques for water distribution network pump scheduling were developed in this work. A particular focus was put on the dynamics between pumping, water reservoirs, and water use. The work shows the applicability of the approach via numerous realistic simulation case studies. / Tiivistelmä Työ käsittelee alueellisten vedenjakelujärjestelmien pumppauksen aikataulutuksen optimointia. Esitettyjen menetelmien tavoitteet ja mahdolliset sovellukset poikkeavat toisistaan. Kaikki on kuitenkin tarkoitettu tiettyjen todellisten ongelmien ratkaisemiseen. Kehitetyt tekniikat käyttävät vesivarastojen kapasiteettia optimaalisen pumppausohjelman löytämiseksi. Jokainen optimointitehtävä on aikadiskreetti ja deterministinen, vedenkulutuksen stokastista käyttäytymistä on approksimoitu odotusarvoilla. Ensimmäiseksi työssä esitetään ns. neutraaleja geneettisiä algoritmeja varustettuna rajoitusten käsittelyllä. Menetelmällä voidaan ratkaista skedulointiohjelmia reaalimittakaavaisille ja monimutkaisille verkostoille (esim. Budapestin verkosto varustettuna hydraulisilla simuloinneilla, sekä muuttuvanopeuksisilla että vakionopeuksisilla verkoston pumpuilla). Tuloksia verrataan toisiin yleisesti käytössä olevilla geneettisillä algoritmeilla saatuihin, sekä johtavilla yleiskäyttöisillä optimointitekniikoilla saatuihin tuloksiin. Työssä käytettiin myös dynaamiseen ohjelmointiin pohjaavaa menetelmää, jolla saadaan globaali optimi ns. "kombinatoorisille" pumppauksen aikataulutusongelmille. Tällainen mallinnustapa on hyvin yleistä teollisuudessa. Sitä voidaan käyttää, jos pumppujen toimintapisteet saavat diskreettejä arvoja. Menetelmän perusajatuksena on "permutationaalisen invarianssin" hyväksikäyttäminen, josta seuraa tila-avaruuden virheetön diskretointi ilman informaation häviämistä. Työssä esitellään myös approksimoidun dynaamisen ohjelmoinnin tekniikka, jonka avulla voidaan ratkaista samantyyppisiä ongelmia kuin yllämainituilla geneettisillä algoritmeilla. Tämä tekniikka jakaa vesijohtoverkoston mallin pienempiin yksiköihin: lähdekenttiin ja pääjakeluverkostoon. Pääjakeluverkoston tila-avaruutta voitiin edelleen pienentää ilman, että tulosten laatu heikkeni. Osa käsitellyistä esimerkkitapauksista on samoja kuin edellämainittujen geneettisten algoritmien osalla, joten tuloksia voidaan verrata. Lopuksi tutkittiin pienen muuttuvanopeuksisella pumpulla syötetyn vesijohtoverkoston toimintaa. Esitetyt menetelmät perustuvat ominaisenergiankulutuksen minimointiin. Saatuja tuloksia verrataan korkearesoluutioisella diskreetillä dynaamisella ohjelmoinnilla saatuihin tuloksiin. Työssä kehitettiin uusia optimointitekniikoita vedenjakelujärjestelmien pumppauksen aikataulutuksen optimintiin. Erityisesti työssä keskityttiin pumppauksen, vesitornien ja kuluttajien käyttäytymisen väliseen dynamiikkaan. Työssä osoitettiin tekniikoiden toimivuus realististen esimerkkisimulointien avulla. / Kivonat Jelen doktori disszertáció regionális ivóvízellátó-hálózatok üzemvitel-optimalizációjával foglalkozik. A bemutatott módszerek alkalmazhatósági köre rendszerint eltér egymástól, mindegyik egy-egy speciális, de a való életben is előforduló problémára kíván megoldást nyújtani. A kidolgozott módszerek a medencék tárolókapacitását kihasználva, az optimális szivattyú-menetrendet keresve kívánják megtalálni az adott vízműhálózat üzemviteloptimumát. Az optimalizáció egy időben diszkrét, ugyanakkor determinisztikus feladat megoldását igényli, a vízfogyasztások sztochasztikus viselkedését a várható értékekkel közelítettem. Elsőként egy új mellékfeltétel-kezeléssel ellátott, ún. neutrális genetikus algoritmus bemutatása a cél. A kidolgozott módszer alkalmas nagy, valós méretű (pl. Budapest) és bonyolultságú (kapcsolt hidraulikai szimulációk, frekvenciaváltós és direkt szivattyúk a hálózatban) ivóvízhálózatok napi üzemvitel optimalizálására. Az eredményeket más genetikus algoritmusokkal és a világ élvonalába tartozó, de általános célú optimalizációs módszerekkel hasonlítottam össze. Kidolgozásra került egy dinamikus programozás alapú, a valós, globális optimumot adó módszer is. Az algoritmus a gyakorlatban elterjedt, ún. "kombinációs" hálózatként modellezhető vízműhálózat típusokra alkalmazható, ahol a szivattyúk munkapontjai diszkrét értékek. A megoldás alapját az ún. "permutációs invariancia" jelensége adja, mely lehetővé teszi az állapottér információveszteség nélküli, tökéletes diszkretizációját. Egy, a korábban bemutatott genetikus algoritmuséhoz hasonló problémakört megoldó, de közelítő dinamikus programozás alapú módszer is bemutatásra kerül. Az algoritmus a hálózat kisebb részegységekre (víztermelő területekre és fő elosztó hálózatra) való felbontásával és a fő elosztó hálózat állapotterének önkényes, de a megoldás jóságán jelentősen nem rontó csökkentésével éri el a program futtatásához szükséges számítási igény csökkentését. A tesztfeladatok egy része megegyezik a genetikus algoritmus tesztfeladataival, így azok közvetlenül összehasonlíthatóak. Végül bemutatásra kerül egy kisméretű, mindössze egy darab változtatható fordulat- számú szivattyúval táplált rendszer energetikai vizsgálata. Az itt bemutatott módszerek mind a fajlagos energiafelhasználás minimalizálásán alapulnak. Az eredményeket egy nagyfelbontású dinamikus programozás alapú módszerhez hasonlítottam.

Abstract Fading in wireless channels, the limited battery energy available in wireless handsets, the changing user demands and the increasing demand for high data rate and low delay pose serious design challenges in the future generations of mobile communication systems. It is necessary to develop efficient transmission policies that adapt to changes in network conditions and achieve the target delay and rate with minimum power consumption. In this thesis, a number of new paradigms in wireless networks are presented. Dynamic programming tools are used to provide dynamic network stabilizing resource allocation solutions for virtualized data centers with clouds, cooperative networks and heterogeneous networks. Exact dynamic programming is used to develop optimal resource allocation and topology control policies for these networks with queues and time varying channels. In addition, approximate dynamic programming is also considered to provide new sub-optimal solutions. Unified system models and unified control problems are also provided for both secondary service provider and primary service provider cognitive networks and for conventional wireless networks. The results show that by adapting to the changes in queue lengths and channel states, the dynamic policy mitigates the effects of primary service provider and secondary service provider cognitive networks on each other. We investigate the network stability and provide new unified stability regions for primary service provider and secondary service provider cognitive networks as well as for conventional wireless networks. The K-step Lyapunov drift is used to analyse the performance and stability of the proposed dynamic control policies, and new unified stability analysis and queuing bound are provided for both primary service provider and secondary service provider cognitive networks and for conventional wireless networks. By adapting to the changes in network conditions, the dynamic control policies are shown to stabilize the network and to minimize the bound for the average queue length. In addition, we prove that the previously proposed frame based does not minimize the bound for the average delay, when there are shared resources between the terminals with queues. / Tiivistelmä Langattomien kanavien häipyminen, langattomien laitteiden akkujen rajallinen koko, käyttäjien käyttötarpeiden muutokset sekä lisääntyvän tiedonsiirron ja lyhyemmän viiveen vaatimukset luovat suuria haasteita tulevaisuuden langattomien verkkojen suunnitteluun. On välttämätöntä kehittää tehokkaita resurssien allokointialgoritmeja, jotka sopeutuvat verkkojen muutoksiin ja saavuttavat sekä tavoiteviiveen että tavoitedatanopeuden mahdollisimman pienellä tehon kulutuksella. Tässä väitöskirjassa esitetään uusia paradigmoja langattomille tietoliikenneverkoille. Dynaamisen ohjelmoinnin välineitä käytetään luomaan dynaamisia verkon stabiloivia resurssien allokointiratkaisuja virtuaalisille pilvipalveludatakeskuksille, käyttäjien yhteistyöverkoille ja heterogeenisille verkoille. Tarkkoja dynaamisen ohjelmoinnin välineitä käytetään kehittämään optimaalisia resurssien allokointi ja topologian kontrollointialgoritmeja näille jonojen ja häipyvien kanavien verkoille. Tämän lisäksi, estimoituja dynaamisen ohjelmoinnin välineitä käytetään luomaan uusia alioptimaalisia ratkaisuja. Yhtenäisiä systeemimalleja ja yhtenäisiä kontrollointiongelmia luodaan sekä toissijaisen ja ensisijaisen palvelun tuottajan kognitiivisille verkoille että tavallisille langattomille verkoille. Tulokset osoittavat että sopeutumalla jonojen pituuksien ja kanavien muutoksiin dynaaminen tekniikka vaimentaa ensisijaisen ja toissijaisen palvelun tuottajien kognitiivisten verkkojen vaikutusta toisiinsa. Tutkimme myös verkon stabiiliutta ja luomme uusia stabiilisuusalueita sekä ensisijaisen ja toissijaisen palveluntuottajan kognitiivisille verkoille että tavallisille langattomille verkoille. K:n askeleen Lyapunovin driftiä käytetään analysoimaan dynaamisen kontrollointitekniikan suorituskykyä ja stabiiliutta. Lisäksi uusi yhtenäinen stabiiliusanalyysi ja jonon yläraja luodaan ensisijaisen ja toissijaisen palveluntuottajan kognitiivisille verkoille ja tavallisille langattomille verkoille. Dynaamisen algoritmin näytetään stabiloivan verkko ja minimoivan keskimääräisen jonon pituuden yläraja sopeutumalla verkon olosuhteiden muutoksiin. Tämän lisäksi todistamme että aiemmin esitetty frame-algoritmi ei minimoi keskimääräisen viiveen ylärajaa, kun käyttäjät jakavat keskenään resursseja.