Master's Thesis

Job Scheduling in Logistic Warehouses

Final Thesis 3.24 MB

Author of thesis: Ing. Lukáš Povoda, Ph.D.

Acad. year: 2013/2014

Supervisor: Ing. Jan Karásek, Ph.D.

Reviewer: Ing. Václav Uher, Ph.D.

Abstract:

The main aim of this thesis is flow shop and job shop scheduling problem in logistics warehouses. Managing and scheduling works is currently often problem. There is no simple solution due to complexity of this problem. This problem must be resolved because of a lack efficiency of work with a higher load such as during the christmas holidays. This paper describes the methods used to solve this problem focusing mainly on the use of search algorithms, evolutionary algorithms, specifically grammar guided genetic programming. This paper describes the problem of job shop scheduling on a simple theoretical example. The implemented algorithm for solving this problem was subjected to tests inspired on data from real warehouse, as well as synthetically created tests with more jobs and a greater number of workers. Synthetic tests were generated randomly. All tests were therefore run several times and the results were averaged. In conclusion of this work are presented the results of the algorithm and the optimum parameter settings for different sizes of problems and requirements for the solution. Genetic algorithm has been extended to calculate fitness of individuals with regard to number of collisions, extended to use priority rules during run of evolution, and some parts of algorithm was parallelized.

Keywords:

Job shop, flow shop, logistics, genetic algorithm, evolutionary algorithm, grammar guided genetic programming, heuristics

Date of defence

12.06.2014

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

Lze nějakým způsobem omezit paměťovou náročnost evolučního algoritmu u velkých populací? Otázka na aplikovanie výsledkov v praxi. Požadavky na technický systém potrebný k realizovaniu danej aplikácie.

Language of thesis

Slovak

Faculty

Department

Study programme

Electrical, Electronic, Communication and Control Technology (EEKR-M)

Field of study

Communications and Informatics (M-TIT)

Composition of Committee

prof. Ing. Jiří Mišurec, CSc. (předseda)
doc. Ing. Miloš Orgoň, Ph.D. (místopředseda)
Ing. Tomáš Zeman, Ph.D. (člen)
Ing. Vladimír Červenka, Ph.D. (člen)
Ing. Milan Šimek, Ph.D. (člen)
Ing. Jan Karásek, Ph.D. (člen)

Supervisor’s report
Ing. Jan Karásek, Ph.D.

Student vypracoval diplomovou práci na téma „Rozvrhování úkolů v logistických skladech“, v rámci které zpracoval rešerši týkající se rozvrhovacích problémů se zaměřením na meta-heuristické algoritmy a jejich využití při optimalizačních úlohách logistických skladů. V praktické části práce student vytvořil testovací scénáře z historického provozu skladu a vytvořil také generátor syntetických testů pro ověření výkonosti algoritmu. Vhodné části kódu jsou zpracovány paralelně. Hlavním jádrem práce je návrh vlastních pravidel, která kombinují výhody logicky strukturovaných pravidel a existujícího přístupu založeného na bezkontextovou gramatikou řízeném genetickém programování. Testování algoritmu a měření výsledků bylo zdárně ukončeno a lze říci, že studentem navržený přístup předčí dosavadní výsledky optimalizace prováděné pouze na základě evolučního principu.

Student po dobu zpracování práce postupoval svědomitě, aktivně, přinášel vlastní nápady na řešení, pravidelně se účastnil konzultací a dbal pokynů vedoucího. Přírůstky práce byly prezentovány na pravidelných schůzkách. Odevzdaná práce je na vynikající úrovni jak po teoretické, tak po praktické stránce. Student se podílel na několika publikacích v oblasti optimalizace logistických skladů, zúčastnil se konference EEICT a dále bude pokračovat v tématu na doktorském studiu. Práci hodnotím stupněm „výborně/A“ a zkušební komisi navrhuji udělit za vypracování cenu děkanky FEKT. Points proposed by supervisor: 100

Grade proposed by supervisor: A

Reviewer’s report
Ing. Václav Uher, Ph.D.

Student v teoretické části popsal jednotlivé algoritmy pro optimalizaci úloh. K tomu hojně využíval literaturu. V praktické části vytvořil sadu testů pro evaluaci výkonosti evolučních algoritmů a implementoval prioritní pravidla. Tím splnil body zadání. Výsledky jednotlivých testů jsou podrobně popsány a správně interpretovány. Po formální stránce je práce v pořádky, jenom obsahuje drobné typografické chyby – například spojka „a“ na konci řádku. Práci doporučuji k obhajobě a hodnotím známkou A – 98 bodů. Topics for thesis defence:
  1. Lze nějakým způsobem omezit paměťovou náročnost evolučního algoritmu u velkých populací?
Points proposed by reviewer: 98

Grade proposed by reviewer: A

Responsibility: Mgr. et Mgr. Hana Odstrčilová