|
|
Online Bin Stretching: Algorithms and Computer Lower Bounds
Böhm, Martin ; Sgall, Jiří (vedoucí práce) ; Durr, Christoph (oponent) ; Kellerer, Hans (oponent)
Online Bin Stretching: algoritmy a strojové dolní odhady Autor: Martin Böhm Abstrakt: Zabýváme se problémem v oblasti semi-online algoritmů, který se nazývá Online Bin Stretching. Můžeme tento problém chápat jako pro- blém opětovného pakování předmětů: cílem algoritmu je zapakovat před- měty různých velikostí do m kontejnerů identické kapacity R > 1. Objekty na vstupu přicházejí jeden po druhém a algoritmus musí přiřadit předmět do kontejneru dříve, než se objeví předmět další. Zvláštnost tohoto konkrétního problému je existence zaručené vlastnosti vstupu, kterou algoritmus zná. Algoritmus totiž už od začátku vstupu má zaručeno, že existuje pakování celého vstupu do m kontejnerů kapacity 1. Naším cílem je navrhnout algoritmy, které pakují jeden objekt po dru- hém a kterým se podaří vstup zapakovat do co nejmenší možné kapacity R. V této dizertační práci představíme několik nových výsledků kolem On- line Bin Stretchingu. Zaprvé, navrhneme algoritmus, který napakuje všechny objekty do m kontejnerů s kapacitou 1,5, a to pro libovolnou počáteční hodnotu m. Zadruhé se soustředíme na podproblém, ve kterém je počet kontejnerů nízký a pevný, například 3. Pro tento model představíme algo- ritmus, který zapakuje vstup do 3 binů s kapacitou 1,375. Nakonec navrhneme a naimplementujeme počítačový program, který bude...
|
|
|
Online scheduling of multiprocessor jobs with preemption
Šimsa, Štěpán ; Sgall, Jiří (vedoucí práce) ; Kolman, Petr (oponent)
Abstrakt. Práce se věnuje problému preemptivního online rozvrhování paralelních úloh. Podává přehled předchozích výsledků pro tento problém. Pro některé speciální varianty problému, například pro úlohy na jeden a dva procesory, poskytuje nové výsledky, jak v podobě dolních odhadů, tak v podobě kompetitivních algoritmů. Je objevena chyba v dříve publikovaném dolním odhadu a opravena na správný dolní odhad. Je navržen algoritmus pro verzi problému se čtyřmi procesory a s úlohami na jeden a dva procesory, pro který je vyslovena hypotéza, že dosahuje nejlepšího možného kompetitivního poměru.
|
|
|
Úlohy rozvrhování s pevnými časy prací - stochastická rozšíření, formulace a algoritmy
Leder, Ondřej ; Branda, Martin (vedoucí práce) ; Kopa, Miloš (oponent)
Úlohy rozvrhování s pevnými intervaly prací mají široké praktické uplatnění v plánování výroby, dopravě, při plánováni operací v nemocnicích, nebo ve školách při rozvrhování výuky. Bohužel je jejich častou součásti požadavek celočíselnosti proměnných a porušení této celočíselnosti není zanedbatelné jako v~některých případech ze světa financí. Předložíme proto několik možných formulací rozvrhovacích problému a jejich stochastická rozšíření. Navrhneme novou formulaci stochastického rozšíření rozvrhovací úlohy s pevnými intervaly prací založenou na teorii proudění v sítích a ukážeme, že celočíselné řešení je důsledkem jejího tvaru. Srovnáme ji s jinou ekvivalentní formulací. Pojednáme o Gâteauxově derivaci a jejím užití při zkoumání stability řešení stochastické optimalizační úlohy pod vlivem kontaminace. Zformulujeme větu o stabilitě řešení stochastických rozvrhovacích úloh s pevnými konci prací a uplatníme ji na příkladu.
|
|
|
Úlohy rozvrhování s pevnými časy prací - stochastická rozšíření, formulace a algoritmy
Leder, Ondřej ; Branda, Martin (vedoucí práce) ; Kopa, Miloš (oponent)
Úlohy rozvrhování s pevnými intervaly prací mají široké praktické uplatnění v plánování výroby, dopravě, při plánováni operací v nemocnicích, nebo ve školách při rozvrhování výuky. Bohužel je jejich častou součásti požadavek celočíselnosti proměnných a porušení této celočíselnosti není zanedbatelné jako v některých případech ze světa financí. Předložíme proto několik možných formulací rozvrhovacích problému a jejich stochastická rozšíření. Navrhneme novou formulaci stochastického rozšíření rozvrhovací úlohy s pevnými intervaly prací založenou na teorii proudění v sítích a ukážeme, že celočíselné řešení je důsledkem jejího tvaru. Srovnáme ji s jinou ekvivalentní formulací. Pojednáme o Gâteauxově derivaci a jejím užití při zkoumání stability řešení stochastické optimalizační úlohy pod vlivem kontaminace. Zformulujeme větu o stabilitě řešení stochastických rozvrhovacích úloh s pevnými konci prací a uplatníme ji na příkladu.
|
|
|
Analýza rozvrhů
Novák, Ladislav ; Barták, Roman (vedoucí práce) ; Duša, Vladimír (oponent)
Cílem této diplomové práce bylo věnovat se formální analýze rozvrhů, tj. identifikaci slabých míst a následné navržení metod, jak tato slabá místa opravit. Tato diplomová práce navíc řeší metodu, jak z navržených oprav vybrat vhodnou podmnožinu, tj. portfolio. Výsledný softwarový prototyp Analyzer je integrován do projektu FlowOpt, jež představuje komplexní řešení od modelování pracovních procesů, přes vytváření rozvrhů až po zobrazování rozvrhů pomocí Ganttova diagramu. Analyzer byl vyvíjen především jako doprovodné dílo, které softwarově ilustruje formální proces analýzy. Powered by TCPDF (www.tcpdf.org)
|
|
|
Combination of Evolutionary Algorithms and Constraint Programming for Scheduling
Štola, Miroslav ; Pilát, Martin (vedoucí práce) ; Klíma, Martin (oponent)
Je známé, že rozvrhovací problémy a problémy splňování podmínek jsou velice těžké. Tato práce nabízí nový přístup, jak pomocí evolučních algoritmů řešit rozvrhování s omezujícími podmínkami. Evoluce probíhá na pořadí proměnných, které solver postupně ohodnocuje. Tento přístup umožňuje jedince zakódovat jako permutace, a tedy je použitelný na širší škálu problémů s omezujícími podmínkami. Na základě analýzy grafu závislostí byly navrženy metody pro inicializaci počáteční populace jedinců. Rovněž byly vymyšleny a úspěšně použity nové genetické operátory. Naše metoda nalezla mnoho rozličných rozvrhů s optimální délkou. Dále byla úspěšně vy- zkoušena vícekriteriální optimalizace za pomoci algoritmu NSGA-II. 1
|
|
|
Planning operations of space probes
Kolombo, Martin ; Barták, Roman (vedoucí práce) ; Toropila, Daniel (oponent)
Práce popisuje řešení komplikovaného rozvrhovacího problému z problematiky vesmírných misí. V práci je popsán problem rozvrhování operací na družici Mars Express Orbiter, který byl původně prezentován jako zadání soutěže vypsané Evropskou vesmírnou agenturou. Práce popisuje a srovnává dva různé přístupy řešení popsaného problému. Prvním řešením je speciálně pro daný problém vyvinutý rozvrhovač, který pracuje na principu přiřazování akcí do časových oken a využívá techniky lokálního prohledávání. Druhé řešení modeluje problém pomocí programování s omezujícími podmínkami (CP) a pro výpočet řešení používá SICStus Prolog. Oba přístupy jsou v závěru práce experimentálně ověřeny. U obou přístupů se podařilo vytvořit funkční řešení. Závěrem práce je, že obecnější přístup pomocí CP je i bez složité heuristiky schopný vytvořit velmi kvalitní rozvrhy, ale selhává pro malou podmnožinu vstupů. Specificky vyvinutý rozvrhovač je schopný díky lokálnímu prohledávání řešit větší velikost vstupu, ale produkované rozvrhy jsou méně kvalitní.
|
|
|
Integrating Planning and Scheduling
Dvořák, Filip ; Barták, Roman (vedoucí práce) ; Smith, David E. (oponent) ; Hanzálek, Zdeněk (oponent)
Hlavním tématem práce je navržení a vývoj plánovacího systému FAPE, který integruje explicitní reprezentaci času, rozhodování s diskrétními zdroji a rezervoáry, a hierarchické dekompozice. FAPE je první plánovací systém, který akceptuje jazyk ANML a podporuje většinu jeho hlavních vlastností. V~práci se zabýváme různými aspekty integrace zmíněných konceptů, také navrhneme novou techniku pro reformulaci plánovacích problémů do reprezentace pomocí stavových proměnných a identifikujeme přechod výkonosti mezi používaním řídkých a minimálních časových sítí. FAPE dále rozšíříme o schopnosti konání a experimentálně vyhodnotíme výkonnost a výhody jeho vysoké expresivity. Na závěr předvedeme FAPE jako systém, který umí plánovat i konat v experimentech v realném světě, kdy FAPE ovládá robota PR2. Powered by TCPDF (www.tcpdf.org)
|
|
|
Integrating Planning and Scheduling
Dvořák, Filip
Název práce: Integrace plánování a rozvrhování Autor: Mgr. Filip Dvořák Katedra: Katedra teoretické informatiky a matematické logiky Vedoucí disertační práce: prof. RNDr. Roman Barták, Ph.D., KTIML MFF UK Abstrakt: Hlavním tématem práce je navržení a vývoj plánovacího systému FAPE, který integruje explicitní reprezentaci času, rozhodování s diskrétními zdroji a rezervoáry, a hierarchické dekompozice. FAPE je první plánovací systém, který akceptuje jazyk ANML a podporuje většinu jeho hlavních vlastností. V práci se zabýváme různými aspekty integrace zmíněných konceptů, také navrhneme novou techniku pro reformulaci plánovacích problémů do reprezentace pomocí stavových proměnných a identifikujeme přechod výkonosti mezi používaním řídkých a minimálních časových sítí. FAPE dále rozšíříme o schopnosti konání a exper- imentálně vyhodnotíme výkonnost a výhody jeho vysoké expresivity. Na závěr předvedeme FAPE jako systém, který umí plánovat i konat v experimentech v realném světě, kdy FAPE ovládá robota PR2. Klíčová slova: plánování, rozvrhování, temporální podmínky, HTN, robotika
|
|
|
Dynamic Scheduling
Vlk, Marek ; Barták, Roman (vedoucí práce) ; Duša, Vladimír (oponent)
Jedním z problémů rozvrhování výroby v reálném životě je dynamičnost výrobních prostředí zahrnující nové výrobní požadavky a rozbíjející se zařízení během vykonávání rozvrhu. Prosté přerozvržení od nuly v reakci na neočekávané události, které nastávají v provozu, může vyžadovat nadměrný výpočetní čas. Obnovený rozvrh může být navíc neúnosně odchýlený od toho probíhajícího. Tato práce podává přehled o stávajících přístupech v oblasti dynamického rozvrhování a navrhuje postupy jak upravit rozvrh při vyrušení, jako je například selhání zdroje, příchod naléhavé objednávky nebo její zrušení. Důraz je kladen na rychlost navržených procedur i na minimální modifikaci původního rozvrhu. Rozvrhovací model vychází z projektu FlowOpt, který je založen na temporálních sítích s alternativami. Algoritmy jsou napsány v jazyce C#.
|
host ::
RSS.