This thesis is focused on the K-Competing Queues problem, which seeks for an optimal way to share a common resource among multiple user classes. The basic version of this problem, where users have...Show moreThis thesis is focused on the K-Competing Queues problem, which seeks for an optimal way to share a common resource among multiple user classes. The basic version of this problem, where users have unlimited patience, can be solved to optimality by using variations of the well-known cµ rule. The more relevant version of the problem, where user patience is limited, does not yet have an optimal solution. However, some authors have been able to identify special instances, where it is optimal to prioritise one user class over the others. By employing a simple coupling technique, we give an extension to the set of instances, where a full priority policy is optimal. Along with our search for optimality, we also attempt to give an approximate solution by a number of heuristics. As we will see from the numeric simulations, the best of all known heuristics turns out to be the one that solves the fluid approximation of the problem to optimalityShow less
Voting is incorporated into our daily lives in more ways that we usually realise. From electing national leaders and parliaments to selecting a group leader of a collaboration project and from...Show moreVoting is incorporated into our daily lives in more ways that we usually realise. From electing national leaders and parliaments to selecting a group leader of a collaboration project and from electing the winner of an Olympic sport event to choosing the best date for a group meeting, we use voting as a solution of many problems, some of which are daily, some of which only turn up every few years. But are the common methods used for voting these days the best and most honest methods? A lot of people probably have heard of the problem with one of the most important elections in the world, the election of the American president. The best-known problem occurred during the 2000 election, where Al Gore got a majority of the votes, but due to the American voting system, George W. Bush jr. won the election. This is just one of the problems the traditional voting systems have. This poses the question: What is honest voting, and what is an honest voting system? In this thesis we will look at the traditional voting systems and their (dis)advantages. Next, we will look at the voting system created by Michel Balinski and Rida Laraki, called the Majority Judgment. Once again, we will look into the system itself, look at its (dis)advantages and compare it to the traditional systems. We will conclude with a small research that was conducted regarding the Dutch political voting system. For writing this thesis, the book “Majority Judgment - Measuring, Ranking and Electing”[1] has been employed. A large part of this thesis consists of transforming this ‘semi-mathematical’ subject into more welldefined and precise mathematical definitions and theorems. If one does not have a background in mathematics, or just wants to have a brief overview of the various voting systems and their uses, an article about this subject can be found in the scientific magazine ’Eureka!’. The specific edition and further information can be found in the bibliography[4].Show less
Hanabi is a co-operative card game for two to five players, in which every player can see the contents of the other players’ hands, but not of their own. By the exchange of hints, a player can...Show moreHanabi is a co-operative card game for two to five players, in which every player can see the contents of the other players’ hands, but not of their own. By the exchange of hints, a player can obtain information about the cards in his or her hand. The thesis consists of two main parts. In the first part, we study the notion of playability. Not every initial configuration of the game can result in a maximum score even if playing perfectly. By employing combinatorics, we derive a formula with which the amount of the initial configurations which can be finished perfectly can be calculated for a simplification of the original game. We also propose an approach using dynamic programming to perform these calculations for slightly more complicated versions of the game. In the second part, we test a variety of strategies in search of good strategies for the original game. We discover that some simple rules give promising results, but that not all strategies which seem good intuitively indeed result in high scores.Show less
Fritzen is een dobbelspel dat vaak als drankspel wordt gespeeld. Er moeten dobbelstenen opzij worden gelegd om een gunstig aantal ogen te behalen. Het totaal aantal ogen dat is afgelegd, bepaalt de...Show moreFritzen is een dobbelspel dat vaak als drankspel wordt gespeeld. Er moeten dobbelstenen opzij worden gelegd om een gunstig aantal ogen te behalen. Het totaal aantal ogen dat is afgelegd, bepaalt de hoogte van de boete die uitgedeeld of verkregen wordt. In dit redelijk eenvoudige spel zijn veel verschillende dobbelsteencombinaties mogelijk. Voor elk van deze combinaties zijn er weer veel verschillende dobbelsteencombinaties die opzijgelegd kunnen worden. Hierdoor is het vaak niet meteen duidelijk welke van deze keuzes het beste resultaat geeft. In deze scriptie zal eerst voor een vereenvoudigde versie van het Fritzen een optimale speelwijze worden bepaald. Dit wordt gedaan aan de hand van een stochastisch dynamisch programmeringsprobleem dat specifiek voor dit spel wordt gedefinieerd. Daarna breiden we dit uit naar het volledige spel, waarvoor ook een optimale speelwijze wordt bepaald. Door een niet eenduidig vastgelegd doel is er niet ´e´en beste speelwijze. Deze speelwijze hangt af van het doel dat wordt gekozen. Onderdeel van deze scriptie is een programma waarmee, per doel, de optimale speelwijze bepaald kan worden.Show less
Within the world of operational research, project scheduling plays a large and important part. Being able to plan a project in such a way that is deemed optimal, by minimizing a given objective, is...Show moreWithin the world of operational research, project scheduling plays a large and important part. Being able to plan a project in such a way that is deemed optimal, by minimizing a given objective, is a challenging mathematical problem. Depending on the constraints placed on the project, there might not even exist any straightforward algorithm to obtain an optimum. For time constrained problems, polynomial time algorithms exists to calculate the most cost effective solution for any provided set of jobs. However, if jobs are additionally required to compete for resources, such a general solution does not exist. However, this thesis studies a method in which the Lagrangian relaxation of a resource constrained project can be efficiently solved by transforming it into an equivalent time constrained problem. This time constrained problem is subsequently solved by computing the minimum cut in a derived directed graphShow less
In this paper we introduce a new kind of game, called a deck building game, of which Dominion is the most prominent example. We focus on the question to what extent traditional game analysis...Show moreIn this paper we introduce a new kind of game, called a deck building game, of which Dominion is the most prominent example. We focus on the question to what extent traditional game analysis techniques can be used to analyze deck building games? To do this, we look at several simple strategies, like Random and Greedy, and some traditional techniques, namely Monte Carlo Tree Search and Dynamic Programming. We compare the strategies for mid (31 turns) to long games (100 turns). We conclude that our implementation of DP seems to be suitable only for games of medium length or shorter because of its space complexity, whereas our implementation of MCTS seems to fall behind other strategies with similar performance in regards of time complexity.Show less
Menigeen heeft wel eens gehoord van het `lights out'-probleem. Over dit probleem is een hoop op internet te vinden, met name met verscheidene roosters, zogenaamde `grids'. Het idee hiervan is dat...Show moreMenigeen heeft wel eens gehoord van het `lights out'-probleem. Over dit probleem is een hoop op internet te vinden, met name met verscheidene roosters, zogenaamde `grids'. Het idee hiervan is dat je een heel rooster, bestaande uit lampjes die ofwel aan ofwel uit staan, vanuit een semi-willekeurige configuratie volledig uit kunt krijgen door goed gekozen lampjes van toestand te laten veranderen, waarbij de volgende eigenschap geldt: Als lampje X van toestand verandert, oftewel van uit naar aan gaat, of van aan naar uit, dan zullen alle aangrenzende lampjes van X tevens van toestand veranderen.Show less
Iedereen heeft zichzelf wel eens in een situatie bevonden waarin ´e´en of meerdere goederen verdeeld moesten worden over een aantal mensen. Bij zo’n verdeling wil iedereen het liefst het grootste...Show moreIedereen heeft zichzelf wel eens in een situatie bevonden waarin ´e´en of meerdere goederen verdeeld moesten worden over een aantal mensen. Bij zo’n verdeling wil iedereen het liefst het grootste deel hebben. Laten we het voor het gemak over een cake hebben, dan is het doel dus om de cake zo te verdelen dat iedereen een stuk krijgt waar hij tevreden mee is. In dit onderzoek wordt naar dergelijke problemen gekeken: Wanneer is een gegeven verdeling eerlijk? Eerst zal beschreven worden wanneer een verdeling eerlijk genoemd mag worden. Hierna wordt naar het eenvoudige probleem gekeken van een verdeling over twee personen en daarna naar het complexe probleem van een verdeling over meer dan twee personen. Voor beide problemen zal een procedure uitgebreid besproken worden; een procedure die een verdeling oplevert waarmee iedereen tevreden is. Om een goed beeld te krijgen van de beschreven procedures, zullen voldoende (toelichtende) voorbeelden gegeven worden. In werkelijkheid komt het vaak voor dat mensen liegen om op die manier een groter deel van (bijvoorbeeld) de cake te krijgen, ook hiernaar zal dus gekeken worden. Het doel van dit onderzoek is om een beeld te krijgen van hoe verdelingen van ´e´en of meer goederen bereikt kunnen worden op een zo eerlijke mogelijke manier. Tijdens dit onderzoek is gebruik gemaakt van de hoofdstukken 5 en 11 uit het boek ‘Mathematics and Politics - Stratery, Voting, Power and Proof’ van Alan D. Taylor en Allison M. Pacelli.[1] De stellingen, algoritmes en bewijzen uit deze hoofdstukken zijn wiskundig onvolledig, daarom zullen we in dit onderzoek proberen deze te verbeteren en correct te makenShow less
In this thesis, we will compare two different methods for computing the stationary probabilities of Quasi-Birth-Death processes. The first method is Lattice Path Counting, as described in [1] and ...Show moreIn this thesis, we will compare two different methods for computing the stationary probabilities of Quasi-Birth-Death processes. The first method is Lattice Path Counting, as described in [1] and [2], the second Successive Lumping, which is explained in detail in [3]. We begin by explaining what a Quasi-Birth-Death process is and why it’s so hard to calculate its steady state probabilities. After that, a short description follows of both methods. We will briefly explain how they work and in which cases they can be used. These descriptions are meant as a short introduction to the workings of these methods. A more in depth explanation and more formal proofs can be found in the respective articles in which the methods are introduced. After that, both methods will be applied to a number of examples to show that the Successive Lumping method is applicable in more situations than Lattice Path Counting. Readers are expected to have a basic understanding of both discrete- and continuous-time Markov chains.Show less
The structure of the power grid has been unchanged since the introduction of AC power. With the introduction of clean energy we see that the purpose of the grid changes. Instead of only having...Show moreThe structure of the power grid has been unchanged since the introduction of AC power. With the introduction of clean energy we see that the purpose of the grid changes. Instead of only having large power plants, we now have many small generators scattered over the grid. The power network was not designed for this amount of distributed generation and our ever increasing demand for energy. Therefore we can expect that this trend will lead to an increase of interruptions due to a new kind of failures. In this thesis we will investigate the use of temperature and current measurements to prevent these failures from happening unexpectedly and how we can reduce the return on investment time of cables. In this thesis we will investigate the distribution system operator and the challenges found in the distribution grid of Westland Infra. We will simulate a small part of the distribution grid. We will evaluate important parameters for the challenges in the grid of Westland Infra and we will develop a proactive maintenance policy to reduce the return on investment time of adding cables in the grid.Show less
In deze bachelorscriptie worden verschillende indices besproken die de competitiviteit, de mate van onvoorspelbaarheid, van een sporttoernooi kwantificeren. Hierbij wordt gebruik gemaakt van een...Show moreIn deze bachelorscriptie worden verschillende indices besproken die de competitiviteit, de mate van onvoorspelbaarheid, van een sporttoernooi kwantificeren. Hierbij wordt gebruik gemaakt van een vooraf bepaalde ranking van de deelnemers en de uitslagen van het gespeelde toernooi, waarbij gelijkspel buiten beschouwing wordt gelaten. De indices die behandeld zullen worden zijn de (optimale) toernooi-index, Slater’s i, Kendall’s τ , het competitief evenwicht en de gewogen toernooi-index. Daarnaast zullen relaties tussen de (optimale) toernooi-index, Slater’s i en Kendall’s τ gegeven worden, waarna een mooi resultaat besproken wordt. Tot slot wordt aan de hand van de dynamische ranking, gebaseerd op de win-verlies score, besproken hoe de vooraf vastgestelde ranking bepaald kan worden.Show less
Modern society greatly relies on a secure energy supply for communication, security, health care and many more applications. Just rarely do we experience blackouts that make us aware of our...Show moreModern society greatly relies on a secure energy supply for communication, security, health care and many more applications. Just rarely do we experience blackouts that make us aware of our dependence on the various components of the power network. However, the power network was not designed to supply the ever-increasing demand that it faces today and without changes this will lead to more blackouts in the future. This thesis focusses on reducing the damage caused by cascading failures – failures that induce new failures and ultimately lead to a blackout. Concretely, we zoom in on a part of the power network – the high voltage power grid – and study intentional islanding, a mechanism that reduces the damage done by cascading failures. Intentional islanding separates the network in two or more components in order to isolate a cascading failure. This should protect the rest of the network from serious damage, although islanding by itself may also cause a wide disturbance. In this thesis, intentional islands are designed by formulating a MILP optimization problem that takes into consideration various trade-offs in islands design such as stability and load shed. To test the islanding mechanism introduced in this thesis, we want to create instances with cascading failures. For this, it is essential to know which transmission lines are most important to the power grid’s robustness. The relative importance of individual transmission lines to the power grid is calculated and used to simulate cascading failures. Both damage done by the cascading failures and general grid safety are analyzed with and without the implementation of islanding. Our results show that intentional islanding can be a very effective mechanism to protect the grid if implemented correctly.Show less