|
|
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.
|
|
|
Using reinforcement learning to learn how to play text-based games
Zelinka, Mikuláš ; Kadlec, Rudolf (advisor) ; Lisý, Viliam (referee)
The ability to learn optimal control policies in systems where action space is defined by sentences in natural language would allow many interesting real-world applications such as automatic optimisation of dialogue systems. Text-based games with multiple endings and rewards are a promising platform for this task, since their feedback allows us to employ reinforcement learning techniques to jointly learn text representations and control policies. We present a general text game playing agent, testing its generalisation and transfer learning performance and showing its ability to play multiple games at once. We also present pyfiction, an open-source library for universal access to different text games that could, together with our agent that implements its interface, serve as a baseline for future research.
|
|
|
Distributed Monte-Carlo Tree Search for Games with Team of Cooperative Agents
Filip, Ondřej ; Lisý, Viliam (advisor) ; Majerech, Vladan (referee)
The aim of this work is design, implementation and experimental evaluation of distributed algorithms for planning actions of a team of cooperative autonomous agents. Particular algorithms require different amount of communication. In the work, the related research on Monte-Carlo tree search algorithm, its parallelization and distributability and algorithms for distributed coordination of autonomous agents. Designed algorithms are tested in the environment of the game of Ms Pac-Man. Quality of the algorithms is tested in dependence on computational time, the amount of communication and the robustness against communication failures. Particular algorithms are compared according to these characteristics. Powered by TCPDF (www.tcpdf.org)
|
|
|
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.
|
guest ::
