|
|
Aproximace obtížných rozvrhovacích úloh
Lisý, Viliam ; Čepek, Ondřej (advisor) ; Vlach, Milan (referee)
This thesis deals with shop scheduling problems. After introducing the basic denitions and notation, we continue with a short survey of known complexity results for open shop, ow shop and job shop scheduling problems. Then we focus more on open shop and especially on a subclass of open shop with at most two non-zero length operations per job denoted Om|mj = 2|Cmax in standard notation. Besides some minor lemmas and observations, four major new results concerning this subclass are presented. The rst one is an observation, that any schedule in this class can be transformed in polynomial time to a schedule with same length and only one idle interval on each machine. The second one is a proof of a well known conjecture about so-called dense schedules for the subclass. The third one is modication of a known greedy algorithm to obtain schedules no longer then 3/2 of the optimal length, and the last one is a modication of a known polynomial approximation scheme which guarantees a better performance for instances from the above described subclass.
|
|
|
Project portfolio optimisation with time and resources
Huml, Tomáš ; Barták, Roman (advisor) ; Vlach, Milan (referee)
Title: Project portfolio optimization with time and resources Author: Bc. Tomáš Huml Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Roman Barták, Ph.D Abstract: Traditional project portfolio optimization deals with static projects that are not evolving in time. The focus of this diploma thesis is on projects that are spread in time, typically such projects consists of a sequence (or other partially ordered structure) of actions that require some resources (money, people, etc.) for realization. Then the project portfolio optimization deals with selecting a subset of projects according to given time and space (resource) restrictions and optimizing certain criteria such as overall profit. This problem is very close to oversubscribed scheduling where the most profitable subset of orders is being scheduled. Hence scheduling techniques will be the main inspiration for solving this new type of problems. Lots of modelling algorithms for optimal portfolio selection are proposed in this diploma thesis and several of them are implemented in a program which is part of this thesis as well. Keywords: portfolio optimization, integer linear programming (ILP), workflow optimization, project interdependencies
|
|
|
The selection drift against perfect rationality
Kuběna, Aleš ; Šmíd, Martin (advisor) ; Vlach, Milan (referee) ; Šizling, Arnošt Leoš (referee)
A direct application of game theory to conflicts and cooperation of organisms gives different theoretical predictions for their behaviour than economic models, even if the economic models are based on game theory themselves. These direct predictions are in better accordance with empirical data than the economic models. A difference is observed even if we analyse how organisms deal with sources and how they compete for sources, a problem of apparently economic nature. My thesis shows that these contradictions cannot be removed in a plausible way, even not via introducing new biological restrictions in the "economic" decision model applied to organisms, and not even via enriching the utility functions by evolutionary goals. Thus it is not satisfactory to assume rational agents who replaced a utility maximisation by the maximisation of offspring numbers. In my model, gathering of sources is used in a game-theoretical analysis as a necessary condition, but not as a sufficient condition of evolutionary sustainability. Analýza predicts that the fact whether a rational, collectively rational, altruistic, or different strategy wins in some population, is a matter of random fluctuation. In this model, agents will, with non-neglectable probability, behave in a way that contradicts perfect rationality. This...
|
|
|
Demand Management in Smart Grids
Nesveda, František ; Pilát, Martin (advisor) ; Vlach, Milan (referee)
With the rapid adoption of electric vehicles and the rise of power generation from re- newable sources, intelligent management of power demand on a household level is gaining importance. Current algorithms used for that purpose have negative privacy implications and focus only on controlling the charging of electric vehicles while ignoring other ap- pliances. We describe a decentralized algorithm designed to control the power demand of different types of household appliances along with the charging of electric vehicles while preserving the privacy of the subscribers. We also present a smart grid simulator to evaluate the algorithm's effectiveness along with results of simulating a scale model of the power grid of the state of Texas. 1
|
|
|
The selection drift against perfect rationality
Kuběna, Aleš ; Šmíd, Martin (advisor) ; Vlach, Milan (referee) ; Šizling, Arnošt Leoš (referee)
A direct application of game theory to conflicts and cooperation of organisms gives different theoretical predictions for their behaviour than economic models, even if the economic models are based on game theory themselves. These direct predictions are in better accordance with empirical data than the economic models. A difference is observed even if we analyse how organisms deal with sources and how they compete for sources, a problem of apparently economic nature. My thesis shows that these contradictions cannot be removed in a plausible way, even not via introducing new biological restrictions in the "economic" decision model applied to organisms, and not even via enriching the utility functions by evolutionary goals. Thus it is not satisfactory to assume rational agents who replaced a utility maximisation by the maximisation of offspring numbers. In my model, gathering of sources is used in a game-theoretical analysis as a necessary condition, but not as a sufficient condition of evolutionary sustainability. Analýza predicts that the fact whether a rational, collectively rational, altruistic, or different strategy wins in some population, is a matter of random fluctuation. In this model, agents will, with non-neglectable probability, behave in a way that contradicts perfect rationality. This...
|
|
|
Project portfolio optimisation with time and resources
Huml, Tomáš ; Barták, Roman (advisor) ; Vlach, Milan (referee)
Title: Project portfolio optimization with time and resources Author: Bc. Tomáš Huml Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Roman Barták, Ph.D Abstract: Traditional project portfolio optimization deals with static projects that are not evolving in time. The focus of this diploma thesis is on projects that are spread in time, typically such projects consists of a sequence (or other partially ordered structure) of actions that require some resources (money, people, etc.) for realization. Then the project portfolio optimization deals with selecting a subset of projects according to given time and space (resource) restrictions and optimizing certain criteria such as overall profit. This problem is very close to oversubscribed scheduling where the most profitable subset of orders is being scheduled. Hence scheduling techniques will be the main inspiration for solving this new type of problems. Lots of modelling algorithms for optimal portfolio selection are proposed in this diploma thesis and several of them are implemented in a program which is part of this thesis as well. Keywords: portfolio optimization, integer linear programming (ILP), workflow optimization, project interdependencies
|
|
|
Aproximace obtížných rozvrhovacích úloh
Lisý, Viliam ; Vlach, Milan (referee) ; Čepek, Ondřej (advisor)
This thesis deals with shop scheduling problems. After introducing the basic denitions and notation, we continue with a short survey of known complexity results for open shop, ow shop and job shop scheduling problems. Then we focus more on open shop and especially on a subclass of open shop with at most two non-zero length operations per job denoted Om|mj = 2|Cmax in standard notation. Besides some minor lemmas and observations, four major new results concerning this subclass are presented. The rst one is an observation, that any schedule in this class can be transformed in polynomial time to a schedule with same length and only one idle interval on each machine. The second one is a proof of a well known conjecture about so-called dense schedules for the subclass. The third one is modication of a known greedy algorithm to obtain schedules no longer then 3/2 of the optimal length, and the last one is a modication of a known polynomial approximation scheme which guarantees a better performance for instances from the above described subclass.
|
|
|
Algorithms for various geometric problems over zonotopes and their applications in optimization and data analysis
Rada, Miroslav ; Černý, Michal (advisor) ; Vlach, Milan (referee) ; Kopa, Miloš (referee)
The thesis unifies the most important author's results in the field of algorithms concerning zonotopes and their applications in optimization and statistics. The computational-geometric results consist of a new compact output-sensitive algorithm for enumerating vertices of a zonotope, which outperforms the rival algorithm with the same complexity-theoretic properties both theoretically and empirically, and a polynomial algorithm for arbitrarily precise approximation of a zonotope with the Löwner-John ellipsoid. In the application area, the thesis presents a result, which connects linear regression model with interval outputs with the zonotope matters. The usage of presented geometric algorithms for solving a nonconvex optimisation problem is also discussed.
|
|
| |
|
| |
guest ::
RSS feed.