PA167 Rozvrhování Hana Rudová FI MU 23. května 2023 Hodnocení A 90 a více, B 80-89, C 70-79, D 60-69, E 55-59 Závěrečná písemná práce: 75 bodů minimální počet bodů za zkoušku: 40 bodů otázky pokrývají jednotlivé oblasti předmětu cca 7 příkladů: zadán problém, případně i metoda, cílem výpočet rozvrhu; srovnávací, algoritmus, pojmy vzorové zadání písemné práce na webu předmětu Vnitrosemestrální písemná práce: 18.4.2023, 20 bodů minimální počet bodů za vnitrosemestrální práci: 8 bodů Dva odpovědníky: v polovině a koncem semestru až 2.5 bodů za odpovědník, otevřeno od pátku do neděle libovolný počet průchodů, hodnocen nejlepší průchod Bonusové body: až 1 bod za aktivní účast na přednáčce odpovědi/zápojení do diskuse/otázky studentů Hana Rudová: PA167 Rozvrhování 2 23. května 2023 Základní informace Web předmětu: interaktivní osnova na IS MU prezentace + videa + dotazy k probírané látce průběžně zveřejňováný na webu předmětu Sbírka cca 240 vzorových příkladů včetně řešení vybraných příkladů poklad pro přípravu na zkoušku Rozvrhování a plánování v jiných přednáškách: IV126 Umělá inteligence II PA163 Omezující podmínky IA158 Real Time Systems Hana Rudová: PA167 Rozvrhování 3 23. května 2023 Literatura Michael Pinedo: Planning and Scheduling in Manufacturing and Services, Springer, 2009. Philippe Baptiste, Claude Le Pape, Wim Nuijten: Constraint-based scheduling : applying constraint programming to scheduling problems. Kluwer Academic Publishers, 2001. Michael Pinedo: Scheduling Theory, Algorithms, and Systems Springer, 2016. Hana Rudová: PA167 Rozvrhování 4 23. května 2023 Elektronické zdroje Michael Pinedo, Planning and Scheduling in Manufacturing and Services a další knihy https://wp.nyu.edu/michaelpinedo/books/ Sigurdur Olafsson, Iowa State University, USA http://www.stern.nyu.edu/om/faculty/pinedo/book2/dowload.html Erwin Hans, Johann Hurink, University of Twente, Nizozemí http://www.stern.nyu.edu/om/faculty/pinedo/book2/dowload.html Roman Barták, MFF UK, CR http://kti.ms.mff.cuni.cz/~bartak/planovani/ Hana Rudová: PA167 Rozvrhování 5 23. května 2023 Předběžný přehled přednášky (I. část) Úvod terminologie příklady reálných problémů Grahamova klasifikace rozvrhovacích problémů Obecné řešící metody heuristiky řídící pravidla (dispatching rules) lokální prohledávání: simulované žíhání, tabu prohledávání, genetické algoritmy matematické programování: formulace myšlenky řešení lineární, celočíselné programování s omezujícími podmínkami úvod k omezujícím podmínkám rozvrhování s omezujícími podmínkami Hana Rudová: PA167 Rozvrhování 6 23. května 2023 Předběžný přehled přednášky (II. část) Plánování projektu: reprezentace projektu, kritická cesta, kompromis mezi časem a cenou, pracovní síla Plánování úloh: řídící pravidla, metoda větví a mezí & paprskové prohledávání, matematické prohledávání Rozvrhování montážních systémů: montážní linka s flexibilním časem, s fixním časem Rezervace: intervalové rozvrhování, rezervační systémy s rezervou Timetabling: rozvrhování s operátory, rozvrhování s pracovní silou Univerzitní rozvrhování: teorie a praxe (rozvrhování na Masarykově univerzitě) Hana Rudová: PA167 Rozvrhování 7 23. května 2023 Úvod do rozvrhování PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 1 Rozvrh 2 Reálné problémy 3 Terminologie 4 Klasifikace rozvrhovacích problémů 5 Složitost Definice pojmu rozvrhování Rozvrhování optimální alokace/přiřazení zdrojů množině úloh v čase omezené množství zdrojů maximalizace zisku za daných omezení Stroj Mi , i = 1, . . . , m úloha Tj , j = 1, . . . , n Strojově orientovaný Ganttův diagram time 1 1 3 5 4 M T T3 6 9 M T T T T M T T T2 2 8 7 0 1 2 3 4 5 6 7 8 PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 9 23. května 2023 Rozvrh Rozvrh: dán umístěním úloh do konkrétního času a na konkrétní zdroje, kde mají být úlohy prováděny Úplný rozvrh: v rozvrhu jsou umístěny všechny úlohy ze zadání problému Částečný rozvrh: některé úlohy ze zadání problému nejsou umístěny/přiřazeny Konzistentní rozvrh: rozvrh, ve kterém jsou splněna všechna omezení kladená na zdroje a umístěné/přiřazené úlohy, např. úloha je naplánována v čase, kdy je dostupná na jednom stroji (s jednotkovou kapacitou) běží nejvýše jedna úloha Konzistentní úplný rozvrh vs. konzistentní částečný rozvrh Optimální rozvrh: umístění úloh na stroje je optimální vzhledem k zadanému optimalizačnímu kritériu, např. min Cmax : makespan (čas dokončení poslední úlohy) je minimální PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 10 23. května 2023 Příklad: montáž kola 10 úloh s danou dobou trvání Precedenční podmínky úlohu lze provést až po provedení zadané množiny úloh Nepreemtivní úlohy úlohy nelze přerušit Optimalizační kritéria minimalizace makespan minimální počet pracovníků T4 T6 8 T10 T9T5 T1 T3 T7 7 7 822 8 18 3 2 T2 7 T T93T T1 2 T4 6 T10 T5 T T8T T7 Schedule 2TT1 T106TT5T4 Optimal schedule 7 32 7T 24161452 T8 T93T PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 11 23. května 2023 Reálný problém: rozvrhování sester v nemocnici Jedná se o problém rozvrhování zaměstnanců Požadavky na personál odlišný počet sester v pracovní dny a o víkendu menší nároky při obsazování nočních směn dodržení pravidel daných ze zákona preference zaměstnanců na pracovní dobu . . . Cíl určit přiřazení sester na směny splnění požadavků minimalizace ceny PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 12 23. května 2023 Plánování nákladní automobilové dopravy Problém směrování vozidel (vehicle routing problem) požadavky na doručení/vyzvednutí/doručení+vyzvednutí lokace, časová okna, hmotnost, objem vozidla, která musí tyto lokace obsloužit kapacita/objem vozidel, jedno/více depot vozidel stejná/různá vozidla optimalizace: počtu vozidel, vzdálenosti, ceny Statický vs. dynamický problém problém dán předem vs. reakce na změny problému při realizaci řešení Spolupráce FI s firmou Wereldo 1 3 2 4 5 6 7 8 9 1 3 2 4 5 6 7 8 9 PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 13 23. května 2023 Univerzitní rozvrhování předmětů http://www.unitime.org Nalezení času a místnosti pro výuku předmětů na univerzitě omezení kladena na umístění předmětů optimalizace preferenčních požadavků na čas a místnosti každý předmět má určeny své studenty (registrace, studijní obory) minimalizace počtu překrývajících se předmětů pro všechny studenty Návrh, vývoj a používání systému UniTime FI spolupracuje na návrhu a vývoji od 2001 primárně vyvinuto a používáno na Purdue University, USA MU: používáno na 7 fakultách včetně FI International Timetabling Competition ITC 2019 reálné problémy z 10 různých univerzit po celém světě (UniTime data) PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 14 23. května 2023 Terminologie: scheduling vs. timetabling Scheduling ... rozvrhování/plánování alokace zdrojů za daných podmínek na objekty umístěných v časoprostoru tak, že je minimalizována celková cena daných zdrojů důraz je kladen na uspořádání objektů precedenční podmínky př. plánování výroby: stanovení pořadí operací, důležitost časových návazností operací schedule ... rozvrh zahrnuje prostorové a časové informace Timetabling ... rozvrhování alokace zdrojů za daných podmínek na objekty umístěných v časoprostoru tak, že jsou co nejlépe splněna zadaná kritéria důraz kladen na konkrétní časové umístění objektů často vymezen předem časový horizont (počet rozvrhovaných slotů) př. školní rozvrhování: předmětům přiřazen čas a místo vyuky timetable ... rozvrh ukazuje, kdy a kde se budou události konat PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 15 23. května 2023 Terminologie: planning Plánování (planning) někdy chápáno v dlouhodobějším horizontu krátkodobé podrobné rozvrhování + dlouhodobé obecné plánování např. plánování=vytvoření vhodné množiny úloh tak aby bylo dosaženo zadaných cílů rozvrhování=přiřazení úloh v čase na zdroje tak aby byla minimalizována cena nebo dlouhodobé plánování zdrojů tak abychom pokryli budoucí potřeby vs. krátkodobé rozvrhování úloh na zdroje tak aby byly splněny aktuální požadavky PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 16 23. května 2023 Terminologie: AI planning Plánování v umělé inteligenci (AI planning) vykonání posloupnosti akcí tak, abychom se dostali z počátečního stavu do koncového stavu př. plánování činností robota počáteční stav v místnosti, cílový stav v místnosti, robot provede posloupnost akcí (např. přemístí předměty) tak, aby se dostal do cílového stavu lze chápat jako vytvoření vhodné množiny úloh jako u plánování (viz předchozí průsvitka) Přednášká IV126 Umělá inteligence II zahrnut blok přednášek o plánování PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 17 23. května 2023 Terminologie: sequencing, rostering Sequencing ... seřazení za daných podmínek: konstrukce pořadí úloh, ve kterém budou prováděny sequence ... posloupnost pořadí, ve kterém jsou úlohy prováděny př. pořadí automobilů na montážní linku Rostering umístění zdrojů za daných podmínek do slotů s pomocí vzorů (pattern) roster ... rozpis seznam jmen lidí, který určuje, které úlohy budou provádět a kdy př. rozpis sester v nemocnici, rozpis řidičů autobusů PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 18 23. května 2023 Úlohy, stroje Stroje (zdroje, prostředky) i = 1, . . . , m Úlohy (aktivity) j = 1, . . . , n (i, j) operace nebo provádění úlohy j na stroji i úloha se může skládat z několika operací příklad: úloha 4 má tři operace s nenulovou dobou trvání (2,4),(3,4),(6,4), tj. je prováděna na strojích 2,3,6 Statické parametry úlohy doba trvání pij , pj : doba provádění úlohy j na stroji i termín dostupnosti j (release date) rj : nejdřívější čas, ve kterém může být úloha j prováděna termín dokončení (due date) dj : čas, do kdy by měla být úloha j nejpozději dokončena (preference) vs. deadline: čas, do kdy musí být úloha j nejpozději dokončena (požadavek) váha wj : důležitost úlohy j relativně vzhledem k ostatním úloham v systému Dynamické parametry úlohy čas startu úlohy (start time)Sij , Sj : čas zahájení provádění úlohy j na stroji i čas konce úlohy (completion time) Cij , Cj : čas, kdy je dokončeno provádění úlohy j na stroji i PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 19 23. května 2023 Grahamova klasifikace Grahamova klasifikace α|β|γ používá se pro popis rozvrhovacích problémů α: charakteristiky stroje popisuje způsob alokace úloh na stroje β: charakteristiky úloh popisuje omezení aplikovaná na úlohy γ: optimalizační kritéria http://www.informatik.uni-osnabrueck.de/knust/class/ složitost pro jednotlivé rozvrhovací problémy Příklady: P3|prec|Cmax: montáž kola Pm|rj | wj Cj : paralelní stroje PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 20 23. května 2023 Vlastnosti stroje α Jeden stroj 1: 1| . . . | . . . Identické paralelní stroje Pm m identických strojů zapojených paralelně (se stejnou rychlostí) úloha je dána jedinou operací úloha může být prováděna na libovolném z m strojů Paralelní stroje s různou rychlostí Qm doba trvání úlohy j na stroji i přímo závislá na jeho rychlosti vi pij = pj /vi př. několik počítačů s různou rychlostí procesoru Nezávislé paralelní stroje s různou rychlostí Rm stroje mají různou rychlost pro různé úlohy stroj i zpracovává úlohu j rychlostí vij pij = pj /vij př. vektorový počítač počítá vektorové úlohy rychleji než klasické PC PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 21 23. května 2023 Multi-operační (shop) problémy Multi-operační (shop) problémy jedna úloha je prováděna postupně na několika strojích úloha j se skládá z několika operací (i, j) operace (i, j) úlohy j je prováděna na stroji i po dobu pij příklad: úloha j se 4 operacemi (1, j), (2, j), (3, j), (4, j) 1.stroj 3.stroj 4.stroj 2.stroj Multi-operační problémy jsou klasické detailně studované problémy operačního výzkumu Reálné problémy ale často mnohem komplikovanější využití znalostí o podproblémech nebo zjednodušených problémech a jejich řešicích metodách PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 22 23. května 2023 Flow shop α Flow shop Fm multi-operační problém s m stroji v sérii každá úloha musí být prováděna na všech strojích úloha musí být prováděna na všech strojích ve stejném pořadí nejdříve se úloha provádí na 1. stroji, pak na 2., . . . Flexible flow shop FFs zobecnění flow shop problému s fází, každé fázi přísluší paralelní stroj příklad: paralelní stroj 1.fáze: 1+2+3, paralelní stroj 2.fáze: 4+5, ... tj. multi-operační problém s s paralelními stroji úloha musí projít všemi fázemi ve stejném pořadí nejprve se úloha provádí na paralelním stroji 1. fáze, pak na paralelním stroji 2. fáze, . . . na paralelním stroji příslušejícím dané fázi může být úloha prováděna na libovolném stroji 1.fáze 2.fáze 3.fáze 4.fáze 1 2 3 4 5 6 7 8 9 PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 23 23. května 2023 Open shop & job shop α Job shop Jm multi-operační problém s m stroji pořadí provádění operací pro každou úlohu je předem určeno doba zpracování úlohy na některých strojích může být nulová (i, j) → (k, j) určuje, že úloha j má být prováděna na stroji i dříve než na stroji k příklad: (2, j) → (1, j) → (3, j) → (4, j) Open shop Om multi-operační problém s m stroji doba zpracování úlohy na některých strojích může být nulová rozvrhovač určí, v jakém pořadí je úloha prováděna na strojích PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 24 23. května 2023 Omezení β Precedenční podmínky prec lineární posloupnost, stromová struktura pro úlohy a, b píšeme a → b, což znamená Sa + pa ≤ Sb příklad: montáž kola Přerušení úlohy (preemptions) pmtn při příchodu úlohy s vyšší prioritou je současná úloha přerušena Vhodnost stroje Mj podmnožina strojů Mj , na níž lze provádět úlohu j přiřazení místností: postačující velikost učebny hry: počítač s HW grafickou knihovnou Omezení na pracovní sílu W , Wl do problému zavedeme další typ zdroje stroje mohou potřebovat operátory a úlohy lze provádět jen tehdy, pokud jsou dostupní W operátorů mohou existovat různé skupiny operátorů se specifickou kvalifikací Wl je počet operátorů ve skupině l PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 25 23. května 2023 Omezení (pokračování) β Směrovací (routing) omezení udávají, na kterých strojích musí být úloha prováděna pořadí provádění úlohy v multi-operačních problémech job shop problém: pořadí operací předem stanoveno open shop problém: pořadí operací úlohy (route for the job) stanoveno až při rozvrhování Nastavovací (setup) doba a cena sijk, cijk, sjk, cjk závislé na posloupnosti provádění sijk čas nutný pro provádění úlohy k po úloze j na stroji i cijk cena nutná pro provádění úlohy k po úloze j na stroji i sjk , cjk čas/cena nezávislý na stroji příklady problém obchodního cestujícího 1|sjk |Cmax PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 26 23. května 2023 Omezení (pokračování) β Výroba na objednávku a na sklad výroba zboží na sklad, pokud je u něj záruka spotřeby nutno uvážit cenu za skladování výroba zboží na objednávku vynucuje úvahu termínů dokončení vyprodukované množství závislé na zákazníkovi Skladovací prostor a doba čekání při výrobě omezené množství prostoru při výrobě horní hranice počtu úloh čekajících ve frontě na stroj blokování: úloha je zablokována na současném stroji, protože fronta na následujícím stroji je plná ... PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 27 23. května 2023 Optimalizace: výkon a makespan γ Makespan Cmax: maximální čas konce úloh Cmax = max(C1, . . . , Cn) Příklad: Cmax = max{1, 3, 4, 5, 8, 7, 9} = 9 1 3 2 4 5 6 7Zdroj 1 Zdroj 2 cas Cíl: minimalizace makespan často maximalizuje výkon (throughput) zajišťuje rovnoměrné zatížení strojů (load balancing) příklad: Cmax = max{1, 2, 4, 5, 7, 4, 6} = 7 4 62 5 71 3Zdroj 1 Zdroj 2 cas Velmi často používané a základní kritérium PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 28 23. května 2023 Optimalizace: zpoždění γ Zpoždění (lateness) úlohy j: Lj = Cj − dj Maximální zpoždění Lmax Lmax = max(L1, . . . , Ln) Cíl: minimalizace maximálního zpoždění Příklad: d1 d3 d2 21 10 1550 3 2 Lmax = max(L1, L2, L3) = = max(C1 − d1, C2 − d2, C3 − d3) = = max(4 − 8, 16 − 14, 10 − 10) = = max(−4, 2, 0) = 2 PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 29 23. května 2023 Optimalizace: nezáporné zpoždění γ Nezáporné zpoždění (tardiness) úlohy j: Tj = max(Cj − dj , 0) Cíl: minimalizace celkového zpoždění n j=1 Tj celkové zpoždění Příklad: d1 d3 d2 21 10 1550 3 2 T1 +T2 +T3 = max(C1 −d1, 0)+max(C2 −d2, 0)+max(C3 −d3, 0) = max(4−8, 0)+max(16−14, 0)+max(10−10, 0) = 0+2+0 = 2 Cíl: minimalizace celkového váženého zpoždění n j=1 wjTj celkové vážené zpoždění PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 30 23. května 2023 Termín dokončení a grafy γ Cj dj Cj dj Cj dj j Tardiness Pozdě nebo ne V praxi T Cj dj j Lateness L Uj PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 31 23. května 2023 Optimalizace: skladování při výrobě γ Cena za skladování vyrobeného zboží Cena za skladování při výrobě (Work-In-Process inventory cost) příliš velké množství právě vyráběneho zboží může zaplnit linku příliš dlouho odložené zboží může být znehodnoceno Délka skladování při výrobě svázána s časy konce úloh ⇒ minimalizace součtu časů konců úloh n j=1 Cj ⇒ minimalizace váženého součtu časů konců úloh n j=1 wjCj celková hodnota daná skladováním při výrobě PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 32 23. května 2023 Další optimalizační kritéria γ Robustnost robustnější rozvrh vyžaduje méně změn při změně problému (porucha stroje, dopravní špička) Cena za nastavení (setup) cena za připravení letadla na odlet (čištění, zásobování, doplnění pohonných hmot) Cena za pracovní sílu cena za přiřazení zaměstnanců na konkrétní směnu V problému často řada optimalizačních kritérií multi-kriteriální rozvrhování Pareto optimalizace žádoucí vztah mezi nimi nemusí být jasně definovaný co je důležitější? ani samotná kritéria nemusí být jasně definována jak daný požadavek reprezentovat kritériem? PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 33 23. května 2023 Polynomiální a nedeterministicky polynomiální problémy Polynomiální problémy existuje algoritmus polynomiální složitosti pro řešení problému NP a NP-úplné problémy řešitelné nedeterministickým polynomiálním algoritmem potenciální řešení lze ověřit v polynomiálním čase v nejhorším případě exponenciální složitost (pokud neplatí P=NP) NP-úplný problém libovolný problém v NP se na něj dá polynomiálně redukovat Příklady: Polynomiální 1||Lmax P|pmtn|Cmax 1|| wj Cj NP 1|rj |Lmax P2||Cmax P2|| wj Cj PA167 Rozvrhování, H. Rudová: Úvod do rozvrhování 34 23. května 2023 Řídící pravidla PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 6 Řídící pravidla Řídící pravidla (dispatching rules) Řídící pravidlo určuje pořadí (prioritu), ve kterém mají být úlohy prováděny pokud má více úloh stejnou prioritu, úlohy jsou seřazeny náhodně (nebo např. dle čísla úlohy) jakmile se některý stroj uvolní, je vybrána nejprioritnější úloha Příklad: použijte pro seřazení úloh nejdřívější termín dostupnosti rj úlohy 1 2 3 4 5 6 rj 9 2 1 2 0 3 pj 1 2 1 1 2 2 PA167 Rozvrhování, H. Rudová: Řídící pravidla 36 23. května 2023 Pravidla s termíny dostupnosti rj a dokončení dj Nejdřívější termín dostupnosti (Earliest Release Date first ERD) ekvivalentní nejdříve-příjde-nejdříve-obsloužen (First-Come-First-Serve) minimalizuje odlišnosti v době čekání na stroji Nejdřívější termín dokončení (Earliest Due Date first EDD) směřuje k minimalizaci maximálního zpoždění mezi čekajícími úlohami optimální pro 1||Lmax (všechny úlohy dostupné na začátku) pozor, i zde (zejména stejně jako u všech pravidel) musíme brát v úvahu termín dostupnosti, tj. úlohu lze plánovat teprve když je dostupná!!! př. r2 = 3, d2 = 5, r3 = 0, d3 = 6 – dříve plánujeme úlohu 3 úlohy 1 2 3 4 5 6 rj 9 3 0 2 0 6 pj 1 2 1 1 2 2 dj 10 5 6 9 2 8 PA167 Rozvrhování, H. Rudová: Řídící pravidla 37 23. května 2023 Pravidla s termíny dostupnosti: minimální rezerva Minimální rezerva (Minimum Slack first MS) max(dj − pj − t, 0) dj termín dokončení pj doba provádění t aktuální čas funkci max používáme, abychom neměli záporné hodnoty pro úlohy, které už to určitě nestihnou minimalizace kriterií svázaných s termínem dokončení, tj. maximální zpoždění PA167 Rozvrhování, H. Rudová: Řídící pravidla 38 23. května 2023 Statická vs. dynamická pravidla Statická pravidla nejsou závislá na probíhajícím čase pořadí se spočítá jako funkce závislá na úloze a/nebo stroji pořadí nám definuje prioritní frontu úloh př. nejdřívější termín dostupnosti Dynamická pravidla jsou závislá na čase nutno zahrnout do výpočtu funkce i aktuální čas uspořádání úloh závisí na čase ⇒ v každém čase je nutné určit znovu úlohu s nejvyšší prioritou a tu zpracováváme př. minimální rezerva PA167 Rozvrhování, H. Rudová: Řídící pravidla 39 23. května 2023 Pravidla s dobou trvání pj Nejdelší doba trvání (Longest Processing Time first LPT) směřuje k rovnoměrnému zatížení paralelních strojů, tj. k minimalizaci makespan myšlenka: kratší úlohy lze později využít pro vyrovnání zátěže na konci; jakmile jsou úlohy přiřazeny na stroje, tak je lze přeuspořádat bez změny zatížení PA167 Rozvrhování, H. Rudová: Řídící pravidla 40 23. května 2023 Pravidla s dobou trvání pj Nejkratší doba trvání (Shortest Processing Time first SPT) směřuje k minimalizaci součtu časů konců úloh, tj. WIP (Work In Process, cena za sklad při výrobě) Vážená nejkratší doba trvání (Weighted Shortest Processing Time first WSPT) navíc wj oproti SPT (řadím dle wj /pj ) minimalizace vážených součtu časů konců úloh, tj. WIP optimální pro jeden stroj, kde jsou všechny úlohy dostupné na začátku (rj = 0 pro každou úlohu j) PA167 Rozvrhování, H. Rudová: Řídící pravidla 41 23. května 2023 Další řídící pravidla Kritická cesta (Critical Path CP) vhodné pro precedenční omezení vybírá úlohu, která je první v nejdelším řetězci dob provádění v grafu úloh daném precedencemi vede k minimalizaci makespan Nejméně flexibilní úloha (Least Flexible Job LFJ first) při zadání množiny vhodných strojů vybírá se úloha, která může být prováděna na nejmenším počtu strojů (tj. nejméně alternativ) vede k minimalizaci makespan Náhodné pořadí (Service in Random Order SIRO) náhodný výběr úloh PA167 Rozvrhování, H. Rudová: Řídící pravidla 42 23. května 2023 Řídící pravidla: diskuse Jednoduchá na implementaci Optimální ve speciálních případech Zaměřeny na jedno optimalizační kritérium Kombinování několika řídících pravidel: kompozitní řídící pravidla Použití v praxi pro řadu problémů příliš triviální i tady lze např. použít jako generátor iniciálního řešení nebo jako metodu pro řešení podproblémů používá se pro složité problémy s vysokými nároky na propustnost např. počet naplánovaných aktivit za vteřinu nebo pro problémy s vysokým stupněm dynamiky např. plánování úloh na počítače (neznámá doba trvání, příchody nových úloh, výpadky strojů) PA167 Rozvrhování, H. Rudová: Řídící pravidla 43 23. května 2023 Lokální prohledávání PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 7 Lokální prohledávání obecně 8 Tabu prohledávání 9 Simulované žíhání 10 Genetické algoritmy Konstruktivní vs. lokální metody Konstruktivní metody začneme s prázdným rozvrhem do rozvrhu přidáváme postupně jednotlivé úlohy tak, aby byl rozvrh stále konzistentní Lokální prohledávání začneme s úplným nekonzistentním rozvrhem triviálně: s náhodně vygenerovaným snažíme se najít lepší „podobný” rozvrh lokálními změnami kvalitu rozvrhu posuzujeme optimalizačními kritérii např. makespan optimalizační kritéria vyhodnocují také konzistenci rozvrhu např. počet porušených precedenčních omezení Hybridní přístupy kombinace obou metod PA167 Rozvrhování, H. Rudová: Lokální prohledávání 45 23. května 2023 Algoritmus lokálního prohledávání  ¡ ¢£ x F(S) globální optimum lokální optimum 1 Inicializace k = 0 výběr iniciálního rozvrhu S0 zaznamenání dosud nejlepšího rozvrhu: Sbest = S0 a best_cost = F(S0) 2 Výběr a aktualizace výběr rozvrhu z okolí: Sk+1 ∈ N(Sk ) pokud kriterium přijetí rozvrhu nesplňuje žádný prvek N(Sk ), pak algoritmus končí jestliže F(Sk+1) < best_cost pak Sbest = Sk+1 a best_cost = F(Sk+1) 3 Ukončení jestliže platí podmínky ukončení pak algoritmus končí jinak k = k + 1 a skok na krok 2. PA167 Rozvrhování, H. Rudová: Lokální prohledávání 46 23. května 2023 Jeden stroj + nepreemptivní úlohy Reprezentace rozvrhu permutace n úloh příklad se šesti úlohami: 1,4,2,6,3,5 Definice okolí párová výměna sousedních úloh příklad: 1,4,2,6,3,5 se změní např. na 1,4,2,6,5,3 možných rozvrhů v okolí: n − 1 nebo výběr libovolné úlohy v rozvrhu a umístění na libovolnou pozici příklad: z 1,4,2,6,3,5 náhodně vybereme 4 a dáme ji jinam: 1,2,6,3,4,5 možných rozvrhů v okolí: ≤ n(n − 1) PA167 Rozvrhování, H. Rudová: Lokální prohledávání 47 23. května 2023 Iniciální řešení & podmínky ukončení Iniciální řešení generujeme náhodně heuristicky např. konstruktivním algoritmem jako jsou řídící pravidla Podmínka ukončení typicky zadaný počet iterací omezená doba běhu počet porovnání účelové funkce žádné zlepšení nezískáno po daném počtu iterací PA167 Rozvrhování, H. Rudová: Lokální prohledávání 48 23. května 2023 Výběr rozvrhu z okolí Lokální změna úprava rozvrhu výběrem rozvrhu z okolí Výběr rozvrhu z okolí, tj. prohledání okolí a výběr vhodného kandidáta náhodný výběr výběr nejslibnějšího kandidáta vybíráme rozvrh s nejlepší hodnotou účelové funkce v okolí snaha o zlepšení hodnoty účelové funkce PA167 Rozvrhování, H. Rudová: Lokální prohledávání 49 23. května 2023 Kritérium výběru rozvrhu Kritérium výběru rozvrhu = kriterium přijetí/odmítnutí rozvrhu akceptovat vždy lepší rozvrh? někdy akceptovat i horší rozvrh? Metody akceptování horšího rozvrhu pravděpodobnostní náhodná procházka: s malou pravděpodobností (např. 0.01) akceptujeme i horší rozvrh simulované žíhání deterministická tabu prohledávání: udržujeme tabu seznam několika posledních stavů/změn, které jsou pro další výběr nepřípustné PA167 Rozvrhování, H. Rudová: Lokální prohledávání 50 23. května 2023 Tabu prohledávání Deterministické kritérium přijetí/odmítnutí rozvrhu Udržován tabu seznam několika posledních změn v rozvrhu tabu seznam = seznam zakázaných změn každá nová změna je umístěna na vrchol tabu seznamu př. uchovávané změny: výměna úloh j a k okolí omezeno na rozvrhy, které nepožadují změnu z tabu seznamu zabraňuje cyklení příklad triviáního cyklení: první krok: prohození úloh 3 a 4, druhý krok: prohození úloh 4 a 3 pevná délka seznamu (typicky: 5-9) nejstarší změny z tabu seznamu odstraněny příliš malá délka: nebezpečí cyklení příliš velká délka: může omezit prohledávání příliš Aspirační kritérium určuje, kdy je možné akceptovat i změny v tabu seznamu př. změna z tabu seznamu povolena, pokud zlepšeno F(Sbest) PA167 Rozvrhování, H. Rudová: Lokální prohledávání 51 23. května 2023 Algoritmus tabu prohledávání 1 k = 1 výběr iniciálního rozvrhu S1 použitím heuristiky, Sbest = S1 2 výběr Sc ∈ N(Sk ) jestliže je změna Sk → Sc zakázána protože je v tabu seznamu a není splněno aspirační kritérium pak běž na krok 2 3 jestliže změna Sk → Sc není zakázána tabu seznamem nebo je splněno aspirační kritérium pak Sk+1 = Sc ulož reversní změnu na vrchol tabu seznamu posuň další pozice v tabu seznamu o pozici níže smaž poslední položku z tabu seznamu jestliže F(Sc ) < F(Sbest) pak Sbest = Sc 4 k = k + 1 jestliže platí podmínka ukončení pak konec jinak běž na krok 2. PA167 Rozvrhování, H. Rudová: Lokální prohledávání 52 23. května 2023 Příklad: tabu seznam Uvažujte rozvrhovací problém s 1|| wj Tj opakování: Tj = max(Cj − dj , 0) úlohy 1 2 3 4 pj 10 10 13 4 dj 4 2 1 12 wj 14 12 1 12 Okolí: všechny rozvrhy získané párovou výměnou sousedních úloh Výběr rozvrhu z okolí: vybereme nejlepší rozvrh Tabu seznam: páry úloh (j, k), které byly přehozeny při posledních dvou změnách S1 = (2, 1, 4, 3) F(S1) = wj Tj = 12 · 8 + 14 · 16 + 12 · 12 + 1 · 36 = 500 = F(Sbest) F(1, 2, 4, 3) = 480 F(2, 4, 1, 3) = 436 = F(Sbest) F(2, 1, 3, 4) = 652 Tabu seznam: (1, 4) PA167 Rozvrhování, H. Rudová: Lokální prohledávání 53 23. května 2023 Příklad: tabu seznam (pokračování) S2 = (2, 4, 1, 3), F(S2) = 436 F(4, 2, 1, 3) = 460 F(2, 1, 4, 3)(= 500) tabu! F(2, 4, 3, 1) = 608 Tabu seznam: (2, 4), (1, 4) S3 = (4, 2, 1, 3), F(S3) = 460 F(2, 4, 1, 3)(= 436) tabu! F(4, 1, 2, 3) = 440 F(4, 2, 3, 1) = 632 Tabu seznam: (2, 1), (2, 4) F4 = (4, 1, 2, 3), F(S4) = 440 F(1, 4, 2, 3) = 408 = F(Sbest) F(4, 2, 1, 3)(= 460) tabu! F(4, 1, 3, 2) = 586 Tabu seznam: (4, 1), (2, 1) F(Sbest) = 408 PA167 Rozvrhování, H. Rudová: Lokální prohledávání 54 23. května 2023 Cvičení: tabu seznam Uvažujte rozvrhovací problém s 1|| wj Tj úlohy 1 2 3 4 pj 10 10 13 4 dj 4 2 1 12 wj 14 12 1 12 Aplikujte tabu prohledávání pro iniciální řešení (2, 1, 4, 3) Okolí: všechny rozvrhy získané párovou výměnou sousedních úloh Výběr rozvrhu z okolí: vybereme nejlepší rozvrh Proveďte čtyři iterace Tabu seznam: páry úloh (j, k), které byly přehozeny při 1 jedné poslední změně výsledek: F(Sbest) = 408 2 třech posledních změnách výsledek: F(Sbest) = 436 PA167 Rozvrhování, H. Rudová: Lokální prohledávání 55 23. května 2023 Simulované žíhání: principy Myšlenka: simulace procesu ochlazování kovů na začátku při vyšší teplotě atomy více kmitají a pravděpodobnost změny krystalické mřížky je vyšší postupným ochlazováním se atomy usazují do „nejlepší polohy” s nejmenší energií a pravděpodobnost změny je menší ⇒ na začátku je tedy pravděpodobnost toho, že akceptujeme zhoršování řešení, vyšší Aplikace u lokálního prohledávání lepší nebo stejné řešení akceptováno algoritmus umožňuje akceptovat horší řešení, abychom unikli z lokálního minima pravděpodobnost přijetí horšího řešení se postupně snižuje PA167 Rozvrhování, H. Rudová: Lokální prohledávání 56 23. května 2023 Simulované žíhání: realizace Parametr chlazení t t je iniciálně vysoké: hodně změn je akceptováno t postupně klesá: horší změny jsou skoro vždy odmítnuty Rozdíl mezi kvalitou nového a existujícího řešení ∆c = F(Snew ) − F(Sold ) Metropolisovo kritérium předpoklad: minimalizace F lepší nebo stejné řešení akceptováno: ∆c ≤ 0, tj. F(Snew ) ≤ F(Sold ) pravděpodobnostní přijetí/odmítnutí rozvrhu: horší řešení (∆c > 0) akceptováno pokud U < e−∆c/t U náhodné číslo z intervalu (0, 1) PA167 Rozvrhování, H. Rudová: Lokální prohledávání 57 23. května 2023 Metropolisovo kritérium Horší řešení (F(Snew ) − F(Sold ) = ∆c > 0) akceptováno pokud U < e−∆c/t U náhodné číslo z intervalu (0, 1) ∆c > 0, tj. −∆c < 0 pokud klesá t nebo klesá −∆c, tak klesá i e−∆c/t pomůcka: porovnej e−10/100 vs. e−100/100 a e−10/100 vs. e−10/1 Graf ex PA167 Rozvrhování, H. Rudová: Lokální prohledávání 58 23. května 2023 Algoritmus simulovaného žíhání 1 k = 1 výběr iniciálního rozvrhu S1 použitím heuristiky, Sbest = S1 nastavení iniciální teploty t > 0 výběr funkce redukce teploty α(t) 2 výběr Snew ∈ N(Sk ) jestliže F(Snew ) < F(Sbest) pak Sbest = Snew , Sk+1 = Snew jinak jestliže F(Snew ) ≤ F(Sk ) pak Sk+1 = Snew jinak generuj náhodné číslo Uk jestliže Uk < e F(Sk )−F(Snew ) t pak Sk+1 = Snew jinak Sk+1 = Sk 3 t = α(t) k = k + 1 jestliže platí podmínka ukončení pak konec jinak běž na krok 2. PA167 Rozvrhování, H. Rudová: Lokální prohledávání 59 23. května 2023 Příklad: simulované žíhání Opakování: Tj = max(Cj − dj , 0) Uvažujte rozvrhovací problém s 1|| wj Tj úlohy 1 2 3 4 pj 9 9 12 3 dj 10 8 5 28 wj 14 12 1 12 Použijte simulované žíhání s iniciálním rozvrhem (3, 1, 4, 2) Okolí: všechny rozvrhy, které dostaneme sousedními párovými výměnami Výběr rozvrhu z okolí náhodně Zvolte α(t) = 0.9 × t t0 = 0.9 Použijte následující náhodná čísla: 0.17, 0.91, . . . PA167 Rozvrhování, H. Rudová: Lokální prohledávání 60 23. května 2023 Příklad: simulované žíhání (řešení) Sbest = S1 = (3, 1, 4, 2) F(S1) = wj Tj = 1 · 7 + 14 · 11 + 12 · 0 + 12 · 25 = 461 = F(Sbest ) t0 = 0.9 Snew = (1, 3, 4, 2) F(Snew ) = 316 < F(Sbest ) Sbest = (1, 3, 4, 2) F(Sbest ) = 316 S2 = (1, 3, 4, 2) t = 0.9 × 0.9 = 0.81 Snew = (1, 3, 2, 4) F(Snew ) = 340 > F(Sbest ) = 316 F(Snew ) > F(S2) = 316 U1 = 0.17 > e−(340−316)/0.81 = 1.35 × 10−13 S3 = S2 = (1, 3, 4, 2) t = 0.729 Snew = (1, 4, 3, 2) F(Snew ) = 319 > F(Sbest ) = 316 F(Snew ) > F(S3) = 316 U3 = 0.91 > e−(319−316)/0.729 = 0.016 S4 = S3 = (1, 3, 4, 2) t = 0.6561 . . . PA167 Rozvrhování, H. Rudová: Lokální prohledávání 61 23. května 2023 Praktické úvahy Iniciální teplota musí být „vysoká” kritérium přijetí rozvrhu: 40%–60% vykazuje dobré výsledky v mnoha situacích Parametr chlazení několik změn při dané teplotě jedna změna při každé teplotě t = α × t α typicky v intervalu [0.9,0.99] t = t 1+βt β typicky blízké k 0 PA167 Rozvrhování, H. Rudová: Lokální prohledávání 62 23. května 2023 Genetické algoritmy Srovnání simulované žíhání, tabu prohledávání jedno řešení je přenášeno z jedné iterace do druhé genetické algoritmy udržována populace (několika přenášených) řešení Genetické algoritmy rozvrhy jsou jednotlivci (chromozomy), kteří tvoří populaci rozhodovací proměnná (např. čas jedné úlohy) je gen hodnota rozhodovací proměnné (např. konkrétní čas) je alela každý jednotlivec je vyhodnocen kritériem vhodnosti (fitness) někteří jednotlivci mutují jednotlivci jsou vybrání k reprodukci křížením a mají děti tvořící následující populaci nejvhodnější jedinci přežijí do další populace PA167 Rozvrhování, H. Rudová: Lokální prohledávání 63 23. května 2023 Reprodukce Křížení (crossover): kombinování posloupnosti operací na jednom stroji v jednom rodičovském rozvrhu s posloupností operací na jiném stroji u jiného rodiče Operátor jednoduchého křížení není užitečný! P1=[2 1 3 4 5 6 7] P2=[4 3 1 2 5 7 6] O1=[2 1 3 2 5 7 6] O2=[4 3 1 4 5 6 7] bod řezu Každá alela (hodnota) se musí výskytnout v jedinci právě jednou používány různé formy mapování PA167 Rozvrhování, H. Rudová: Lokální prohledávání 64 23. května 2023 Křížení dané pořadím Křížení dané pořadím (Order crossover, OX) 1 Vybrány náhodně dva body křížení 2 Z rodiče 1 hodnoty mezi nimi zkopírovány na stejné pozice v potomkovi 3 Z rodiče 2 začneme od druhého bodu křížení vybírat prvky, které již nebyly vybrány z rodiče 1, a dávame je do potomka od 2. bodu křížení PA167 Rozvrhování, H. Rudová: Lokální prohledávání 65 23. května 2023 Mutace Mutace umožňuje genetickému algoritmu prohledávat prostor nedosažitelný operátorem křížení Párová výměna sousedů v posloupnosti [1, 2, . . . , n] → [2, 1, . . . , n] Mutace výměnou: změna dvou náhodně vybraných prvků permutace Mutace posunem: přesun náhodně vybraného prvku o náhodný počet míst doleva nebo doprava Mutace promícháním podseznamu: výběr dvou bodů v řetězci náhodně a náhodná permutace prvků mezi těmito dvěma pozicemi PA167 Rozvrhování, H. Rudová: Lokální prohledávání 66 23. května 2023 Výběr Ruletové kolo šance na reprodukci jsou proporcionálně závislé na vhodnosti jedince velikost každého dílu ruletového kola záleží na vhodnosti konkrétního jedince př. kritérium vhodnosti pro 6 jedinců: 5,7,1,3,3,3 první díl má velikost 5, druhý 7, třetí 1, čtvrtý 3, páty 3, šestý 3 vybraný jedinec díl pro 1.jedince díl pro 2.jedince Kroky pro ruletové kolo 1 sečti vhodnost všech jednotlivců populace: TF př. TF = 5 + 7 + 1 + 3 + 3 + 3 = 22 2 generuj náhodné číslo m mezi 0 a 22 3 vrať prvního jednotlivce populace do jehož dílu spadá m čím větší vhodnost jedince, tím větší pravděpodobnost, že se na něj strefíme PA167 Rozvrhování, H. Rudová: Lokální prohledávání 67 23. května 2023 Výběr (pokračování) Turnajový výběr 1 výběr jednoho jedince náhodně vyber skupinu t jedinců z populace vyber nejlepšího jedince 2 pokud potřebujeme vybrat k jedinců, pak postup opakujeme k-krát Jak garantovat, že nejlepší člen/členové populace přežijí? Elitářský model: nejlepší člen populace je vybrán jako člen následující populace nebo nejlepší potomci a rodiče jsou vybírání do následující populace PA167 Rozvrhování, H. Rudová: Lokální prohledávání 68 23. května 2023 Základní implementace genetického algoritmu 1 k = 1 vyber N iniciálních rozvrhů S1,1, . . . , S1,N použitím heuristiky vyhodnoť jednotlivce populace 2 vytvoř nové jednotlivce spojením jednotlivců současné populace pomocí křížení a mutace smaž členy existující populace, aby udělali místo novým jednotlivcům vyhodnoť nové jednotlivce a přidej je do populace Sk+1,1, . . . , Sk+1,N 3 k = k + 1 jestliže platí podmínka ukončení pak vrať nejlepšího jedince jako řešení a skonči jinak běž na krok 2. PA167 Rozvrhování, H. Rudová: Lokální prohledávání 69 23. května 2023 Příklad: genetické algoritmy Uvažujte rozvrhovací problém s 1| | Tj úlohy 1 2 3 4 5 pj 4 3 7 2 2 dj 5 6 8 8 17 Velikost populace: 3 Výběr v každé populaci se reprodukuje nejvhodnější jedinec triviální verze pro snadný výpočet! pro reprodukci je použita párová výměna sousedů počet možných potomků: 4 pro reprodukci náhodně vybrán jeden z nich potomek nahradí nejhoršího rodiče Iniciální populace: náhodné posloupnosti permutací PA167 Rozvrhování, H. Rudová: Lokální prohledávání 70 23. května 2023 Příklad: genetické algoritmy (řešení) Populace 1 Jedinec 25314 14352 12345 Cena 25 17 16 Vybraný jedinec: 12345 s potomkem 13245, cena 20 Populace 2 Jedinec 13245 14352 12345 Cena 20 17 16 Vybraný jedinec: 12345 s potomkem 12354, cena 17 Populace 3 Jedinec 12354 14352 12345 Cena 17 17 16 Vybraný jedinec: 12345 s potomkem 12435, cena 11 Populace 4 Jedinec 14352 12345 12435 Cena 17 16 11 Vybraný jedinec: 12435 – optimální řešení Nevýhoda takto jednoduchého nastavení algoritmu: výběr nejlepšího jedince způsobuje opakovanou reprodukci nejlepšího jedince, dokud není nahrazen lepším potomkem PA167 Rozvrhování, H. Rudová: Lokální prohledávání 71 23. května 2023 Praktické úvahy Velikost populace malá populace riskuje příliš malé pokrytí prohledávacího prostoru velká populace má velké výpočetní nároky dle empirických výsledků velikost populace kolem 30 často adekvátní velikost populace 20-100 je běžná Mutace: obvykle použita s velmi malou pravděpodobností např. mutace jednoho genu jedince PA167 Rozvrhování, H. Rudová: Lokální prohledávání 72 23. května 2023 Matematické programování PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 11 Linerární programování 12 Celočíselné programování Matematické programování Řada rozvrhovacích problémů může být formulována jako matematické programy Lineární programování, nelineární programování, celočíselné programování Předměty PV027 Optimalizace ESF:MPM_OMVE Optimalizační metody eitem PřF:M0160 Optimalizace PA167 Rozvrhování, H. Rudová: Matematické programování 74 23. května 2023 Lineární programování Lineární program (LP) Minimalizace c1x1 + c2x2 + · · · + cnxn za předpokladu a11x1 + a12x2 + · · · + a1nxn ≥ b1 a21x1 + a22x2 + · · · + a2nxn ≥ b2 · · · am1x1 + am2x2 + · · · + amnxn ≥ bm xj ≥ 0 pro j = 1, . . . , n xj ∈ R pro j = 1, . . . , n V maticovém zápisu: minimalizace c x za předpokladu Ax ≥ b x ≥ 0 PA167 Rozvrhování, H. Rudová: Matematické programování 75 23. května 2023 Lineární programování: příklad Výrobce vyrábí 3 výrobky A, B, C, na které spotřebuje materiál M a pracovní dobu P Maximalizujeme denní "Zisk"za předpokladu, že platí: zisk z 1 kusu A = 500 Kč, spotřebujeme 4M a 2P. zisk z 1 kusu B = 800 Kč, spotřebujeme 1M a 5P. zisk z 1 kusu C = 300 Kč, spotřebujeme 2M a 1P. přitom platí denní omezení materiálu M≤30 kusů a pracovních hodin P≤48 hodin (např. 6 lidí pracujících 8 hodin denně) Jak lze použít obecný LP vzorec? max(Zisk) = 500*A + 800*B + 300*C (c1 = 500, x1 = A,...) 4*A + 1*B + 2*C ≤ 30 (omezení materiálu) 2*A + 5*B + 1*C ≤ 48 (omezení prac. hodin) Jak bude vypadat výsledek? V jakých proměnných budeme mít uloženou odpověď na naši otázku? Co budou vyjadřovat? Bude to použitelné v praxi? Max vs. min není problém, neboť platí: max f (x) = −min(−f (x)) pro x ∈ Rn PA167 Rozvrhování, H. Rudová: Matematické programování 76 23. května 2023 Lineární programování: metody řešení Pro malé 2D, 3D problémy si často vystačíme s grafickým řešením cíl je rovnice s parametrem = vrstevnice v ploše omezení jsou poloroviny oblast řešení je průnik polorovin (polyedr, tj. mnohostěn) řešení je průnik rovnice s parametrem a vzniklého polyedru Simplexová metoda efektivní nalezení řešení většinou polynomiální čas použití v praxi pro řešení rozsáhlých problémů Elipsoidová metoda Metoda vnitřních bodů PA167 Rozvrhování, H. Rudová: Matematické programování 77 23. května 2023 Celočíselné programování Celočíselné programování (integer programming IP) lineární programování + všechny proměnné celočíselné Mixed-integer programming (MIP) použity celočíselné i reálné obory hodnot proměnných Mnohem obtížnější než lineární programování Pro rozvrhování mnohem užitečnější PA167 Rozvrhování, H. Rudová: Matematické programování 78 23. května 2023 Celočíselné programování a metody řešení Pracuje se s LP relaxací celočíselného programu, tj. z celočíselného programu jsou odstraněna omezení požadující řešení z oboru celých čísel a řešíme lineární programy a řešíme lineární programy Metoda řezné roviny (cutting plane) generována přídavná lineární omezení (řezné roviny), která musí být splněna v celočíselném řešení přídavná omezení zužují množinu přípustných řešení při zachování celočíselných řešení řešení LP relaxace celočíselného programu s přídavnými omezeními pokud nenalezeno řešení celočíselné, přidáváme dalsí řezné roviny a opakujeme postup Metoda větví a mezí (branch and bound) větvení na rozhodovacích proměnných (xj = r v LP řešení pak přidáme xj ≤ r , xj ≥ r ) lineární programy s přidanými omezeními poskytují hranice (meze) Hybridní metody kombinace různých metod např. kombinace metody větví a mezí a řezných rovin (branch and cut)PA167 Rozvrhování, H. Rudová: Matematické programování 79 23. května 2023 Ukázka problému: rozvrhování směn Směna: množina period, kdy zaměstnanec pracuje často je směna chápána jako množina po sobě jdoucích period př. denní směna 6:00-18:00, noční směna 18:00-6:00 Problém rozvrhování směn cyklus je dán předem např. 1 den je cyklus, časová jednotka (perioda) je hodina je dáno několik vzorků směn s odlišnou cenou cíl je minimalizovat celkovou cenu Problém si popíšeme jako matematický celočíselný program minimalizace n j=1 cj xj za předpokladu: n j=1 aij xj ≥ bi ∀i : 1 ≤ i ≤ m xj ≥ 0 ∀j : 1 ≤ j ≤ n xj ∈ Z ∀j : 1 ≤ j ≤ n PA167 Rozvrhování, H. Rudová: Matematické programování 80 23. května 2023 Formulace problému a řešení m period (hodin) př. od 10:00 do 21:00 V periodě i, i = 1, . . . , m je potřeba bi zaměstnanců př. 10:00: 3, 11:00: 4, 12:00 6, ... n vzorků směn př. 10:00 – 18:00, 13:00 – 21:00, 18:00 – 21:00, ... Každý zaměstnanec přiřazen právě jednomu vzorku Vzorek směny j je vektor (a1j , a2j , . . . , amj ) sloupec matice A aij = 1: i je pracovní perioda aij = 0: jinak př. směna 18:00 – 21:00 odpovídá (0,0,0,0,0,0,0,0,1,1,1) pro 10:00 – 21:00 Cena přiřazení zaměstnance na směnu j: cj xj : proměnná reprezentující počet zaměstnanců přiřazených ke směně j Cíl: minimalizace celkové ceny přiřazených zaměstnanců Problém je NP-těžký, nicméně A má speciální tvar, kde směna je dána jako kontinuální posloupnost 1 platí: řešení tohoto lineárního programu je vždy celočíselné PA167 Rozvrhování, H. Rudová: Matematické programování 81 23. května 2023 Příklad rozvrhování směn v obchodě Obchod otevřen od 10:00 do 21:00 5 vzorků (typů) směny Vzorek Doba Hodin Cena 1 10-18 8 50 2 13-21 8 60 3 12-18 6 30 4 10-13 3 15 5 18-21 3 16 Požadavky na počet zaměstnanců v obchodě Hodina 10 11 12 13 14 15 16 17 18 19 20 Počet zaměstnanců 3 4 6 4 7 8 7 6 4 7 8 Lineární relaxace c = (50, 60, 30, 15, 16) A =                   1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1                   b =                   3 4 6 4 7 8 7 6 4 7 8                  Řešení (x1, x2, x3, x4, x5) = (0, 0, 8, 4, 8) PA167 Rozvrhování, H. Rudová: Matematické programování 82 23. května 2023 Omezující podmínky PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 13 Problém splňování podmínek 14 Rozvrhování jako problém splňování podmínek 15 Podmínky pro zdroje 16 Globální omezení 17 Prohledávání a rozvrhovací strategie Omezení (constraint) Dána množina (doménových) proměnných Y = {y1, . . . , yk } konečná množina hodnot (doména) D = D1 ∪ . . . ∪ Dk Omezení c na Y je podmnožina D1 × . . . × Dk omezuje hodnoty, kterých mohou proměnné nabývat současně Příklad: proměnné: A,B domény: {0,1} pro A {1,2} pro B omezení: A=B nebo (A,B) ∈ {(0,1),(0,2),(1,2)} Omezení c definováno na y1, . . . yk je splněno, pokud pro d1 ∈ D1, . . . dk ∈ Dk platí (d1, . . . dk) ∈ c příklad (pokračování): omezení splněno pro (0, 1), (0, 2), (1, 2), není splněno pro (1, 1) PA167 Rozvrhování, H. Rudová: Omezující podmínky 84 23. května 2023 Problém splňování podmínek (CSP) Dána konečná množina proměnných V = {v1, . . . , vn} konečná množina hodnot (doména) D = D1 ∪ . . . ∪ Dn konečná množina omezení C = {c1, . . . , cm} omezení je definováno na podmnožině V Problém splňování podmínek je trojice (V , D, C) (constraint satisfaction problem CSP) Příklad: proměnné: A,B,C domény: {0,1} pro A {1} pro B {0,1,2} pro C omezení: A=B, B=C Řešení CSP přiřazení hodnot všem proměnným, které splňuje všechna omezení (d1, . . . , dn) ∈ D1 × . . . × Dn je řešení (V , D, C) pro každé ci ∈ C na vi1 , . . . vik platí (di1 , . . . dik ) ∈ ci PA167 Rozvrhování, H. Rudová: Omezující podmínky 85 23. května 2023 Filtrace domén Příklad: Da = {1, 2}, Db = {1, 2, 3} a < b ⇒ hodnota 1 může být z Db bezpečně vyřazena Podmínky se používají aktivně pro odstranění nekonzistencí z problému nekonzistence = hodnota, která nemůže být součástí žádného řešení (nesplňuje nějakou podmínku) Tato tzv. filtrace domén je realizována procedurou REVISE, kterou má každá podmínka PA167 Rozvrhování, H. Rudová: Omezující podmínky 86 23. května 2023 Hranová konzistence (arc consistency AC) Říkáme, že podmínka je hranově konzistentní, pokud pro každou hodnotu každé její proměnné existuje kombinace hodnot pro další proměnné v podmínce tak, že je podmínka splněna Říkáme, že hodnota je podporována/má podporu. REVISE procedura pro hranovou konzistenci odstraní z domén proměnných všechny hodnoty, které nemají podporu Příklad: A=B+C je hranově konzistentní pro B,C ∈ {1,2}, A ∈ {2,3,4} (hodnota 3 proměnné A má např. podporu (3,1,2) pro (A,B,C)) A=B je hranově konzistentní pro A ∈ {0,1}, B ∈ {1,2,3} A=B není hranově konzistentní pro A ∈ {1,2,3}, B ∈ {1,2} (hodnota 3 proměnné A není podporována) CSP je hranově konzistentní, pokud jsou všechny podmínky hranově konzistentní. PA167 Rozvrhování, H. Rudová: Omezující podmínky 87 23. května 2023 Zajištění hranové konzistence Jak zařídit hranovou konzistenci v CSP? Každá podmínka musí být zrevidována Příklad: X in 1..6, Y in 1..6, Z in 1..6, X lct(Ω) − est(A) ⇒ ¬A << Ω A(2) C(4) B(5) 6 16 157 4 16 Ω = {B, C} ¬A << Ω ⇒ start(A) ≥ min{ect(B)|B ∈ Ω} A(2) B(5) C(4) 16 157 4 8 16 PA167 Rozvrhování, H. Rudová: Omezující podmínky 104 23. května 2023 Odvozovací pravidla pro ne-první/ne-poslední Zopakujme Ne-první pravidla: (co se stane, pokud aktivita A bude zpracována jako první?) lct(Ω) − est(A) < p(Ω ∪ {A}) ⇒ ¬A << Ω ¬A << Ω ⇒ start(A) ≥ min{ect(B)|B ∈ Ω} Ne-poslední (symetrická) pravidla: (co se stane, pokud aktivita A bude zpracována jako poslední?) lct(A) − est(Ω) < p(Ω ∪ {A}) ⇒ ¬Ω << A ¬Ω << A ⇒ end(A) ≤ max{lst(B)|B ∈ Ω} V praxi: Vilím 2004: algoritmus s časovou složitostí O(n log n) PA167 Rozvrhování, H. Rudová: Omezující podmínky 105 23. května 2023 Alternativní zdroje Jak modelovat alternativní zdroje pro danou aktivitu? Pro každý zdroj uděláme duplikát aktivity duplikát se účastní příslušných zdrojových podmínek, ale neomezuje další aktivity na daném zdroji „neúspěch” u duplikátu znamená odstranění zdroje z domény proměnné resource(A) příslušné aktivity odstranění zdroje z domény proměnné resource(A) znamená „smazání” odpovídajícího duplikátu původní aktivita se účastní precedenčních podmínek (např. v rámci multi-operační úlohy) omezení časů u duplikátu se propaguje do originálu aktivity a naopak PA167 Rozvrhování, H. Rudová: Omezující podmínky 106 23. května 2023 Alternativní zdroje: odvozovací pravidla Nechť Au reprezentuje duplikát aktivity A na zdroji u∈resource(A), pak probíhají následující propagace: u∈resource(A) ⇒ start(A) ≤ start(Au) u∈resource(A) ⇒ end(Au) ≤ end(A) start(A) ≥ min{start(Au): u ∈ resource(A)} end(A) ≤ max{end(Au): u ∈ resource(A)} neúspěch pro Au ⇒ resource(A)\{u} PA167 Rozvrhování, H. Rudová: Omezující podmínky 107 23. května 2023 Kumulativní zdroje Každá aktivita využívá jistou kapacitu zdroje cap(A) Aktivity mohou být zpracovány paralelně, pokud není překročena kapacita zdroje Kapacita zdroje může být v čase proměnná takové zdroje lze modelovat pomocí v čase neměnné kapacity, od které se odečte kapacita pevně umístěných aktivit, čímž se v každém čase dosáhne požadované kapacity pevně umístěné aktivity vytvoří kapacitní profil zdroje volnákapacita pevná kapacita čas PA167 Rozvrhování, H. Rudová: Omezující podmínky 108 23. května 2023 Agregované požadavky Baptiste et al. 2001 Kdy je dostatečná kapacita pro zpracování aktivity?                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ využitákapacita čas agregované požadavky kapacita zdroje Jak se konstruuje graf agregovaných požadavků?                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢¢¢£ £ £ £ £ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ využitákapacita čas kapacita zdroje agregované požadavky tady aktivita určitě poběží PA167 Rozvrhování, H. Rudová: Omezující podmínky 109 23. května 2023 Podmínka tabulky (timetable constraint) Uvažujeme diskrétní čas Jak zajistit, že v žádném čase není překročena maximální kapacita? ∀t start(Ai )≤t≤end(Ai ) cap(Ai ) ≤ MaxCapacity Tabulka (timetable) pro aktivitu A je množina boolovských proměnných X(A, t) udávajících, zda A běží v čase t ∀t Ai X(Ai , t)cap(Ai ) ≤ MaxCapacity (∗) ∀t, i start(Ai ) ≤ t ≤ end(Ai ) ⇔ X(Ai , t) PA167 Rozvrhování, H. Rudová: Omezující podmínky 110 23. května 2023 Podmínka tabulky: př. s odvozovacími pravidly Počáteční stav Některé pozice zakázány vzhledem ke kapacitě zdroje Nový stav PA167 Rozvrhování, H. Rudová: Omezující podmínky 111 23. května 2023 Podmínka tabulky: odvozovací pravidla Jak realizovat filtraci přes omezení ∀t, i start(Ai ) ≤ t < end(Ai ) ⇔ X(Ai , t) ? Problém: t je zároveň index a také proměnná start(A) ≥ min{t | 1 ∈ X(A,t)} end(A) ≤ 1+max{t | 1 ∈ X(A,t)} X(A,t)=0 ∧ t < ect(A) ⇒ start(A)>t X(A,t)=0 ∧ lst(A)≤t ⇒ end(A)≤t lst(A)≤t ∧ t < ect(A) ⇒ X(A,t)=1 PA167 Rozvrhování, H. Rudová: Omezující podmínky 112 23. května 2023 Cvičení: podmínka tabulky Máme zadány zdroj s kapacitou 2 a aktivity j cap(j) est(j) lct(j) p(j) A 2 1 6 3 B 1 3 9 4 C 1 0 3 2 1 Jak jsou inicializovány proměnné X(j,t)? 2 Jak se jejich hodnoty mění při použití odvozovacích pravidel podmínky tabulky? 3 Jak by mohly vypadat výsledné rozvrhy po aplikaci pravidel? PA167 Rozvrhování, H. Rudová: Omezující podmínky 113 23. května 2023 Cvičení: podmínka tabulky 1 Jak jsou inicializovány proměnné X(j,t)? X(A, 1) až X(A, 5) jsou {0, 1}, X(B, 3) až X(B, 8) jsou {0, 1}, X(C, 0) až X(C, 2) jsou {0, 1}, ostatní proměnné nulové 2 Jak se jejich hodnoty mění při použití odvozovacích pravidel podmínky tabulky? 1 dle (∗) B může začít nejdříve v čase 4 kvůli A, tj. X(B, 3) = 0 a A musí být před B, tj. A nejpozději skončí v čase 5 a X(A, 5) = 0 2 dále z (∗) X(C, 2) = 0, C začne v čase 0 X(A, 1) = 0 a A začne v čase 2 a také B musí začít až v čase 5 a X(B, 4) = 0 a máme jediné řešení PA167 Rozvrhování, H. Rudová: Omezující podmínky 114 23. května 2023 Cvičení: podmínka tabulky PA167 Rozvrhování, H. Rudová: Omezující podmínky 115 23. května 2023 Cvičení: podmínka tabulky PA167 Rozvrhování, H. Rudová: Omezující podmínky 116 23. května 2023 Unární a kumulativní zdroje: shrnutí a možná rozšíření Disjunktivní omezení známe: unarní zdroje, nepřerušitelné aktivity rozšíření: přerušitelné aktivity, kumulativní zdroje Hledání hran známe: unarní zdroje, nepřerušitelné aktivity rozšíření: přerušitelné aktivity, kumulativní zdroje Ne-první/ne-poslední známe: unarní zdroje, nepřerušitelné aktivity rozšíření: kumulativní zdroje Podmínka tabulky známe: kumulativní zdroje, nepřerušitelné aktivity rozšíření: přerušitelné aktivity PA167 Rozvrhování, H. Rudová: Omezující podmínky 117 23. května 2023 Produkovatelné/spotřebovatelné zdroje Zdroj = rezervoár Aktivita konzumuje nějaké množství zdroje cap(A)<0 nebo aktivita produkuje nějaké množství zdroje cap(A)>0 Požadována minimální kapacita zdroje (při konzumaci) a maximální kapacita zdroje nemůže být překročena (produkcí) −1 −1 +1 Kumulativní zdroj může být chápan jako speciální případ rezervoáru každá aktivita konzumuje cap(A) při startu a produkuje cap(A) na konci PA167 Rozvrhování, H. Rudová: Omezující podmínky 118 23. května 2023 Relativní uspořádání Pokud je čas relativní (uspořádání aktivit) potom techniky edge finding a agregovaných požadavků nic neodvodí Pořád ale můžeme používat informace o uspořádání aktivit a spotřebě/produkci daného zdroje Příklad: reservoár: aktivity konzumují a produkují zdroj −1−1−1 +1 lze odvodit nezbytnost přídavné aktivity produkující jednotku zdroje PA167 Rozvrhování, H. Rudová: Omezující podmínky 119 23. května 2023 Optimistický zdrojový profil (orp) Cesta&Stella 1997 orp(A): maximální možná úroveň zdroje v čase, kdy se A začne zpracovávat Aktivity, které musí být před A, se vezmou dohromady s produkčními aktivitami, které mohou být před A orp(A) = InitLevel + cap(A) + B<0 cap(B) Příklad: B??A znamená, že pořadí A a B ještě není známé PA167 Rozvrhování, H. Rudová: Omezující podmínky 120 23. května 2023 orp odvozovací pravidla I. orp(A) < MinLevel ⇒ fail i když je veškerá produkce plánována před A není dosažena minimální požadovaná úroveň zdroje orp(A) = InitLevel + cap(A) + B<0 cap(B) PA167 Rozvrhování, H. Rudová: Omezující podmínky 121 23. května 2023 orp odvozovací pravidla II. orp(A) − cap(D) − D<0 cap(B) < MinLevel ⇒ D << A Uvažujme časový okamžik, kdy začne aktivita A pro libovolné D takové, že D??A a cap(D) > 0: pokud je produkce v D plánována za A a minimální požadovaná úroveň zdroje není dosažena, pak musí být D před A Příklad: PA167 Rozvrhování, H. Rudová: Omezující podmínky 122 23. května 2023 Odvozovací pravidla pro orp orp(A) = InitLevel + prod(A) + B<0 prod(B) orp(A) < MinLevel ⇒ fail přestože veškerá produkce je plánována před A, pořád ještě není dosažena požadovaná minimální úroveň zdroje orp(A) − prod(D) − D<0 prod(C) < MinLevel ⇒ D << A pro libovolné D takové, že D??A a prod(D) > 0 pokud je produkce v D plánována za A a minimální požadovaná úroveň zdroje není dosažena ani když všechny ostatní produkční aktivity jsou před A (které tam být mohou), potom D musí být před A tedy odečteme produkci C, které musí být až po D (tudíž tato produkce není k dispozici pro A) ⇒ v orp(A) je zahrnuta produkce D a produkce aktivit C, které musí být po D. Proto tyto produkce odečítáme od orp(A) a dostáváme se k novému požadavku na MinLevel. PA167 Rozvrhování, H. Rudová: Omezující podmínky 123 23. května 2023 Optimistický zdrojový profil: cvičení orp(A) = InitLevel + cap(A) + B<0 cap(B) orp(A) − cap(D) − D<0 cap(B) < MinLevel ⇒ D << A Máme dány aktivity A, B, C, X, Y , Z a jejich požadované kapacity jsou po řadě 1, 2, 3, 4, 5, −1 Jsou dány precedence: A << B << C, X << Y InitLevel = MinLevel = 0 Jaká je hodnota orp(A)? orp(A) = 0 + cap(A) + 0 + (cap(X) + cap(Y )) = 0 + 1 + 0 + (4 + 5) = 10 Může být X naplánováno po A? 10 − 4 − 5 = 1, tj. ano Co se změní, pokud bychom přidali aktivitu D s následujícími vlastnostmi? cap(D) = −2 D << A orp(A) = 0 + 1 + (−2) + (4 + 5) = 8 a dále 8 − 4 − 5 = −1, tj. X nesmí být po A PA167 Rozvrhování, H. Rudová: Omezující podmínky 124 23. května 2023 Pesimistický zdrojový profil (prp) Cesta&Stella 1997 prp(A): minimální možná úroveň zdroje v čase, kdy se A začne zpracovávat Aktivity, které musí být před A, se vezmou dohromady s konzumačními aktivitami, které mohou být před A prp(A) = InitLevel + cap(A) + B< MaxLevel ⇒ fail i když je veškerá konzumace plánována před A, maximální povolená kapacita zdroje je překročena InitLevel cap(B): all B with B??A and cap(B)<0 cap(B): all B with B< MaxLevel ⇒ D << A Uvažujme časový okamžik, kdy začne aktivita A: pro libovolné D takové, že D??A a cap(D) < 0: jestliže je konzumace v D plánována po A a je překročena maximální povolená úroveň zdroje, pak musí být D před A Příklad: InitLevel cap(B): all B with B??A and cap(B)<0 cap(B): all B with B< MaxLevel ⇒ fail přestože veškerá konzumace je plánována před A, je maximální úroveň zdroje (kapacita) překročena prp(A) − prod(D) − D< MaxLevel ⇒ D << A pro libovolné D takové, že D??A a prod(D) < 0 pokud je konzumace v D plánována za A a maximální úroveň zdroje je překročena i když všechny ostatní konzumační aktivity jsou před A (které tam být mohou), potom D musí být před A tedy přičteme konzumaci C, které musí být až po D (tudíž se tato konzumace neodehraje před A) ⇒ v prp(A) je zahrnuta konzumace D a konzumace aktivit C, které musí být po D. Proto tyto konzumace přičítáme k prp(A) a dostáváme se k novému požadavku na MaxLevel. PA167 Rozvrhování, H. Rudová: Omezující podmínky 128 23. května 2023 Globální podmínky Pro reprezentaci zdrojů využívány v programovacích jazycích tzv. globální podmínky definované pro libovolný konečný počet proměnných komplexní podmínky s vlastním propagačním algoritmem Základní globální podmínky (pro rozvrhování) příklady z IBM ILOG OPL (Optimization Programming Language) všechny proměnné různé allDifferent disjunktivní zdroj dvar interval, dvar sequence noOverlap kumulativní zdroj cumuFunction, pulse PA167 Rozvrhování, H. Rudová: Omezující podmínky 129 23. května 2023 Všechny proměnné různé Proměnné v poli Array jsou různé reprezentace unárního zdroje s jednotkovou dobou trvání všech aktivit dvar int Array[Interval]; globální podmínka: allDifferent(Array) učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Příklad: učitelé musí učit v různé hodiny Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr ∈ {3, 4}, Eva ∈ {3, 4} PA167 Rozvrhování, H. Rudová: Omezující podmínky 130 23. května 2023 Intervalové proměnné Intervalová proměnná: pro modelování časového intervalu (úlohy, aktivity) hodnotou intervalové proměnné je celočíselný interval [start, end) příklad: dvar interval x in 0..1000000 size 100..200; PA167 Rozvrhování, H. Rudová: Omezující podmínky 131 23. května 2023 Disjunktní rozvrhování Sekvenční proměnná p definována na množině intervalových proměnných x dvar interval x[i in 1..n] ...; dvar sequence p in x; hodnota intervalové proměnné p je permutace přítomných intervalů pozor, permutace t ještě neimplikuje žádné uspořádání v čase Omezení noOverlap(p) vyjadřuje, že sekvenční proměnná p reprezentuje řetězec nepřekrývajících se intervalových proměnných pro vyjádření rozvrhování na unárním/disjunktivním zdroji, kde se intervaly/úlohy nepřekrývají PA167 Rozvrhování, H. Rudová: Omezující podmínky 132 23. května 2023 Precedence, účelová funkce Mezi intervalovými proměnnými můžeme definovat precedenční podmínky: dvar interval i; dvar interval j; endBeforeStart(i, j); startBeforeStart(i, j); startAtStart(i, j); ... Pro vytváření účelových funkcí nebo definici omezení startOf(x) endOf(x) sizeOf(x, V) Příklad: minimalizace makespanu minimize max(i in 1..n) endOf(x[i]) PA167 Rozvrhování, H. Rudová: Omezující podmínky 133 23. května 2023 Příklad: rozvrhování problému job-shop tuple Operation { int mch; // machine int pt; // processing time }; Operation Ops[j in Jobs][p in Pos] = ...; op[j][p] odkazuje operaci úlohy j, která je zpracovávána v rámci úlohy jako p-tá PA167 Rozvrhování, H. Rudová: Omezující podmínky 134 23. května 2023 Kumulativní zdroj pomocí kumulativní funkce Hodnota výrazu kumulativní funkce reprezentuje vývoj kvantity v čase, která může být inkrementálně změněna (snížena nebo navýšena) intervalovými proměnnými. Intervalové proměnné x[i] přispívají do kumul. funkce po dobu svého provádění int capacity[1..5] = [1,3,2,4,1]; cumulFunction y = sum(i in 1..5) pulse(x[i],capacity[i]); Omezení na výrazech kumulativní funkce: pro omezení kapacity zdroje int h = ... cumulFunction f= ... f<=h Příklad: job-shop a omezení celkového počtu strojů cumulFunction allMachines = sum(j in Jobs, p in Pos) pulse(op[j][p],1); allMachines <= m; PA167 Rozvrhování, H. Rudová: Omezující podmínky 135 23. května 2023 Prohledávání/přiřazování (opakování) Konzistenční techniky jsou (obvykle) neúplné ⇒ potřeba prohledávací algoritmus, který vyřeší "zbytek" Přiřazovaní (labeling) prohledávání do hloubky (DFS/BT) přiřaď hodnotu do proměnné propaguj = udělěj problém lokálně konzistentní vrať se v případě neúspěchu PA167 Rozvrhování, H. Rudová: Omezující podmínky 136 23. května 2023 Způsoby větvení (opakování) Jaká proměnná má být ohodnocena první? princip prvotního neúspěchu (first-fail) preferuj proměnnou, jejíž přiřazení je nejobtížnější (hrozí u ní nebezpečí failu) Jaká hodnota má být vyzkoušena první? princip prvotního úspěchu (succeed-first) preferuj hodnoty, které nejspíše patří do řešení PA167 Rozvrhování, H. Rudová: Omezující podmínky 137 23. května 2023 Schémata větvení Větvení = řešení disjunkcí Tradiční rozvrhovací přístupy kritická rozhodnutí se dělají první vyřeš kritická místa (bottlenecks), . . . definuje tvar prohledávacího stromu podobně jako princip prvního neúspěchu (first-fail) preferuj alternativy s větší flexibilitou definuje pořadí větví pro prozkoumání podobně jako princip prvního úspěchu (succeed-first) Jak popsat, co je kritické a co je flexibilní? PA167 Rozvrhování, H. Rudová: Omezující podmínky 138 23. května 2023 Rezerva (slack) Smith&Cheng 1993 Rezerva (slack) je formální popis flexibility Rezerva pro dané pořadí dvou aktivit „volný čas pro posunování aktivit” A B slack for A< pmin j ∀j ∈ GCP Pokud takový řez neexistuje STOP, jinak běž na krok 3 3 Pro každý minimální řez: spočítej cenu redukující všechny doby provádění o 1 časovou jednotku Vyber minimální řez s nejnižší cenou pozn. abychom za snížení zaplatili co nejnižší cenu Jestliže je cena řezu menší než fixní režijní náklady c0 za časovou jednotku běž na krok 4, jinak STOP 4 Redukuj všechny doby provádění v minimálním řezu o 1 časovou jednotku Urči novou množinu kritických cest Reviduj graf GCP a běž na krok 2 PA167 Rozvrhování, H. Rudová: Plánování projektu 167 23. května 2023 Lineární program Heuristika negarantuje nalezení optima Celková cena je lineární c0Cmax + n j=1 cb j + cj (pmax j − pj ) všimněte si: stejná účelová funkce jako cena za provádění projektu Lineární program: cb j a cj pmax j minimalizace: c0Cmax − n j=1 cj pj se nemění za předpokladu: xk − pj − xj ≥ 0 ∀j ∈ Preck pj ≤ pmax j ∀j pj ≥ pmin j ∀j xj ≥ 0 ∀j Cmax − xj − pj ≥ 0 ∀j kde xj je nejdřívější možný startovní čas úlohy j PA167 Rozvrhování, H. Rudová: Plánování projektu 168 23. května 2023 Přidání pracovní síly Pracovní síla = operátor = zdroj Problém popsán v literatuře jako problém plánování projektu s omezenými zdroji resource-constrained project scheduling problem (RCPSP) n úloh N zdrojů Ri kapacita zdroje i pj doba provádění úlohy j Rij požadavek úlohy j na zdroj i Precj (přímí) předchůdci úlohy j PA167 Rozvrhování, H. Rudová: Plánování projektu 169 23. května 2023 Formulace celočíselného programování Pomocná úloha n + 1 jako stok, pn+1 = 0 xjt = 1 úloha j je dokončena v čase t xjt = 0 jinak Kapacita zdroje i, který potřebuje úloha j v intervalu [t − 1, t]: Rij t+pj −1 u=t xju tt−1 pjj t+pj −1 u=t xju . . . počítá, zda úloha j běží v čase [t − 1, t] př. úloha s Sj = 2, pj = 2 a t = 2, 3, 4, 5 (xj4 = 1, pro t = 3, 4 úloha započítána) H jako horní hranice makespan: H = n j=1 pj Koncový čas úlohy j: Cj = H t=1 t xjt Makespan: Cmax = H t=1 t xn+1,t koncový čas stoku PA167 Rozvrhování, H. Rudová: Plánování projektu 170 23. května 2023 Celočíselný program Minimalizace H t=1 t xn+1,t minimalizace makespan za předpokladu jestliže j je předchůdce k, pak Cj ≤ Sk , tj. Cj ≤ Ck − pk , tj. Cj + pk − Ck ≤ 0 H t=1 t xjt + pk − H t=1 t xkt ≤ 0 ∀j ∈ Preck pro každý čas t: požadavek na zdroj i nepřeroste kapacitu i n j=1  Rij t+pj −1 u=t xju   ≤ Ri ∀i ∀t každá úloha j skončí právě jednou H t=1 xjt = 1 ∀j PA167 Rozvrhování, H. Rudová: Plánování projektu 171 23. května 2023 Diskuse Řešení celočíselného programu obtížné Při velkém počtu úloh a dlouhém časovém horizontu použití heuristik Lze použít programování s omezujícími podmínkami kumulativní zdroje precedenční podmínky Probírané speciální případy problému job shop + makespan timetabling PA167 Rozvrhování, H. Rudová: Plánování projektu 172 23. května 2023 Plánování projektu: shrnutí Základní problém s neomezenými zdroji metoda kritické cesty Neomezené zdroje + variabilní doba trvání (lineární) kompromisní heuristika mezi časem a cenou lineární programování Problém plánování projektu s omezenými zdroji celočíselné programování heuristiky programování s omezujícími podmínkami PA167 Rozvrhování, H. Rudová: Plánování projektu 173 23. května 2023 Plánování úloh na jednom stroji PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 23 Řídící pravidla (také paralelní stroj) 24 Metoda větví a mezí 25 Paprskové prohledávání 26 Matematické programování Jeden stroj a paralelní stroj Dekompoziční problémy pro složité (flexible) job shop problémy používají jeden stroj paralelní stroj jako podproblémy při řešení Metody řešení: řídící pravidla metoda větví & mezí paprskové prohledávání PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 175 23. května 2023 Řídící pravidla pro jeden stroj: přehled Cmax a rj = 0, dj = ∞ (snadné: nezávisí na rozvrhu) wj Cj a rj = 0, dj = ∞ vážená nejkratší doba provádění (WSPT) je optimální rozvrhuje úlohy v klesajícím pořadí podle wj /pj Lmax a rj = 0 nejdřívější termín dokončení (EDD) je optimální rozvrhuje úlohy ve vzrůstající velikosti dj minimální rezerva (MS) pravidlo příbuzné EDD ale dynamické max(dj − pj − t, 0), kde je t aktuální čas Lmax a rozdílné rj NP-těžký problém základní podproblém v rámci známé heuristiky posouvání kritického místa řešen pomocí metody větví a mezí nebo dynamického programování Tj , wj Tj mnohem obtížnější na optimalizaci kompozitní řídící pravidlo apparent tardiness cost (ATC) využívající kombinaci WSPT a MS PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 176 23. května 2023 Řídící pravidla a paralelní stroj: přehled Cmax : důležité kritérium při balancování zátěže strojů NP-těžký nejdelší doba provádění (LPT) kratší úlohy odloženy, protože je snadnější je narozvrhovat nalezne řešení s garancí rozsahu 33% optima Cj a rj = 0 nepreemptivní nejkratší doba provádění (SPT) nepreemptivní SPT minimalizuje Cj nepreemptivní SPT zůstává optimální i při povolených přerušeních wj Cj a rj = 0 NP-těžký WSPT grarantuje řešení v rámci 22% optima wj Tj ještě obtížnější problém lze použít ATC (apparent tardiness cost), ale kvalita řešení nemusí být dobrá PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 177 23. května 2023 Vážený součet koncových časů pro jeden stroj Řídící pravidlo vážená nejkratší doba trvání (weighted shortest processing time, WSPT) je optimální pro 1|| wj Cj . WSPT rozvrhuje úlohy v klesajícím pořadí podle wj /pj Důkaz: předpokládejme, že to není pravda a že S je optimální pak existují dvě sousední úlohy, např. úloha j následovaná úlohou k takové, že wj pj < wk pk , tj.pkwj < pjwk po provedení párové výměny máme rozvrh S j kt+p +p j k t+p +p j k k j ... ... ... ... S: S’: Příspěvky do účelové funkce pro j a k: S : (t + pj )wj + (t + pj + pk )wk = twj + pj wj + twk + pjwk + pk wk S : (t + pk )wk + (t + pk + pj )wj = twk + pk wk + twj + pkwj + pj wj wj Cj pro S < wj Cj pro S spor s optimalitou S PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 178 23. května 2023 Zpoždění pro jeden stroj EDD optimální pro 1||Lmax Rozdílné termíny dostupnosti rj , tj. problém 1|rj |Lmax : NP-úplný problém Proč je tento problém tak obtížný? PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 179 23. května 2023 1|rj|Lmax Úlohy 1 2 3 pj 4 6 5 rj 0 3 5 dj 8 14 10Rozvrh pomocí EDD: r3 r2r1 d1 d3 d2 1 10 1550 32 Lmax = max(L1, L2, L3) = = max(C1 − d1, C2 − d2, C3 − d3) = = max(4 − 8, 10 − 14, 15 − 10) = = max(−4, −4, 5) = 5 Existuje lepší řešení? PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 180 23. května 2023 Rozvrh se zdržením pro 1|rj|Lmax Pozdržíme provádění úloh: r3 r2r1 d1 d3 d2 21 10 1550 3 2 Lmax = max(L1, L2, L3) = = max(C1 − d1, C2 − d2, C3 − d3) = = max(4 − 8, 16 − 14, 10 − 10) = = max(−4, 2, 0) = 2 Problém je obtížný, protože optimální rozvrh není nutně bez zdržení PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 181 23. května 2023 1|rj, prmp|Lmax Preemptivní úlohy: je možné přerušit jejich provádění Preemptivní verze řídících pravidel: nečekáme až na dokončení prováděné úlohy pro výběr další úlohy k provádění v každém časovém okamžiku je nutné zvážit, zda není k dispozici jiná prioritnější úloha (např. vzhledem k jejímu rj ) pokud existuje prioritnější úloha, přerušíme aktuální úlohu a spustíme prioritnější úlohu Cvičení: aplikujte preemptivní EDD na předchozí příklad Preemptivní EDD pravidlo je optimální pro preemptivní verzi problému 1|rj , prmp|Lmax Preemptivní EDD je optimální pro předchozí příklad PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 182 23. května 2023 Metoda větví a mezí Prohledávací prostor se rychle zvětšuje se zvětšujícím počtem proměnných Metoda větví a mezí (Branch & Bound search, BB) založena na myšlence postupného dělení prohledávacího prostoru S SS SS S . . . . . . . . . 12 13 1 2 n S = S1 ∪ S2 ∪ · · · ∪ Sn S1 ∩ S2 ∩ · · · ∩ Sn = ∅ potřebujeme spočítat hranici/mez na cenu řešení části stavového prostoru, které dávají řešení horší než tato mez nemusíme prohledávat PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 183 23. května 2023 Výpočet dolní hranice řešení Typický způsob, jak zjistit hranice je relaxovat (zjednodušit) původní problém (např. odstraněním některých požadavků) na snadno řešitelný problém jestliže neexistuje řešení pro relaxovaný problém, pak neexistuje řešení pro původní problém (větev lze smazat) jestliže je optimální řešení relaxovaného problému zároveň řešením původního problému, pak je pro něj také optimální jestliže optimální řešení není řešením původního problému, pak dává hranici na jeho řešení (původní problém nebude mít zcela jistě lepší řešení) PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 184 23. května 2023 Pravidla větvení pro 1|rj|Lmax *,*,*,* 1,3,*,*1,2,*,* 2,*,*,*1,*,*,* n,*,*,* . . . . . . . . . Uroven 2 Uroven 1 Uroven 0 Rozvrh je konstruován od času t = 0 Úroveň 1: n větví, ve kterých je každá z n úloh rozvrhována první Úroveň k − 1: úlohy j1, . . . , jk−1 jsou rozvrhovány v pořadí 1, . . . , k − 1 Úlohu c uvažujeme na úrovni k (a odpovídající větvení) pokud: rc < minl∈J (max(t, rl ) + pl ) = PS J množina dosud nerozvržených úloh t čas, kdy je skončena jk−1 a lze rozvrhovat další úlohu pokud je rc ≥ PS, pak je třeba rozvrhovat úlohu minimalizující PS na pozici k a úlohu c na pozici k + 1 (nebo i později) (toto uspořádání úloh stejně vůbec neovlivní čas dokončení c) PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 185 23. května 2023 Dolní hranice pro 1|rj|Lmax Relaxace problému 1|rj |Lmax je problém 1|rj , prmp|Lmax neumožnění přerušení je omezení pouze v původním problému 1|rj |Lmax Preemptivní EDD pravidlo je optimální pro 1|rj , prmp|Lmax ⇒ Preemptivní rozvrh (rozvrh bez zdržení) určitě nebude mít Lmax větší než ne-preemptivní rozvrh (rozvrh potenciálně se zdržením) ⇒ Dolní hranice na úrovni k − 1 může být založena na rozvrhu zbývajících úloh podle preemptivního EDD pravidla + Jestliže preemptivní EDD dává nepreemptivní rozvrh, pak můžeme všechny uzly s větší dolní hranicí zrušit PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 186 23. května 2023 Příklad: BB pro 1|rj|Lmax Úlohy 1 2 3 4 pj 4 2 6 5 rj 0 1 3 5 dj 8 12 11 10 2,*,*,* 4,*,*,* 1,3,*,* 1,3,4,2 3,*,*,* uloha 2 muže být prováděna před ulohou 3 uloha 1 muže být prováděna před ulohou 4 *,*,*,* 1,2,*,* 1,*,*,* LB=5 LB=6 LB=5 LB=7 1,4,*,* nemá smysl prozkoumávat, protože už v 1,3,*,* máme šanci na řešení s minimání LB=5 PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 187 23. května 2023 Příklad: dolní hranice BB pro 1|rj|Lmax Úlohy 1 2 3 4 pj 4 2 6 5 rj 0 1 3 5 dj 8 12 11 10 (3,*,*,*) uloha 2 muže být prováděna před ulohou 3 (4,*,*,*) uloha 1 i 2 muže být prováděna před ulohou 3 (*,*,*,*) (1,2,*,*) 1 [0,4] L =−4 2 [4,6] L =−6 4 [6,11] L =1 3 [11,17] L =6 2 1 3 4 (1,3,*,*) 1 [0,4] L =−4 3 [4,10] L =−1 4 [10,15] L =5 2 [15,17] L =52 4 3 1 Rozvrh: (1,3,4,2) 4 2 1 2 [1,3] L =−9 (2,*,*,*) 1 [3,7] L =−1 4 [7,12] L =2 3 [12,18] L =73 (1,*,*,*) 3 [4,5] 2 [15,17] L = 5 1 [0,4] L =−41 2 3 4 3 [10,15] L = 4 4 [5,10] L =0 PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 188 23. května 2023 Paprskové prohledávání Metoda větví a mezí uvažuje každý uzel pro n úloh: na první úrovni n uzlů, na druhé úrovni n(n − 1) uzlů, na třetí úrovni n(n − 1)(n − 2) uzlů, . . . ⇒ n! uzlů na n-té úrovni garantuje optimum obvykle příliš pomalá Paprskové prohledávání (Beam Search, BS) uvažuje pouze slibné uzly šířka paprsku (beam width) udává, u kolika uzlů budeme na každé úrovni pokračovat v prohledávání negarantuje optimální řešení mnohem rychlejší PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 189 23. května 2023 Větvení Kriterium: 1|| j wj Tj Problém: Úlohy 1 2 3 4 pj 10 10 13 4 rj 4 2 1 12 dj 14 12 1 12 Šířka paprsku 2: 2,*,*,* 4,*,*,*3,*,*,* *,*,*,* 1,*,*,* (1,4,2,3) (2,4,1,3) (3,4,1,2) (4,1,2,3) ATC pravidlo 408 436 814 440 PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 190 23. května 2023 Paprskové prohledávání 2,*,*,* 2,4,*,*1,4,*,* 4,*,*,*3,*,*,* 2,1,*,* 2,4,1,3 2,4,3,11,4,3,2 1,2,*,* 1,4,2,3 *,*,*,* 1,*,*,* 2,3,*,*1,3,*,* PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 191 23. května 2023 Diskuse Kompromisy při implementaci: podrobná evaluace uzlů (kvůli přesnosti) odhad evaluace uzlu (kvůli rychlosti) Dvoufázová procedura odhad evaluace je prováděn pro všechny uzly na úrovni k podrobná evaluace šířka filtru > šířka paprsku prováděna pro počet uzlů odpovídající šířce filtru PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 192 23. května 2023 Matematické programování (opakování) Celočíselný program minimalizace n j=1 cj xj za předpokladu: n j=1 aij xj ≥ bi ∀i : 1 ≤ i ≤ m xj ≥ 0 ∀j : 1 ≤ j ≤ n xj ∈ Z ∀j : 1 ≤ j ≤ n PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 193 23. května 2023 Model problému 1| | n j=1 wjCj Proměnné xjt = 1 jestliže úloha j začne v čase t = 0 jinak Formulace celočíselného programu Minimalizace n j=1 Cmax −1 t=0 wj (t + pj )xjt tj. n j=1 wj Cj za předpokladu xjt ∈ 0, 1 ∀j, t každá úloha právě jednou začne: Cmax −1 t=0 xjt = 1 ∀j v každém čase běží právě jedna úloha: n j=1 t−1 s=max(t−pj ,0) xjs = 1 ∀t (pro každé t běží v intervalu t − 1, t) právě jedna úloha) PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 194 23. května 2023 V každém čase jedna úloha Proměnné xjt = 1 jestliže úloha j začne v čase t V každém čase, tj. v každém intervalu t − 1, t , běží právě jedna úloha: n j=1 t−1 s=max(t−pj ,0) xjs = 1 ∀t PA167 Rozvrhování, H. Rudová: Plánování úloh na jednom stroji 195 23. května 2023 Plánování job-shopu PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 27 Disjunktivní grafová reprezentace 28 Matematické programování a job shop 29 Metoda větví a mezí pro job shop 30 Posunování kritického místa (shifting bottleneck) Multi-operační rozvrhování: job shop s minimalizací makespan n úloh m strojů operace (i, j): provádění úlohy j na stroji i Pořadí operací úlohy je stanoveno: (i, j) → (k, j) specifikuje, že úloha j má být prováděna na stroji i dříve než na stroji k pij : trvání operace (i, j) Cíl: rozvrhovat úlohy na strojích bez překrytí na strojích bez překrytí v rámci úlohy minimalizace makespan Cmax PA167 Rozvrhování, H. Rudová: Plánování job-shopu 197 23. května 2023 Příklad: job shop problém Data: stroje: M1, M2, M3 úlohy: J1 : (3, 1) → (2, 1) → (1, 1) J2 : (1, 2) → (3, 2) J3 : (2, 3) → (1, 3) → (3, 3) doby trvání: p31 = 4, p21 = 2, p11 = 1 p12 = 3, p32 = 3 p23 = 2, p13 = 4, p33 = 1 Řešení: 105 12 M3 M2 M1 0 PA167 Rozvrhování, H. Rudová: Plánování job-shopu 198 23. května 2023 Disjunktivní grafová reprezentace Graf G = (N, A ∪ B ∪ P) uzly odpovídají operacím N = {(i, j)|(i, j) je operace} ∪ {U, V } dva pomocné uzly U a V reprezentující zdroj a stok konjunktivní hrany A reprezentují pořadí operací úlohy (i, j) → (k, j) ∈ A ⇐⇒ operace (i, j) předchází (k, j) disjunktivní hrany B reprezentují konflikty na strojích dvě operace (i, j) a (i, l) jsou spojeny dvěma opačně orientovanými hranami pomocné hrany P hrany z U ke všem prvním operacím úlohy hrany ze všech posledních operací úlohy do V 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V PA167 Rozvrhování, H. Rudová: Plánování job-shopu 199 23. května 2023 Výběr hran Pojmy: Podmnožina D ⊂ B je nazývána výběr, jestliže obsahuje z každého páru disjuktivních hran právě jednu Výběr D je splnitelný, jestliže výsledný orientovaný graf G(D) = (N, A ∪ D ∪ P) je acyklický jedná se o graf s pomocnými, konjunktivními hranami a vybranými disjunktními hranami Poznámky: splnitelný výběr určuje posloupnost, ve které jsou operace prováděny na strojích vztah splnitelného výběru a (konzistentního) rozvrhu? každý (konzistentní) rozvrh jednoznačně určuje splnitelný výběr každý splnitelný výběr jednoznačně určuje (konzistentní) rozvrh PA167 Rozvrhování, H. Rudová: Plánování job-shopu 200 23. května 2023 Příklad: nesplnitelný výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V V grafu existuje v důsledku nevhodného výběru hran cyklus: (1, 2) → (3, 2) (3, 2) → (3, 1) → (2, 1) → (1, 1) → (1, 2) ⇒ nelze splnit (k tomuto výběru neexistuje rozvrh) PA167 Rozvrhování, H. Rudová: Plánování job-shopu 201 23. května 2023 Příklad: výběr pro daný rozvrh Nalezněte (splnitelný) výběr hran pro daný rozvrh: 105 12 M3 M2 M1 0 Konstrukce odpovídajícího výběru: vybereme (jeden stroj po druhém) disjunktivní hrany, které odpovídají uspořádání operací na stroji v daném rozvrhu: 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V PA167 Rozvrhování, H. Rudová: Plánování job-shopu 202 23. května 2023 Příklad: rozvrh pro daný splnitelný výběr Jakým způsobem nalézt rozvrh pro daný splnitelný výběr? 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V Tedy: jakým způsobem lze nalézt tento odpovídající rozvrh: 105 M3 M2 M1 0 15 20 PA167 Rozvrhování, H. Rudová: Plánování job-shopu 203 23. května 2023 Výpočet rozvrhu pro výběr Metoda: výpočet nejdelších cest z U do dalších uzlů v G(D) obdoba dopředného zpracování z metody kritické cesty pro plánování projektu Technický popis: uzly (i, j) mají ohodnocení pij , uzel U má váhu 0 délka cesty i1, i2, . . . , ir je součet ohodnocení uzlů i1, i2, . . . , ir−1 spočítej délku lij nejdelší cesty z U do (i, j) a V 1 lU = 0 a pro každý uzel (i, j) s jediným předchůdcem U: lij = 0 2 vypočítej postupně pro všechny zbývající uzly (i, j) (a pro uzel V): lij = max ∀(k,l):(k,l)→(i,j) (lkl + pkl ) tj. projdeme všechny předchůdce (k, l) uzlu (i, j) délka cesty do (i, j) přes (k, l) je lkl + pkl zahaj operaci (i, j) v čase lij délka nejdelší cesty z U do V je rovna makespan tato cesta je kritická cesta PA167 Rozvrhování, H. Rudová: Plánování job-shopu 204 23. května 2023 Výpočet rozvrhu pro výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 2 4 1 124 33 Výpočet lij : uzel (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka 0 0 0 4 4 6 7 11 12 PA167 Rozvrhování, H. Rudová: Plánování job-shopu 205 23. května 2023 Disjunktivní programování Formulace disjunktivního programování nejčastěji používaná formulace matematického programování pro job shop bez recirkulace (bez recirkulace: úlohy prováděny na stroji nejvýše jednou) vychází z disjunktivní grafové reprezentace Disjunktivní programování jedná se o matematické programování omezení rozděleny do množin konjunktivních omezení všechna tato omezení musí být splněna standardní matematické programování: všechna omezení konjuktivní a jedné nebo více množin disjunktivních omezení z každé množiny disjunktivních omezení musí být alespoň jedno omezení splněno PA167 Rozvrhování, H. Rudová: Plánování job-shopu 206 23. května 2023 Disjunktivní programování a job shop yij značí startovní čas operace (i, j) úlohy j na stroji i Minimalizace Cmax za předpokladu ykj − yij ≥ pij ∀(i, j) → (k, j) ∈ A Cmax − yij ≥ pij ∀(i, j) ∈ N yij − yil ≥ pil nebo yil − yij ≥ pij ∀(i, l), (i, j) : i = 1 . . . m yij ≥ 0 ∀(i, j) ∈ N Tato formulace ale nezajišťuje existenci standardní řešící procedury Problém velmi obtížný Ukážeme další přístupy: enumerační procedury (BB), heuristiky (posunování kritického místa) PA167 Rozvrhování, H. Rudová: Plánování job-shopu 207 23. května 2023 Typy rozvrhů Rozvrh je bez zdržení (nondelay), pokud žádný stroj nečeká, když existuje dostupná operace Rozvrh je aktivní, pokud nemůže být žádná operace rozvrhována dříve změnou posloupnosti úloh na stroji bez pozdějšího naplánování jiné operace redukce makespan aktivního rozvrhu je možná pouze zvýšením startovního času alespoň jedné operace optimální rozvrh je aktivní rozvrh PA167 Rozvrhování, H. Rudová: Plánování job-shopu 208 23. května 2023 Příklad: aktivní vs. neaktivní rozvrh Neaktivní rozvrh: 105 M3 M2 M1 0 15 20 Aktivní rozvrh: 105 M3 M2 M1 0 15 20 PA167 Rozvrhování, H. Rudová: Plánování job-shopu 209 23. května 2023 Aplikace metody větví a mezí na job shop Víme: optimální rozvrh je aktivní rozvrh Metoda řešení generování množiny aktivních rozvrhů výběr nejlepšího rozvrhu Zlepšení použití metody větví a mezí při generování Důsledek potřebujeme algoritmus pro generování všech aktivních rozvrhů Značení Ω: množina všech operací, jejichž předchůdci už jsou narozvrhováni rij : nejdřívější startovní čas operace (i, j) ∈ Ω může být spočítano pomocí výpočtu nejdelší cesty Ω : podmnožina Ω PA167 Rozvrhování, H. Rudová: Plánování job-shopu 210 23. května 2023 Generování množiny všech aktivních rozvrhů 1 Inicializace Ω := {první operace každé úlohy} rij := 0 pro všechna (i, j) ∈ Ω 2 Výběr stroje spočítej pro současný částečný rozvrh t(Ω) := min (i,j)∈Ω {rij + pij } tj. kdy nejdřívě může nějaká úloha z Ω skončit i∗ := stroj, na němž bylo dosaženo minima 3 Větvení Ω := {(i∗ , j)|ri∗j < t(Ω)} pro všechna (i∗ , j) ∈ Ω přidej do rozvrhu (i∗ , j) jako další operaci na stroji i∗ smaž (i∗ , j) z Ω přidej následníky úlohy (i∗ , j) do Ω běž na krok 2 PA167 Rozvrhování, H. Rudová: Plánování job-shopu 211 23. května 2023 Příklad: generování aktivních rozvrhů Úlohy: J1 : (3, 1) → (2, 1) → (1, 1) J2 : (1, 2) → (3, 2) J3 : (2, 3) → (1, 3) → (3, 3) Částečný rozvrh: neřešíme od začátku, začneme řešit už s tímto rozvrhem, aby byl postup demonstrativní 5 M3 M2 M1 0Ω = {(1, 1), (3, 2), (1, 3)} p11 = 1, p32 = 3, p13 = 4 r11 = 6, r32 = 4, r13 = 3 t(Ω) = min(6 + 1, 4 + 3, 3 + 4) = 7 např. i∗ = M1 Ω = {(1, 1), (1, 3)} Rozšířené částečné rozvrhy: 5 M3 M2 M1 0 5 M3 M2 M1 0 PA167 Rozvrhování, H. Rudová: Plánování job-shopu 212 23. května 2023 Disjunkce vybrané při větvení Větvení algoritmu volí disjunkce Předpokládejme větvení Ω = {(i∗, j), (i∗, l)} → výběr (i∗, j) při větvení přidání disjunkce (i∗ , j) → (i∗ , k) pro všechny dosud nenarozvrhované operace (i∗ , k) → výběr (i∗, l) při větvení přidání disjunkce (i∗ , l) → (i∗ , k) pro všechny dosud nenarozvrhované operace (i∗ , k) Důsledek: každý uzel stromu je charakterizován množinou D vybraných disjukcí PA167 Rozvrhování, H. Rudová: Plánování job-shopu 213 23. května 2023 Výpočet dolní hranice Předpokládejme uzel V s vybranými disjukcemi D Jednoduchá dolní hranice spočítej kritickou cestu v G(D ) dolní hranice LB(V ) Vylepšená dolní hranice uvažuj stroj i povolíme překrývání operací na všech strojích kromě i vyřeš problém na stroji i PA167 Rozvrhování, H. Rudová: Plánování job-shopu 214 23. května 2023 Podproblém: 1|rj|Lmax Vypočítej nejdřívější startovní čas rij všech operací (i, j) na stroji i nejdelší cesta ze zdroje v G(D ) Vypočítej minimální množství času ∆ij mezi: startem operace (i, j) (tj. rij ) a koncem rozvrhu (nejdelší cesta v G(D ) z uzlu do stoku) Získáme termíny dokončení dij = LB(V ) − ∆ij + pij time p LB(V)dij ij ij Vyřeš výsledný problém: 1|rj |Lmax viz dříve PA167 Rozvrhování, H. Rudová: Plánování job-shopu 215 23. května 2023 Vylepšená dolní hranice Vyřeš 1|rj |Lmax pro všechny stroje Výsledek: L1, . . . , Lm LBnew (V ) = LB(V ) + max i=1...m Li tj. výsledné řešení nemůže mít lepší kvalitu než nejlepší možné řešení pro každý stroj zvlášť, a proto zahrneme do dolní hranice nejhorší (největší) spočítané zpoždění Poznámky: 1|rj |Lmax je NP-úplný problém experimentální výsledky přesto ukazují, že se vyplatí řešit m NP-úplných problémů pro každý uzel stromu 20 × 20 instance jsou už obtížně řešitelné metodou větví a mezí PA167 Rozvrhování, H. Rudová: Plánování job-shopu 216 23. května 2023 Příklad: dolní hranice Částečný rozvrh: 5 M3 M2 M1 0 Odpovídající graf: hrany G(D’) pár disjuktivních dosud nevybraných hran 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V vybrané disjunktivní hrany konjuktivní hrany PA167 Rozvrhování, H. Rudová: Plánování job-shopu 217 23. května 2023 Příklad: dolní hranice Graf G(D ) s dobami provádění: 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 4 2 142 3 3 1 LB(V ) = l(U, (1, 2), (1, 3), (3, 3), V ) = 8 Data pro úlohy na stroji M1: modrá zelená červená r12 = 0 r13 = 3 r11 = 6 ∆12 = 8 ∆13 = 5 ∆11 = 1 d12 = 3 d13 = 7 d11 = 8 (víme: dij = LB(V ) − ∆ij + pij ) Optimální řešení: Lmax = 0, LBnew (V ) = 8 0 3 7 8 M1 PA167 Rozvrhování, H. Rudová: Plánování job-shopu 218 23. května 2023 Příklad: dolní hranice Změna p11 z 1 na 2: 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 4 2 142 3 3 2 LB(V ) = l(U, (1, 2), (1, 3), (3, 3), V ) = l(U, (3, 1), (2, 1), (1, 1), V ) = 8 Data pro úlohy na stroji M1: modrá zelená červená r12 = 0 r13 = 3 r11 = 6 ∆12 = 8 ∆13 = 5 ∆11 = 2 d12 = 3 d13 = 7 d11 = 8 Optimální řešení: Lmax = 1, LBnew (V ) = 9 0 3 7 M1 9 PA167 Rozvrhování, H. Rudová: Plánování job-shopu 219 23. května 2023 Posunování kritického místa (shifting bottleneck) Úspěšná heuristika při řešení problému minimalizace makespan pro job shop Základní popis iterativní heuristika v každé iteraci je určen rozvrh pro jeden další stroj používána re-optimalizace pro změnu už narozvrhovaných strojů Rozšiřitelnost: metoda lze rozšířít na obecnější job shop problémy další objektivní funkce flexible flow shop (paralelní stroj místo samostatných strojů) nastavovací doba stroje PA167 Rozvrhování, H. Rudová: Plánování job-shopu 220 23. května 2023 Princip algoritmu Značení M je množina všech strojů Dáno určen rozvrh pro podmnožinu M0 ⊂ M strojů tj. je určen výběr disjunktivních hran Akce při jedné iteraci 1 výběr stroje k, pro který ještě neexistuje rozvrh tj. stroj z M\M0 2 určení rozvrhu (výběru disjunktivních hran) pro stroj k na základě daných (zafixovaných) rozvrhů pro stroje z M0 3 nové rozvrhování (= přeplánování) všech strojů z M0 na základě ostatních daných (zafixovaných) rozvrhů, tj. přeplánujeme jeden stroj po druhém PA167 Rozvrhování, H. Rudová: Plánování job-shopu 221 23. května 2023 Princip výběru stroje a určení jeho rozvrhu Myšlenka: výběr ještě nerozvrženého stroje, který působí nejvíce problémů, tzv. kritický (bottleneck) stroj Realizace: spočítej pro každou operaci na nenarozvrhovaném stroji nejdřívější možný startovní čas a minimální zdržení mezi koncem operace a koncem úplného rozvrhu založeného na zafixovaných rozvrzích strojů v M0 a pořadí úloh spočítej pro každý nenarozvrhovaný stroj rozvrh respektující tyto nejdřívější termíny dostupnosti a zdržení vyber stroj s maximálním koncovým časem a zafixuj rozvrh na tomto stroji PA167 Rozvrhování, H. Rudová: Plánování job-shopu 222 23. května 2023 Princip přeplánování strojů Myšlenka: snaha redukovat makespan rozvrhu pro stroje v M0 Popis: uvažuj stroje z M0 jeden po druhém smaž rozvrh vybraného stroje a spočítej nový rozvrh na základě nejdřívějšího startovního času a zdržení vyplývající z ostatních strojů v M0 a pořadí úloh PA167 Rozvrhování, H. Rudová: Plánování job-shopu 223 23. května 2023 Plánování job-shopu: shrnutí Modelování a reprezentace disjunktivní grafová reprezentace matematické programování a job shop (+ řešení) Řešení metoda větví a mezí pro job shop heuristika: posunování kritického místa PA167 Rozvrhování, H. Rudová: Plánování job-shopu 224 23. května 2023 Rozvrhování montážních systémů PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 31 Montážní linka s flexibilním časem 32 Montážní linka s fixním časem Montážní linka Job shop každá úloha má jednoznačnou identitu výroba na objednávku, malý objem výroby potenciálně komplikovaná cesta systémem velmi obtížný problém Montážní linka (flexible assembly system) limitovaný počet odlišných typů výrobků specifikováno vyráběné množství každého typu systém pro manipulaci s materiálem startovní čas úlohy je funkcí času dokončení na předchozím stroji limitovaný počet úloh čekajících ve frontě mezi stroji masová produkce ještě obtížnější problém PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 226 23. května 2023 Montážní linka s flexibilním časem (unpaced assembly system) Několik strojů zapojených sériově (flow system) Flexibilní čas stroj může strávit tolik času na úloze, kolik je třeba Blokování následující stroj je plný a úloha na něj nemůže být přesunuta Fronty mezi stroji? bez újmy na obecnosti lze uvažovat fronty nulové délky frontu délky n lze simulovat n stroji, na kterých je doba provádění úlohy nulová ⇒ budeme uvažovat fronty nulové délky Limitovaný počet odlišných typů výrobků Specifikováno vyráběné množství každého typu Cíl: maximalizace výkonu výkon opět definován kritickým strojem PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 227 23. května 2023 Příklad: výroba kopírek Různé typy kopírek montované na jedné lince Odlišné modely mají obvykle společný základ Odlišnost v rámci komponent automatický podavač ano/ne, rozdílné optiky, . . . Odlišnost typů vede k odlišným dobám výroby na jednotlivých strojích PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 228 23. května 2023 Cyklické rozvrhy Rozvrhy jsou často cyklické nebo periodické daná množina úloh rozvrhována v určitém pořadí jsou obsaženy všechny typy výrobků některé typy zde mohou být vícekrát druhá identická množina rozvrhována, atd. Nevhodné pokud jsou dlouhé nastavovací doby pak se vyplatí dlouhé běhy výrobku jednoho typu Praktické pokud nevýznamná nastavovací doba nízké skladovací náklady snadné na implementaci nicméně: acyklický rozvrh může dávat maximální výkon V praxi cyklické rozvrhy s malými odchylkami závislými na aktuálních objednávkách PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 229 23. května 2023 Minimální podílová množina (minimum part set) Předpokládejme l typů výrobků Nk požadovaný počet výrobků typu k z největší společný dělitel Potom N∗ = N1 z , . . . , Nl z je nejmenší množina se „správnými” proporcemi minimální podílová množina (MPS, minimum part set) Uvažujme úlohy v MPS jako n úloh: n = 1 z l k=1 Nk pij jako dříve cyklický rozvrh je rozvrh určen seřazením úloh v MPS maximalizace výkonu = minimalizace doby cyklu PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 230 23. května 2023 Příklad: MPS Systém se 4 stroji Tři odlišné typy výrobku, které musí být vyráběny ve stejném množství, tj. N∗ = (1, 1, 1) Doby provádění Úlohy 1 2 3 p1j 0 1 0 p2j 0 0 0 ← fronta mezi strojem 1 a 3 p3j 1 0 1 p4j 1 1 0 PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 231 23. května 2023 Příklad: posloupnost v MPS 1,2,3 Úlohy 1 2 3 p1j 0 1 0 p2j 0 0 0 p3j 1 0 1 p4j 1 1 0 1 1 3 3 1 1 1 1 1 3 3 1 1 1 32 2 2 2 22 2 0 1 2 3 5 4 6 7 doba cyklu=3 1 2 3 4 stroje 8 PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 232 23. května 2023 Příklad: posloupnost v MPS 1,3,2 Úlohy 1 2 3 p1j 0 1 0 p2j 0 0 0 p3j 1 0 1 p4j 1 1 0 1 1 12 2 2 3 3 2 1 1 2 1 3 1 3 2 1 0 1 2 4 5 6 doba cyklu=2 3 4 stroje 2 1 3 PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 233 23. května 2023 Minimalizace doby cyklu Heuristika padnoucího profilu (profile fitting heuristic, PF) Vyber první úlohu j1 výběr libovolné úlohy nebo výběr úlohy s nejdelší celkovou dobou provádění Úloha generuje profil Xi,j1 = i h=1 ph,j1 předpokládáme, že úloha j1 poběží bez blokování ⇒ Xi,j1 čas odchodu: čas, kdy úloha j1 opustí stroj i PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 234 23. května 2023 PF: určení následující úlohy Spočítej pro každou možnou úlohu dobu, kterou stroje čekají dobu, kdy je úloha blokována spočítej čas odchodu pro kandidáta na druhou pozici (j2), např. pro úlohu c (j1: úloha na první pozici) X1,j2 = max(X1,j1 + p1c, X2,j1 ) Xi,j2 = max(Xi−1,j2 + pic, Xi+1,j1 ) i = 2, . . . , m − 1 Xm,j2 = Xm−1,j2 + pmc PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 235 23. května 2023 PF: určení následující úlohy Spočítej pro každou možnou úlohu dobu, kterou stroje čekají dobu, kdy je úloha blokována spočítej čas odchodu pro kandidáta na druhou pozici (j2), např. pro úlohu c X1,j2 = max(X1,j1 + p1c, X2,j1 ) Xi,j2 = max(Xi−1,j2 + pic, Xi+1,j1 ) i = 2, . . . , m − 1 Xm,j2 = Xm−1,j2 + pmc neproduktivní doba na stroji i, pokud je c na druhé pozici: Xi,j2 − Xi,j1 − pic celková neproduktivní doba (přes všechny stroje) pro c: m i=1 (Xi,j2 − Xi,j1 − pic) úloha s nejmenší neproduktivní dobou vybrána na druhou pozici (pro další pozice opakuj totéž) ... myšlenka padnoucího profilu PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 236 23. května 2023 Diskuse PF heuristika se chová v praxi dobře stále platí, že při použití heuristiky PF nehrají roli nastavovací doby Zjemnění: neproduktivní doby nejsou stejně špatné na všech strojích uvažuj kritický stroj použití vah v součtu PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 237 23. května 2023 Montážní linka s fixním časem Popis modelu transportér, který se posunuje konstantní rychlostí výrobky, které se vyrábí se posunují mezi stroji pevnou rychlostí jednotková doba cyklu: určena jako doba mezi dvěma po sobě jdoucími úlohami na lince každý stroj má danou kapacitu a omezení cíl: uspořádat úlohy tak, aby nebyly stroje přetíženy a byla minimalizována cena za nastavení Příklad: výroba automobilu rozdílné modely vyráběné na stejné lince auta mají odlišné barvy a vybavení vyráběná auta uspořádána tak, aby byla minimalizována cena za nastavení a stroje na lince byly rovnoměrně vytíženy PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 238 23. května 2023 Skupiny a distribuce Atributy a charakteristiky každé úlohy barva, vybavení, . . . Cena za změny při výrobě vytváření skupin výrobků, které mají vybrané atributy stejné např. barva auta Časově náročné operace distribuuj úlohy, které obsahují tyto operace operace omezující kapacitu (index kritičnosti) operace s vyšším indexem jsou kritičtější např. instalace posuvné střechy př. čtyřikrát časově náročnější, 10% aut má posuvnou střechu, tj. index kritičnosti = 4/10 sekce linky pro instalaci posuvné střechy musí být vytížena alespoň čtyřikrát méně než sekce pro automobily bez posuvné střechy, jinak nebude dostatek času na instalaci posuvné střechy PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 239 23. května 2023 Kritéria Minimalizace celkové ceny na nastavení Splnění termínů dokončení pro výrobky na objednávku celkové nezáporné vážené zpoždění opakování: Tj = max(Cj − dj , 0) Distribuce operací omezujících kapacitu ψi (l) značí penalizaci, pokud stroj musí vyrábět dva výrobky, které jsou l pozic od sebe Pravidelné tempo spotřeby materiálu PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 240 23. května 2023 Heuristika seskupování a distribuce (grouping and spacing) 1 Urči celkový počet úloh, které mají být rozvrhovány vyšší počet úloh na rozvrhování umožní nižší cenu, ale snadněji dojde k narušení rozvrhu typicky jeden den až týden 2 Seskup úlohy obsahující operace s vysokými cenami za nastavení 3 Uspořádej skupiny podle nastavovacích cen a termínů objednávky 4 Distribuuj úlohy v rámci skupiny tak, aby byly brány v úvahu operace omezující kapacitu nejkritičtější operace distribuovány co nejlépe co nejdříve a zohledni přitom termíny objednávky PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 241 23. května 2023 Jednoduchý matematický model 1 stroj, n úloh Každá úloha: pj = 1, dj (mohou být nekonečné), wj , b atributů aj1, . . . , ajb 1. atribut reprezentuje barvu 2. atribut je 1, pokud má úloha posuvnou střechu, jinak je 0 . . . Jestliže úloha j následována úlohou k a aj1 = ak1, pak je nutná cena na nastavení cjk cjk je funkcí aj1 a ak1 Jestliže aj2 = ak2 = 1, pak je nutná penalizace ψ2(l) pokud jsou úlohy j a k od sebe vzdáleny l pozic Jestliže je úloha dokončena po termínu dokončení, uvažujeme vážené nezáporné zpoždění Cíl: minimalizovat celkovou cenu včetně ceny za nastavení ceny za distribuci ceny za zpoždění PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 242 23. května 2023 Příklad: heuristika seskupování a distribuce (zadání) 1 stroj, 10 úloh, pj = 1 Atributy úlohy j: aj1 a aj2 Cena za nastavení s využitím aj1 pro úlohu j: dvě po sobě jdoucí úlohy mají aj1 = ak1, pak cjk = |aj1 − ak1| aj2 = ak2 = 1 a mezi j a k je (l − 1) úloh, pak ψ2(l) = max(3 − l, 0) úlohy těsně po sobě (0 = l − 1), pak je penalizace max(3 − 1, 0) = 2 jedna úloha mezi nimi (1 = l − 1), pak je penalizace max(3 − 2, 0) = 1 více než jedna úloha mezi nimi (s), pak je penalizace max(3 − s, 0) = 0 Některé úlohy mají konečné termíny dokončení, pokud překročeny, pak wj Tj brána v úvahu Úlohy 1 2 3 4 5 6 7 8 9 10 aj1 1 1 1 3 3 3 5 5 5 5 aj2 0 1 1 0 1 1 1 0 0 0 dj ∞ 2 ∞ ∞ ∞ ∞ 6 ∞ ∞ ∞ wj 0 4 0 0 0 0 4 0 0 0 PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 243 23. května 2023 Příklad: heuristika seskupování a distribuce (řešení) 3 skupiny dle aj1 Skupina A: úlohy 1,2,3 skupina B: úlohy 4,5,6 skupina C: úlohy 7,8,9,10 Nejlepší pořadí skupin vzhledem k ceně za nastavení A, B, C nebo C, B, A Ale úloha 7 nebo 2 by nebyla dokončena včas a cena za zpoždění vysoká ⇒ výběr pořadí A, C, B Úlohy s atributem 2 nutno distribuovat, optimální posloupnosti minimalizující penalizaci ψ2 A: 2,1,3 atributy 1 0 1 C: 8,7,9,10 atributy 0 1 0 0 B: 5,4,6 atributy 1 0 1 cena 3 (první-třetí=1, třetí-pátý=1, osmý-desátý=1) Celková cena: 6+3+0=9 (cena za nastavení+cena za distribuci+cena za zpoždění) PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 244 23. května 2023 Shrnutí Montážní linka s flexibilním časem př. výroba kopírek cyklické rozvrhy heuristika padnoucího profilu PF Montážní linka s fixním časem př. výroba automobilů heuristika seskupování a distribuce PA167 Rozvrhování, H. Rudová: Rozvrhování montážních systémů 245 23. května 2023 Rezervace PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 33 Úvod 34 Intervalové rozvrhování 35 Rezervační systém s rezervou Rezervační systém m strojů zapojených paralelně n úloh s dobou provádění p1, . . . , pn termíny dostupnosti r1, . . . , rn termíny dokončení d1, . . . , dn váhy w1, . . . , wn Úloha musí být prováděna v rámci daného časového intervalu termín dostupnosti a dokončení nelze porušit Nemusí být možné realizovat všechny úlohy Cíl: vyber podmnožinu úloh, pro kterou existuje konzistentní rozvrh která maximalizuje danou objektivní funkci maximalizace počtu prováděných úloh maximalizace celkového množství provádění maximalizace profitu realizovaných úloh (zadané váhy) PA167 Rozvrhování, H. Rudová: Rezervace 247 23. května 2023 Základní modely Systém bez rezervy úlohy trvají od termínu dostupnosti do termínu dokončení, tj. pj = dj − rj mluvíme o pevných intervalech nebo o intervalovém rozvrhování Systémy s rezervou interval mezi termínem dostupnosti a dokončení může mít nějakou rezervu, tj. pj ≤ dj − rj PA167 Rozvrhování, H. Rudová: Rezervace 248 23. května 2023 Aplikace rezervačních systémů Pronájem aut čtyři typy aut: subcompact, střední velikost, plná velikost, sportovní typ pevné množství každého typu stroj = typ auta úloha = zákazník požadující auto zákazník může požadovat určitý(é) typ(y) auta úloha může být prováděna na podmnožině strojů v případě nedostatku některého typu auta může být nabídnut v některých případech silnější typ auta Rezervace pokojů v hotelu Rezervace strojů v továrně PA167 Rozvrhování, H. Rudová: Rezervace 249 23. května 2023 Intervalové rozvrhování m strojů zapojených paralelně n úloh, pro úlohu j zadán termín dostupnosti rj termín dokončení dj doba provádění pj = dj − rj množina Mj strojů, na kterých může být úloha j prováděna wij : profit z provádění úlohy j na stroji i Cíl: maximalizovat profit z prováděných úloh wij = 1: maximalizovat počet realizovaných úloh wij = wj : maximalizovat vážený počet realizovaných úloh PA167 Rozvrhování, H. Rudová: Rezervace 250 23. května 2023 Formulace celočíselného programování Časové periody 1, . . . , H Jl : množina úloh, která potřebuje provádění v čase l (známe předem!) xij = 1 pokud je úloha j prováděna na stroji i xij = 0 jinak Maximalizace m i=1 n j=1 wij xij za předpokladu: úloha běží nejvýše na jednom stroji m i=1 xij ≤ 1 j = 1, . . . , n v každém čase běží na každém stroji nejvýše jedna úloha j∈Jl xij ≤ 1 i = 1, . . . , m l = 1, . . . , H provádění úlohy j na stroji i: xij ∈ {0, 1} PA167 Rozvrhování, H. Rudová: Rezervace 251 23. května 2023 Jednotková doba trvání Každá úloha je dostupná přesně 1 časovou jednotku Co z toho plyne? Problém lze rozdělit na nezavislé problémy víme přesně, které úlohy i jsou prováděny v každé časové jednotce jeden podproblém pro každou časovou jednotku Výsledný problém pro časovou jednotku l: Maximalizace m i=1 n j=1 wij xij za předpokladu m i=1 xij ≤ 1 j = 1, . . . , n j∈Jl xij ≤ 1 i = 1, . . . , m xij ∈ {0, 1} Jedná se o problém přiřazení (assignment problem) problém řešitelný v polynomiálním čase PA167 Rozvrhování, H. Rudová: Rezervace 252 23. května 2023 Jednotková váha & identické stroje wij = 1; Mj = {1, . . . , m} pro všechna i, j; obecná pj tedy stroje jsou identické a cíl je maximalizovat počet realizovaných úloh nejednotková pj , nelze tedy řešit rozkladem v čase Algoritmus dávající optimální řešení Předpokládejme: r1 ≤ · · · ≤ rn J = ∅ (J je množina už vybraných úloh pro provádění) for j = 1 to n do if existuje stroj dostupný v čase rj then přiřaď j tomuto stroji J := J ∪ {j} else urči úlohu j∗ takovou, že Cj∗ = maxk∈J Ck = maxk∈J (rk + pk ) if Cj = rj + pj > Cj∗ then nezařazuj j do J else přiřaď j stroji j∗ (nová úloha skončí dříve nebo zároveň) J := J ∪ {j}\{j∗ } PA167 Rozvrhování, H. Rudová: Rezervace 253 23. května 2023 Příklad: jednotková váha & identické stroje 2 stroje a 8 úloh: j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Iterace 1: j = 1 1 1050 M2 M1 Iterace 2: j = 2 2 1 1050 M2 M1 Iterace 3: j = 3, j∗ = 1 3 2 1050 M2 M1 Iterace 4: j = 4 4 3 2 1050 M2 M1 PA167 Rozvrhování, H. Rudová: Rezervace 254 23. května 2023 Příklad: jednotková váha & identické stroje 2 stroje a 8 úloh: j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Iterace 5: j = 5 5 4 3 2 1050 M2 M1 Iterace 6: j = 6, j∗ = 4 6 53 2 1050 M2 M1 Iterace 7: j = 7 7 6 53 2 1050 M2 M1 Iterace 8: j = 8, j∗ = 7 8 6 53 2 1050 M2 M1 PA167 Rozvrhování, H. Rudová: Rezervace 255 23. května 2023 Nelimitovaný počet identických strojů Všechny úlohy musí být realizovány tj. váha úloh nehraje roli Cíl: použít minimální počet strojů Algoritmus dávající optimální řešení Předpokladejme: r1 ≤ · · · ≤ rn M = ∅ (M množina použitých strojů) i := 0 for j = 1 to n do if stroj z M je volný v rj then přiřaď j na volný stroj else i := i + 1 M := M ∪ {i} přiřaď úlohu j na stroj i PA167 Rozvrhování, H. Rudová: Rezervace 256 23. května 2023 Příklad: nelimitovaný počet identických strojů j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 1 1050 M3 M2 M1 2 1 1050 M3 M2 M1 3 2 1 1050 M3 M2 M1 PA167 Rozvrhování, H. Rudová: Rezervace 257 23. května 2023 Příklad: nelimitovaný počet identických strojů j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 4 3 2 1 1050 M3 M2 M1 5 4 3 2 1 1050 M3 M2 M1 6 6 5 4 3 2 1 1050 M3 M2 M1 PA167 Rozvrhování, H. Rudová: Rezervace 258 23. května 2023 Příklad: nelimitovaný počet identických strojů j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 7 6 6 5 4 3 2 1 1050 M3 M2 M1 8M4 7 6 6 5 4 3 2 1 1050 M3 M2 M1 PA167 Rozvrhování, H. Rudová: Rezervace 259 23. května 2023 Barvení grafu Problém barvení grafu Je možné obarvit vrcholy grafu s použitím n barev tak, aby žádné dva sousední vrcholy nebyly obarveny stejnou barvou? Chromatické číslo grafu Minimální počet barev n nutný k obarvení grafu tak, by žádné dva sousední vrcholy nebyly obarveny stejnou barvou. NP-úplný problém PA167 Rozvrhování, H. Rudová: Rezervace 260 23. května 2023 Reformulace na problém barvení grafu Problém s nelimitovaným počtem identických strojů lze reformulovat na problém barvení grafu vrchol = úloha hrana (j, k) znamená, že se úlohy j a k překrývají v čase každá barva odpovídá jednomu stroji přiřaď barvu (tj. stroj) každému vrcholu tak, že dva sousední vrcholy (překrývají se v čase) mají různou barvu (tj. stroje) Poznámky: obecný problém existence obarvení grafu m barvami je NP-úplný uvažovaný rezervační problém je speciálním (jednodušším) případem problému barvení grafu PA167 Rozvrhování, H. Rudová: Rezervace 261 23. května 2023 Příklad: reformulace j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Odpovídající řešení problému barvení grafu: 6 5 4 3 2 1 8 7 PA167 Rozvrhování, H. Rudová: Rezervace 262 23. května 2023 Rezervační systém s rezervou Rezervační systém s rezervou: pj ≤ dj − rj Triviální případ doby provádění = 1, identické váhy, identické stroje řešení opět dekompozicí v čase Maximalizace váženého počtu aktivit NP-těžký problém ⇒ řešení heuristikami kompozitní řídící pravidlo předzpracování: určení flexibility úloh a strojů algoritmus: nejméně flexibilní úloha na nejméně flexibilním stroji první PA167 Rozvrhování, H. Rudová: Rezervace 263 23. května 2023 Předzpracování ψit: počet úloh, které mohou být přiřazeny na stroj i během intervalu [t − 1, t] možné využití stroje i v čase t čím vyšší hodnota, tím je zdroj i v tomto čase flexibilnější |Mj |: počet strojů, které mohou být přiřazeny úloze j čím vyšší hodnota, tím je úloha j flexibilnější PA167 Rozvrhování, H. Rudová: Rezervace 264 23. května 2023 Prioritní indexy Prioritní index pro úlohu j: Ij = f (wj /pj , |Mj |) uspořádání úloh podle: I1 ≤ I2 ≤ · · · ≤ In čím menší je |Mj |, tím nižší je Ij čím vyšší je wj /pj , tím nižší je Ij snažíme se dát přednost kratším úlohám, protože maximalizujeme počet vážených provedených aktivit a delší úlohy jsou náročnější např. Ij = |Mj | wj /pj Prioritní index pro stroj vybírá stroj pro úlohu jestliže úloha potřebuje stroj v [t, t + pj ] pak výběr stroje i záleží na funkci s faktory ψi,t+1, . . . , ψi,t+pj , tj. na g(ψi,t+1, . . . , ψi,t+pj ) např. g(ψi,t+1, . . . , ψi,t+pj ) = pj l=1 ψi,t+l /pj nebo g(ψi,t+1, . . . , ψi,t+pj ) = max(ψi,t+1, . . . , ψi,t+pj ) PA167 Rozvrhování, H. Rudová: Rezervace 265 23. května 2023 Algoritmus maximalizace váženého počtu aktivit 1 j = 1 2 Vyber úlohu j s nejnižším Ij a vyber mezi stroji a dostupnými časy zdroj a čas s nejnižší g(ψi,t+1, . . . , ψi,t+pj ) Zruš úlohu j jestliže nemůže být přiřazena ani jednomu stroji v žádném čase 3 Jestliže j = n STOP jinak nastav j = j + 1 a běž na krok 2 PA167 Rozvrhování, H. Rudová: Rezervace 266 23. května 2023 Cvičení: maximalizace váženého počtu aktivit Nalezněte rozvrh pro daný problém Úlohy 1 2 3 4 5 6 7 pj 3 10 9 4 6 5 3 wj 2 3 3 2 1 2 3 rj 5 0 2 3 2 4 5 dj 12 10 20 15 18 19 14 Mj {1, 3} {1, 2} {1, 2, 3} {2, 3} {1} {1} {1, 2} pro Ij = |Mj | wj /pj a g(ψi,t+1, . . . , ψi,t+pj ) = pj l=1 ψi,t+l /pj Řešení: Úlohy 7 6 1 4 5 2 Stroje 2 1 3 3 1 2 Časy 11-14 14-19 5-8 11-15 2-8 0-10 úlohu 3 nelze umístit PA167 Rozvrhování, H. Rudová: Rezervace 267 23. května 2023 Shrnutí Rezervace Intervalové rozvrhování (rezervační systém bez rezervy) celočíselné programování jednotková doba trvání: formulace problému přiřazení (řešení pro každou čas. jednotku zvlášť) jednotková váha & identické stroje (maximalizace počtu provedených aktivit) nelimitovaný počet identických strojů Rezervační systém s rezervou kompozitní řídící pravidlo PA167 Rozvrhování, H. Rudová: Rezervace 268 23. května 2023 Rozvrhování jako timetabling PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 36 Úvod 37 Rozvrhování s operátory 38 Rozvrhování s pracovní sílou Rozvrhování = timetabling Doposud: rozvrhování = scheduling Nyní: rozvrhování = timetabling důraz kladen na časové umístění objektů vazby na časové uspořádání mezi objekty hrají malou roli Omezení operátorů/nástrojů (operator/tool) mnoho operátorů úloha potřebuje jeden nebo více odlišných operátorů úlohy vyžadující stejné operátory nemohou běžet zároveň možné cíle: rozvržení všech úloh v rámci časového horizontu H nebo minimalizace makespan Omezení pracovní síly R identických pracovníků = jeden zdroj kapacity R každá úloha potřebuje několik pracovníků celkový počet pracovníků nesmí být nikdy překročen PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 270 23. května 2023 Rozvrhování jako problém plánování projektu s omezenými zdroji Problém plánování projektu s omezenými zdroji resource-constrained project scheduling problem (RCPSP) n úloh N zdrojů Ri kapacita zdroje i pj doba provádění úlohy j Rij požadavek úlohy j na zdroj i Precj (přímí) předchůdci úlohy j Rozvrhování s operátory Ri = 1 pro všechna i = 1 . . . N Rozvrhování s pracovní sílou N = 1 Oba problémy rozvrhování stále velmi obtížné i při pj = 1 NP-těžké operátoři ≡ barvení grafu pracovní síla ≡ bin-packing PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 271 23. května 2023 Rozvrhování s operátory jako barvení grafu Omezíme se na problém s jednotkovou dobou trvání Úloha = uzel Úlohy potřebují stejného operátora = hrana mezi uzly Přiřazení barev (= času) uzlům sousední uzly musí mít různé barvy tj. úlohy se stejným operátorem musí být prováděny v různých časech Problém existence řešení tj. zadán časový horizont H a hledám rozvrh v rámci horizontu může být graf obarven H barvami? Optimalizační problém tj. minimalizace makespan jaký nejmenší počet barev je třeba? chromatické číslo grafu PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 272 23. května 2023 Heuristiky pro barvení grafu Stupeň uzlu počet hran spojených s uzlem Úroveň saturace počet různých barev spojených s uzlem Intuice obarvi uzly s vyšším stupněm dříve obarvi uzly s vyšší úrovní saturace dříve Algoritmus 1 uspořádej uzly v klesajícím pořadí podle jejich stupně 2 použij barvu 1 pro první uzel 3 vyber neobarvený uzel s maximální úrovní saturace v případě volby z nich vyber uzel s maximálním stupněm v neobarveném podgrafu 4 obarvi vybraný uzel s nejmenší možnou barvou 5 jestliže jsou všechny uzly obarveny STOP jinak běž na krok 3 PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 273 23. května 2023 Příklad: rozvrhování schůzek Vytvoř rozvrh pro 5 schůzek se 4 lidmi schůzka = úloha, člověk = operátor všechny schůzky trvají jednu hodinu 1 2 3 4 5 Joe 1 1 0 1 1 Lisa 1 1 1 0 0 Jane 1 0 1 0 0 Larry 0 1 0 1 1 2 1 5 3 4 stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 Můžeme vybrat buď úlohu 1 nebo úlohu 2 Např. vybereme 1 a obarvíme barvou 1 PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 274 23. května 2023 Příklad: rozvrhování schůzek (dokončení) 5 1 3 2 4 Úroveň saturace = 1 pro všechny úlohy Vyber 2 vzhledem k nejvyššímu stupni stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 Úroveň saturace = 2 pro všechny uzly Vyber 4 vzhledem k nejvyššímu stupni stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 Úroveň saturace = 2 pro uzel 3 Úroveň saturace = 3 pro uzel 5 Vyber 5 na obarvení stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 V posledním kroku obarvi 3 stejnou barvou jako 4 ⇒celkem 4 barvy, tj. makespan=4 stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 275 23. května 2023 Příklad: rezervace vs. rozvrhování s operátory Předpokládejme, že máme rezervační systém Úloha 1 2 3 pj 2 3 1 rj 0 2 3 dj 2 5 4 Lze přeformulovat na rozvrhování s operátory Úloha 1 2 3 Operátor 1 1 0 0 Operátor 2 1 0 0 Operátor 3 0 1 0 Operátor 4 0 1 1 Operátor 5 0 1 0 úloha 1 běží v čase [0,2] úloha 2 běží v čase [2,5] úloha 3 běží v čase [3,4] PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 276 23. května 2023 Vztah k rezervačním systémům Rozvrhování s operátory blízké rezervačnímu systému bez rezervy Oba problémy reformulovány na problém barvení grafu rezervace: hrana = dvě úlohy se překrývají v čase rozvrhování: hrana = dvě úlohy požadují stejného operátora Rozdíl ve složitosti rezervace: překrývající se časové jednotky jdou po sobě rozvrhování: úlohy často nevyžadují pouze sousední operátory ⇒ rozvrhování s operátory je obtížnější problém PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 277 23. května 2023 Rozvrhování s pracovní sílou: aplikace Řízení projektu ve stavebním průmyslu dodavatel má realizovat n aktivit doba trvání aktivity j je pj aktivita j požaduje pracovní skupinu velikosti Wj precedenční omezení na aktivity dodavatel má W pracovníků cíl: dokončit všechny aktivity v minimálním čase Rozvrhování zkoušek všechny zkoušky mají stejnou dobu trvání všechny zkoušky jsou v místnosti s W sedadly počet studentů předmětu j, kteří skládají zkoušku, je Wj několik zkoušek může být narozvrhováno ve stejné místnosti, pokud je postačující počet sedadel cíl: zkonstruovat rozvrh tak, že jsou všechny zkoušky narozvrhovány v minimálním čase PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 278 23. května 2023 Reformulace pomocí problému plnění košů (bin-packing) Problém plnění košů každý koš má kapacitu W předměty velikosti Wj cíl: naplnit minimální počet košů Uvažujme speciální problém rozvrhování s pracovní silou předpokládejme jednotkovou dobu trvání nelimitovaný počet strojů minimalizace makespan Rozvrhování s pracovní silou jako problém plnění košů předmět = úloha (s počtem pracovníků Wj ) kapacita koše = celkový počet pracovníků W 1 koš = 1 časová jednotka minimalizace počtu košů = minimalizace makespan Řešení problému plnění košů NP-těžký problém vyvinuta řada heuristik heuristika prvního padnoucího (first fit FF) koše víme, že: Cmax (FF) ≤ 17 10 Cmax (OPT) + 2 PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 279 23. května 2023 Příklad: heuristika prvního padnoucího koše (FF) Předpokládejme 18 úloh a W =2100 úloha 1-6 požaduje 301 jednotek zdroje úloha 7-12 požaduje 701 jednotek zdroje úloha 13-18 požaduje 1051 jednotek zdroje FF heuristika: přiřadíme prvních 6 úloh na jeden zdroj (301×6=1806) pak přiřadíme vždy dvě úlohy na další tři zdroje (701×2=1402) pak přiřadíme právě jednu úlohu na každý zdroj Velmi nekvalitní řešení vzhledem k uspořádání úloh PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 280 23. května 2023 Heuristika prvního padnoucí koše se zmenšováním úloh Zlepšení FF heuristiky Uspořádání úloh od nejdelší k nejkratší První padnoucí koš se zmenšováním úloh (first fit decreasing FFD) Řešení příkladu: seřadíme úlohy dle požadovaných jednotek zdroje, tj. 13,14,15,16,17,18,7,8,9,10,11,12,1,2,3,4,5,6 úlohy bereme postupně a dáváme je na první zdroj, kam se vejdou 13 dáme na zdroj 1, 14 dáme na zdroj 2, ..., 18 dáme na zdroj 6 7 dáme na zdroj 1, 8 dáme na zdroj 2, ..., 12 dáme na zdroj 6 1 dáme na zdroj 1, 2 dáme na zdroj 2, ..., 6 dáme na zdroj 6 Víme, že Cmax (FFD) ≤ 11 9 Cmax (OPT) + 4 FF i FFD mohou být rozšířeny o různé termíny dostupnosti PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 281 23. května 2023 Diskuse Uvažovali jsme reprezentanty různých problémů V praxi obecnější problémy (kombinace všech uvažovaných rysů problémů zároveň) dynamické rezervační problémy uvažování ceny (management zisku) přerušení aktivit . . . PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 282 23. května 2023 Shrnutí Rezervace Intervalové rozvrhování (rezervační systém bez rezervy) celočíselné programování jednotková doba trvání: formulace problému přiřazení (řešení pro každou čas. jednotku zvlášť) jednotková váha & identické stroje (maximalizace počtu provedených aktivit) jednotková váha & nelimitovaný počet identických strojů Rezervační systém s rezervou kompozitní řídící pravidlo Timetabling plánování projektu s omezenými zdroji (RCPSP) rozvrhování s operátory a barvení grafu heuristika pro barvení grafu rozvrhování s pracovní silou a problém plnění košů heuristika prvního padnoucího koše heuristika prvního padnoucího koše se zmenšováním úloh PA167 Rozvrhování, H. Rudová: Rozvrhování jako timetabling 283 23. května 2023 Rozvrhování předmětů na univerzitě PA167 Rozvrhování, Hana Rudová FI MU 23. května 2023 39 Popis problému 40 Iniciální tvorba rozvrhu 41 Interaktivní rozvrhování Rozvrhování předmětů na univerzitě Typy problémů rozvrhování se studijními obory (curriculum-based timetabling) curriculum (studijní obor): množina předmětů každý studen je zapsán do (jednoho nebo více) curricula cíl: rozvrhování všech předmětů curricula bez překrývání typické také pro rozvrhování na střední škole rozvrhování se zápisy studentů (enrollment-based timetabling) každý student je individuálně zapsán/zaregistrován do nějaké množiny předmětů studentský konflikt: student není schopen absolvovat (dva) zaregistrované předměty vzhledem k jejich překryvu cíl: nalezení rozvrhu, který minimalizuje počet studenských konfliktů př. rozvrhování na FI dělení studentů na skupiny (student sectioning/student scheduling) dělení studentů na skupiny pro velké předměty, kde je nutné několik seminárních nebo přednáškových skupin Iniciální tvorba rozvrhu (vytvoření rozvrhu ze začátku) vs. Interaktivní rozvrhování: změny vytvořeného rozvrhu PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 285 23. května 2023 Rozvrhovací systém UniTime http://www.unitime.org Vyvinutý na Purdue University (USA) ve spolupráci s FI MU a MFF UK Komplexní systém pro univerzitní rozvrhování rozvrhování předmětů se studijními obory i i se zápisy dělení studentů na skupiny iniciální tvorba rozvrhu, interaktivní rozvrhování rozvrhování studentů, zkoušek, událostí otevřený zdrojový kód webové rozhraní, Java, SQL+hibernate, XML Použití používáno pro rozvrhování na Purdue University 70 různých problemů, celkem asi 40 000 studentů Masarykova univerzita: používáno na téměř všech fakultách např. MIT, USA, Lahore University of Management Sciences, Pakistán, University of Zagreb, Chorvatsko, AGH University of Science and Technology, Polsko, Antalya International University, Turecko, Universidad de Ingeniería y Tecnología (UTEC), Peru, American College of Middle East (ACM), Kuwait PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 286 23. května 2023 Literatura Materiál k přednášce přehledová práce – rozvrhování na Purdue University H. Rudová, T. Müller, K. Murray, Complex university course timetabling. Journal of Scheduling, 14(2): 187-207, Springer, 2011. http://dx.doi.org/10.1007/s10479-010-0828-5 Další materiály http://www.unitime.org/publications.php rozvrhování na Filozofické fakultě MU H. Rudová and T. Müller, Rapid Development of University Course Timetables (extended abstract). Proceedings of the 5th Multidisciplinary International Scheduling Conference (MISTA 2011), pages 649–652. 2011 http://www.fi.muni.cz/~hanka/publ/mista11.pdf rozvrhování na Pedagogické fakultě MU a FSpS T. Müller, H. Rudová, Real-life Curriculum-based Timetabling with Elective Courses and Course Sections. Annals of Operations Research, 239(1):153-170, Springer, 2016. http://dx.doi.org/10.1007/s10479-014-1643-1 PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 287 23. května 2023 Struktura předmětu s jeho třídami (vyučovanými částmi) PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 288 23. května 2023 Typická omezení Pevná Měkká omezení omezení Časy pro třídy∗ časové vzory (pro pravidelné časy) x individuální časy x x Místnosti pro třídy individuální budovy/místnosti x x individuální vybavení místnosti x x Omezení místnosti x na zdroje vyučující x Studenti konflikty mezi dvěma třídami x časové závislosti mezi třídami x x Distribuční časové precedence mezi třídami x x omezení třídy rozvrhované v podobných časech x x mezi třídami stejný nebo odlišný den/čas/místnost výuky pro třídy x x ∗Třída je každá rozvrhovaná položka předmětu (přednáška, cvičení, ...) PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 289 23. května 2023 Omezení a účelové funkce Pevné podmínky musí být splněny Měkké podmínky nemusí být splněny, pokud je to nutné Měkké podmínky v rozvrhování: přehled studentské konflikty měkká omezení na čas měkká omezení na místností měkké distribuční podmínky Vážený problém splňování podmínek (weighted CSP, WCSP) P zahrnuje pevné a měkké podmínky cíl: minimalizace F jako součtu vah nesplněných měkkých podmínek PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 290 23. května 2023 Iterativní dopředné prohledávání (Iterative Forward Search, IFS) pro WCSP P: WCSP, F: účelová funkce, <: komparátor 1: function IFS(P, F, <) 2: i = 0 3: ω = ∅ (současné přiřazení/rozvrh) 4: σ = ∅ (nejlepší přiřazení/rozvrh) 5: while canContinue(ω, i) do 6: i = i + 1 7: v = selectVariable(P, ω) (v reprezentuje třídu) 8: d = selectValue(P, ω, F, <, v) (d reprezentuje umístění v rozvrhu) 9: γ = hardConflicts(P, ω, v/d) (předměty, které musím odpřiřadit) 10: ω = ω\γ ∪ {v/d} 11: if F(ω) < F(σ) then σ = ω 12: end while 13: return σ 14: end function Poznámka: není používána žádná propagace omezení proměnná má buď přiřazenu iniciální hodnotu nebo má plnou iniciální doménu PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 291 23. května 2023 Funkce v IFS Nalezení konfliktních proměnných γ = hardConflicts (P, ω, v/d) vypočítá množinu proměnných γ takovou, že ω\γ ∪ {v/d} neporuší žádnou pevnou podmínku lze aplikovat jednoduchý algoritmus – vyšší počet iterací je lepší než sofistikovány algoritmus Výběr proměnné selectVariable(P, ω) nevýznamný – chyby mohou být odstraněny budoucími iteracemi aplikováno náhodné uspořádání Výběr hodnoty selectValue(P, ω, F, <, v) velmi důležitý pro minimalizaci porušení měkkých podmínek: výběr hodnoty d proměnné v s minimálním zhoršením ∆F(ω, v/d) hodnoty účelové funkce s ohledem na měkká omezení ∆F(ω, v/d) = F(ω ∪ {v/d}) − F(ω) (výpočet inkrementální) pro minimalizaci porušení pevných podmínek: konfliktní statistika PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 292 23. května 2023 Konfliktní statistika pro třídu CS 101 Lab 2 PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 293 23. května 2023 Konfliktní statistika Předpoklad: při výběru hodnoty a proměnné A je nutné zrušit přiřazení hodnoty b proměnné B, tj. [A = a → ¬ B = b] V průběhu výpočtu si tedy lze pamatovat: A = a ⇒ 3׬ B = b, 4׬ B = c, 1׬ C = a, 120׬ D = a Při výběru hodnoty výběr hodnoty s nejnižším počtem konfliktů váženým jejich frekvencí konflikt započítáme pouze, pokud to vede k odstranění přiřazení př. A = a ⇒ 3 × ¬ B = b, 90 × ¬ B = c, 1 × ¬ C = a, 120 × ¬ D = a A = b ⇒ 1 × ¬ B = a, 3 × ¬ B = b, 2 × ¬ C = a za předpokladu, že máme přiřazení B = c, C = a, D = b nechť A/a vede ke konfliktu s B/c: vyhodnoceno jako 90 není konflikt s C/a, tak se nezapočítává nechť A/b vede ke konfliktu s C/a: vyhodnoceno jako 2 tj. vybereme hodnotu b pro proměnnou A PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 294 23. května 2023 Konfliktní statistika II. CBS[x = dx → ¬ y = dy ] = cxy : při přiřazení x = dx bylo nutné zrušit přiřazení y = dy v minulosti cxy-krát Jestliže je hodnota d vybrána pro proměnnou v v IFS, potom hardConflicts(P, ω, v/d) vypočítá přiřazení γ = {v1/d1, v2/d2, . . . vn/dn}, které musí být zrušeno, aby byla vynucena konzistence nového částečného přiřazení Jako důsledek jsou navýšeny čítače CBS[v = d → ¬ v1 = d1], CBS[v = d → ¬ v2 = d2], ..., CBS[v = d → ¬ vn = dn] . Konfliktní statistika je používána jako heuristika pro výběr hodnoty Evaluace hodnoty d proměnné v: vi /di ∈ω ∧ vi /di ∈hardConflicts(P,ω,v/d) CBS[v = d → ¬vi = di ] tj. konflikt započítáme pouze tehdy, pokud to vede k odstranění přiřazení PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 295 23. května 2023 Interaktivní rozvrhování: návrhy Uvažovány změny s třídou PSY 120 Lec 5 PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 296 23. května 2023 Opravná verze metody větví a mezí (Repair-based BB) Algoritmus n nejlepších návrhů ω je vráceno uživateli prohledávání s časovým limitem hodnoty s nejlepší ∆F(ω, v/d) prozkoumávány nejdříve konfliktní statistika není brána v úvahu vzhledem k výpočetní náročnosti Meze omezená hloubka prohledávání abychom umožnili pouze malý počet změn proměnných pro zahrnutí změny na jedné třídě nemá smysl měnit příliš mnoho dalších tříd M: maximální hloubka hodnota účelové funkce F musí být lepší než n-tý nejlepší návrh Ω[n]: n-tý nejlepší návrh Opakování RepairBB: provádění nového RepairBB se zvětšenou hloubkou prohledávání a/nebo zvětšeným časovým limitem PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 297 23. května 2023 Opravná verze metody větví a mezí P: WCSP ω: současné přiřazení vbb: proměnná (třída), která bude přiřazována 1: function RepairBB(P, ω, vbb) 2: if {vbb/d} ⊆ ω then ω = ω\{vbb/d} 3: else d = nil 4: γ = {vbb/d} 5: return backtrack(P, ω, ∅, γ, ∅, 0) 6: end function backtrack(P, ω, µ, γ, Ω, m) µ: nově vybrané přiřazení aktuálním prohledáváním do hloubky γ: proměnné (s případným původním přiřazením), pro které hledáme přiřazení Ω: návrhy (několik dosud nejlepších nalezených přiřazení) m: aktuální hloubka prohledávání PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 298 23. května 2023 Funkce backtrack 1: function backtrack(P, ω, µ, γ, Ω, m) 2: if γ + m > M then return ∅ (M je maximální hloubka) 3: if γ = ∅ then return ω (konflikty vyřešeny) 4: if timeout then return ∅ 5: if LowerBound(F(ω ∪ γ)) ≥ F(Ω[n]) then return ∅ (odhad kvality nového přiřazení (po zahrnutí γ) je horší než n-tý návrh) 6: v = selectVariableBB(γ) (je vybrána některá nepřiřazená proměnná) 7: let v/do ∈ γ (d0 je původní hodnota proměnné v) 8: for d ∈ Dv ordered by ∆F(ω, v/d) do 9: if d = do then continue (je vybrána původní hodnota) 10: α = hardConflicts(P, ω, v/d) 11: if α ∩ µ = ∅ then continue (konflikt s už vybraným přiřazením) 12: Ω = Ω ∪ backtrack(P, ω ∪ {v/d}, µ ∪ {v/d}, γ\{v/do} ∪ α, Ω, m + 1) 13: end for 14: return Ω 15: end function PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 299 23. května 2023 UniTime.org: GUI s vygenerovaným rozvrhem PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 300 23. května 2023 Fakulta informatiky MU Jaro 2014 Podzim 2014 Místnosti 14+5 14+6 Vyučující 197 231 Předměty 190 199 Třídy 500 604 Registrace 12 701+ 14 055+ Registrace + obory 17 599 20 670 Konflikty dop.průchody 4x Konflikty 958 1 440 Preference na čas 75,89 % 78,2 % + odstraněny registrace cca 25 studentů s více než 20 předměty PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 301 23. května 2023 International Timetabling Competition 2019 Mezinárodní soutěž, kterou organizovala i FI MU https://www.itc2019.org rozvrhování univerzitních předmětů Vychází z reálných problémů shromážděných v systému UniTime řešení problémů z celého světa včetně rozvrhování FI MU anonymizovaná data málo významné charakteristiky problémů odstraněny snaha soustředit se na důležité rysy problému Průběh soutěže 3 × 10 datových sad publikováno během soutěžního období dostupný validátor řešení – založený na řešiči UniTime submitování validních řešení přes web soutěže Výsledky zahrnuty tři problémy z FI MU vítězný řešič časově náročný (výsledky po 24 hodinách i déle) matheuristika: matematické programování kombinované s heuristikami řešič založený na UniTime druhý nejlepší schopný produkovat výsledky v krátkém čase (hodina až dvě) PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 302 23. května 2023 Rozvrhování předmětů na univerzitě: shrnutí Typy řešených problémů studijní obory, zápisy, dělení na skupiny iniciální vs. interaktivní rozvrhování UniTime Model problému struktura předmětu omezení a účelové funkce Prohledávání iterativní dopředné prohledávání konfliktní statistika opravná verze metody větví a mezí PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 303 23. května 2023 Zdroje, ze kterých průsvitky čerpají V průsvitkách jsou použity obrázky a texty z uvedených zdrojů Michael Pinedo, Planning and Scheduling in Manufacturing and Services. Springer, 2005. Erwin Hans, Johann Hurink, Production Planning. Přednáška na University of Twente, Nizozemí. http://www.stern.nyu.edu/om/faculty/pinedo/book2/dowload.html Sanja Petrovič, Automated Scheduling. Přednáška na University of Nottingham, UK. Sigurdur Olafsson, Production Scheduling. Přednáška na Iowa State University, USA, http://www.stern.nyu.edu/om/faculty/pinedo/book2/dowload.html Roman Barták, Plánování a rozvrhování. Přednáška na MFF UK, http://kti.ms.mff.cuni.cz/~bartak/planovani/prednaska.html Thom Frühwirth and Slim Abdennadher. Essentials of Constraint Programming, Springer Verlag, 2003. http://www.informatik.uni-ulm.de/pm/fileadmin/pm/home/fruehwirth/pisa/ Hana Rudová, Tomáš Müller and Keith Murray, Complex university course timetabling. Journal of Scheduling, 14(2): 187-207, Springer, 2011. http://dx.doi.org/10.1007/s10951-010-0171-3 IBM ILOG CP optimizer for scheduling, Philippe Laborie et al., Constraints, 23(2):210-250, 2018 https://link.springer.com/article/10.1007/s10601-018-9281-x PA167 Rozvrhování, H. Rudová: Rozvrhování předmětů na univerzitě 304 23. května 2023