Tato diplomová práce je zaměřena na výzkum evolučních algoritmů (EA) v oblasti plánování zakázkové výroby a na vývoj nové strategie za účelem zlepšení výkonu. Sekvenční rovrhovací problem (JSSP) je jedním z nejsložitějších plánovacích problémů a nalezení optimálního řešení je vzhledem ke složitosti velmi obtížné. Byly přezkoumány existující evoluční algoritmy a pro řešení sekvenčního rozvrhovacího problému byl vybrán jeden z široce používaných genetických algoritmů. Pro porovnání efektivnosti EA jsou vygenerovány nejprve Aktivní plány pro pro eta lonové problémy JSSP na základě různých prioritních pravidel . Poté je přezkoumána struktura a hlavní parametry jednoduchého genetického algoritmu (SGA) a na základě toho je v SGA navržena a implementována nová strategie nahrazení (opakovaně použitelná substituční strategie - RSS). Implementace RRS v SGA zlepšuje výsledky a také byl experimentován její dopad na dva různé typy reprezentací chromozomů. Navržený MSGAJO je považován mezi testovanými za nejlepší genetický algoritmus, který dává nejlepší hodnoty promísení pro případy problému JSSP.
Anotace v angličtině
This thesis is aimed at research of evolution algorithms (EA) in the field of the shop scheduling problems and to develop a new strategy in order to improve the performance. Job shop scheduling problem (JSSP) is one of the most complex scheduling problem and finding the optimal solution is very difficult due to their complexity. Existing evolution algorithms were reviewed and one of the best and widely used genetic algorithm is selected for solving job shop scheduling problem. Active schedules for JSSP were generated based on various dispatching rules with the help of most used problem instances to compare effectiveness of EA. Then the structure and the major parameters of simple genetic algorithm (SGA) is reviewed and based on that a new strategy for replacement (Reusable Replacement Strategy) is proposed and implemented in the SGA. The implementation of RRS in SGA improves the results and also its impact on two different type of chromosome representations were experimented. The developed MSGAJO is concluded to be the best genetic algorithm among tested to give the best makespan values for the JSSP problem instances.
Tato diplomová práce je zaměřena na výzkum evolučních algoritmů (EA) v oblasti plánování zakázkové výroby a na vývoj nové strategie za účelem zlepšení výkonu. Sekvenční rovrhovací problem (JSSP) je jedním z nejsložitějších plánovacích problémů a nalezení optimálního řešení je vzhledem ke složitosti velmi obtížné. Byly přezkoumány existující evoluční algoritmy a pro řešení sekvenčního rozvrhovacího problému byl vybrán jeden z široce používaných genetických algoritmů. Pro porovnání efektivnosti EA jsou vygenerovány nejprve Aktivní plány pro pro eta lonové problémy JSSP na základě různých prioritních pravidel . Poté je přezkoumána struktura a hlavní parametry jednoduchého genetického algoritmu (SGA) a na základě toho je v SGA navržena a implementována nová strategie nahrazení (opakovaně použitelná substituční strategie - RSS). Implementace RRS v SGA zlepšuje výsledky a také byl experimentován její dopad na dva různé typy reprezentací chromozomů. Navržený MSGAJO je považován mezi testovanými za nejlepší genetický algoritmus, který dává nejlepší hodnoty promísení pro případy problému JSSP.
Anotace v angličtině
This thesis is aimed at research of evolution algorithms (EA) in the field of the shop scheduling problems and to develop a new strategy in order to improve the performance. Job shop scheduling problem (JSSP) is one of the most complex scheduling problem and finding the optimal solution is very difficult due to their complexity. Existing evolution algorithms were reviewed and one of the best and widely used genetic algorithm is selected for solving job shop scheduling problem. Active schedules for JSSP were generated based on various dispatching rules with the help of most used problem instances to compare effectiveness of EA. Then the structure and the major parameters of simple genetic algorithm (SGA) is reviewed and based on that a new strategy for replacement (Reusable Replacement Strategy) is proposed and implemented in the SGA. The implementation of RRS in SGA improves the results and also its impact on two different type of chromosome representations were experimented. The developed MSGAJO is concluded to be the best genetic algorithm among tested to give the best makespan values for the JSSP problem instances.
The aim of diploma thesis is to develop evolution algorithm to solve scheduling problems in mechanical engineering manufacturing. Thesis will include :
1/ Literature review of scheduling models ending with selecting one type.
2/ Literature review to map current approaches to solve selected model by evolutionary computing with goal to define nowadays approaches.
3/ Developing own evolution algorithm.
4/ Design testing of developed algorithm with comparison to Simple Genetic Algorithm and Dispatching rules.
5/ Evaluating efficiency of developed algorithm.
Zásady pro vypracování
The aim of diploma thesis is to develop evolution algorithm to solve scheduling problems in mechanical engineering manufacturing. Thesis will include :
1/ Literature review of scheduling models ending with selecting one type.
2/ Literature review to map current approaches to solve selected model by evolutionary computing with goal to define nowadays approaches.
3/ Developing own evolution algorithm.
4/ Design testing of developed algorithm with comparison to Simple Genetic Algorithm and Dispatching rules.
5/ Evaluating efficiency of developed algorithm.
Seznam doporučené literatury
[1] MICHALEWICZ, Z. Genetic algorithms+ data structures= evolution programs. Springer Science and Business Media, 2013.
[2] BACK, T. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. New York: Oxford University Press, 1996. ISBN 0-19-509971-0.
[3] EIBEN, A. E. a J. E. SMITH. Introduction to evolutionary computing. Second edition. Heidelberg: Springer, 2015. Natural computing series. ISBN 978-3-662-44873-1.
[4] DASH, S. S. a S. DAS, B. K. PANIGRAHI a K. VIJAYAKUMAR. Artificial Intelligence and Evolutionary Computations in Engineering Systems. Springer, 2017. Advances in Intelligent Systems and Computing, 517. ISBN 978-981-10-3173-1.
[5] SIMON, D. Evolutionary optimization algorithms: biologically-inspired and population-based approaches to computer intelligence. Hoboken: Wiley, 2013. ISBN 978-0-470-93741-9
Seznam doporučené literatury
[1] MICHALEWICZ, Z. Genetic algorithms+ data structures= evolution programs. Springer Science and Business Media, 2013.
[2] BACK, T. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. New York: Oxford University Press, 1996. ISBN 0-19-509971-0.
[3] EIBEN, A. E. a J. E. SMITH. Introduction to evolutionary computing. Second edition. Heidelberg: Springer, 2015. Natural computing series. ISBN 978-3-662-44873-1.
[4] DASH, S. S. a S. DAS, B. K. PANIGRAHI a K. VIJAYAKUMAR. Artificial Intelligence and Evolutionary Computations in Engineering Systems. Springer, 2017. Advances in Intelligent Systems and Computing, 517. ISBN 978-981-10-3173-1.
[5] SIMON, D. Evolutionary optimization algorithms: biologically-inspired and population-based approaches to computer intelligence. Hoboken: Wiley, 2013. ISBN 978-0-470-93741-9
Přílohy volně vložené
pdf
Přílohy vázané v práci
ilustrace, grafy, schémata, tabulky
Převzato z knihovny
Ano
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Průběh obhajoby je zveřejněn pouze přihlášenému uživateli.