Dp 2011 krejci filip cz
Evoluční algoritmy pro rozvrhování projektů
- Autor: Ing. Filip Krejčí, mailto:krejci.filip@gmail.com
- Vedoucí práce: Doc. Dr. Ing. Zdeněk Hanzálek
- Oponent: Ing. Petr Pošík, Ph.D.
Anotace
Práce se zabývá řešením problému RCPS ǀ temp metodou Particle Swarm Optimization (PSO). Vytvořil jsem nový algoritmus GPSO, který kombinuje dobré vlastnosti PSO s genetickými operátory nevyváženého dvoubodového křížení a náhodné mutace. Srovnávám výkonnost tohoto nového algoritmu a různých variant PSO a GA na kritériích energetické efektivity a earliness-tardiness.
Koncept kritéria energetické efektivity je v oblasti rozvrhování projektů s temporálními omezeními zcela nový. Jeho optimalizací se dosahuje redukování počtu zapínání resp. vypínání zařízení a zkracování prodlev mezi úlohami, ve kterých musí být zařízení zapnuté a naopak vytváření dostatečně dlouhých prodlev, aby se zařízení mohlo přepnout do úsporného režimu.
V rozsáhlých testech překonává navržené GPSO ostatní testované varianty PSO i GA. Pro některé testovací množiny dosahuje zlepšení energetické efektivity až o 25 %. Kritérium earliness-tardiness vylepšuje až o 6,7 %, přičemž zároveň zkracuje i délku rozvrhu (Cmax) až o 3,7 %.
Klíčová slova: RCPS | temp, PSO, GA, GPSO, energetická efektivita, earliness-tardiness