PA167 Rozvrhování 16. května 2022 Hodnocení Závěrečná písemná práce: 80 bodů minimální počet bodů za zkoušku: 40 bodů otázky z několika různých oblastí předmětu příklady: zadán problém, případně i metoda, cílem výpočet rozvrhu; srovnávací, algoritmus, pojmy cca 7 příkladů vzorové zadání písemné práce na webu předmětu Vnitrosemestrální písemná práce: 28.3.2022 20 bodů minimální počet bodů za vnitrosemestrální práci: 8 bodů Bonusové body: až 1 bod za aktivní účast na přednáčce odpovědi/zápojení do diskuse/otázky studentů Hodnocení: A 90 a více, B 80-89, C 70-79, D 60-69, E 50-59 Hana Rudová, FI MU: PA167 Rozvrhování 2 16. května 2022 Základní informace Web předmětu: interaktivní osnova na IS MU průsvitky + 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á, FI MU: PA167 Rozvrhování 3 16. května 2022 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á, FI MU: PA167 Rozvrhování 4 16. května 2022 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á, FI MU: PA167 Rozvrhování 5 16. května 2022 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á, FI MU: PA167 Rozvrhování 6 16. května 2022 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á, FI MU: PA167 Rozvrhování 7 16. května 2022 Úvod do rozvrhování 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 9 16. května 2022 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í Hana Rudová, FI MU: Úvod do rozvrhování 10 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 11 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 12 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 13 16. května 2022 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) Hana Rudová, FI MU: Úvod do rozvrhování 14 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 15 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 16 16. května 2022 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í Hana Rudová, FI MU: Úvod do rozvrhování 17 16. května 2022 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ů Hana Rudová, FI MU: Úvod do rozvrhování 18 16. května 2022 Ú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 Hana Rudová, FI MU: Úvod do rozvrhování 19 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 20 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 21 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 22 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 23 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 24 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 25 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 26 16. května 2022 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á ... Hana Rudová, FI MU: Úvod do rozvrhování 27 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 28 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 29 16. května 2022 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í Hana Rudová, FI MU: Úvod do rozvrhování 30 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 31 16. května 2022 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ě Hana Rudová, FI MU: Úvod do rozvrhování 32 16. května 2022 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? Hana Rudová, FI MU: Úvod do rozvrhování 33 16. května 2022 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 Hana Rudová, FI MU: Úvod do rozvrhování 34 16. května 2022 Řídící pravidla 16. května 2022 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 Hana Rudová, FI MU: Řídící pravidla 36 16. května 2022 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 Hana Rudová, FI MU: Řídící pravidla 37 16. května 2022 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í Hana Rudová, FI MU: Řídící pravidla 38 16. května 2022 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 Hana Rudová, FI MU: Řídící pravidla 39 16. května 2022 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í Hana Rudová, FI MU: Řídící pravidla 40 16. května 2022 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) Hana Rudová, FI MU: Řídící pravidla 41 16. května 2022 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 Hana Rudová, FI MU: Řídící pravidla 42 16. května 2022 Ří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ů) Hana Rudová, FI MU: Řídící pravidla 43 16. května 2022 Lokální prohledávání 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 45 16. května 2022 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. Hana Rudová, FI MU: Lokální prohledávání 46 16. května 2022 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) Hana Rudová, FI MU: Lokální prohledávání 47 16. května 2022 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í Hana Rudová, FI MU: Lokální prohledávání 48 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 49 16. května 2022 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é Hana Rudová, FI MU: Lokální prohledávání 50 16. května 2022 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) Hana Rudová, FI MU: Lokální prohledávání 51 16. května 2022 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. Hana Rudová, FI MU: Lokální prohledávání 52 16. května 2022 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) Hana Rudová, FI MU: Lokální prohledávání 53 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 54 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 55 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 56 16. května 2022 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) Hana Rudová, FI MU: Lokální prohledávání 57 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 58 16. května 2022 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 t0 > 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(S k )−F(Snew ) t pak Sk+1 = Snew jinak Sk+1 = Sk 3 tk = α(tk ) k = k + 1 jestliže platí podmínka ukončení pak konec jinak běž na krok 2. Hana Rudová, FI MU: Lokální prohledávání 59 16. května 2022 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, . . . Hana Rudová, FI MU: Lokální prohledávání 60 16. května 2022 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 . . . Hana Rudová, FI MU: Lokální prohledávání 61 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 62 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 63 16. května 2022 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í Hana Rudová, FI MU: Lokální prohledávání 64 16. května 2022 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í Hana Rudová, FI MU: Lokální prohledávání 65 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 66 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 67 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 68 16. května 2022 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. Hana Rudová, FI MU: Lokální prohledávání 69 16. května 2022 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í Hana Rudová, FI MU: Lokální prohledávání 70 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 71 16. května 2022 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 Hana Rudová, FI MU: Lokální prohledávání 72 16. května 2022 Matematické programování 16. května 2022 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 PřF:M0160 Optimalizace ESF:BKM_OPRO Optimalizace a rozhodování Hana Rudová, FI MU: Matematické programování 74 16. května 2022 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 Hana Rudová, FI MU: Matematické programování 75 16. května 2022 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 Hana Rudová, FI MU: Matematické programování 76 16. května 2022 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ů Hana Rudová, FI MU: Matematické programování 77 16. května 2022 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ší Hana Rudová, FI MU: Matematické programování 78 16. května 2022 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)Hana Rudová, FI MU: Matematické programování 79 16. května 2022 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 Hana Rudová, FI MU: Matematické programování 80 16. května 2022 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 ) 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é Hana Rudová, FI MU: Matematické programování 81 16. května 2022 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) Hana Rudová, FI MU: Matematické programování 82 16. května 2022 Omezující podmínky (pokračování) 16. května 2022 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 Prohledávání/přiřazování Konzistenční techniky jsou (obvykle) neúplné ⇒ potřeba prohledávací algoritmus, který vyřeší "zbytek" př. X in 1..2, Y in 1..2, Z in 1..2, X=Y, Y=Z, X=Z AC neodstraní žádnou hodnotu ale problem je nekonzistentní 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 X in 1..5 ≡ X=1 ∨ X=2 ∨ X=3 ∨ X=4 ∨ X=5 Obecně: prohledávací algoritmus řeší zbylé disjunkce X=1 ∨ X=1 standardní přiřazování X<3 ∨ X≥3 dělení domén 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 Hana Rudová, FI MU: Omezující podmínky (pokračování) 96 16. května 2022 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) Hana Rudová, FI MU: Omezující podmínky (pokračování) 97 16. května 2022 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 Hana Rudová, FI MU: Omezující podmínky (pokračování) 98 16. května 2022 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} Hana Rudová, FI MU: Omezující podmínky (pokračování) 99 16. května 2022 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 Hana Rudová, FI MU: Omezující podmínky (pokračování) 100 16. května 2022 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ěží Hana Rudová, FI MU: Omezující podmínky (pokračování) 101 16. května 2022 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) Hana Rudová, FI MU: Omezující podmínky (pokračování) 102 16. května 2022 Podmínka tabulky: př. s odvozovacími pravidly Počáteční stav Některé pozice zakázány vzhledem ke kapacitě zdroje Nový stav Hana Rudová, FI MU: Omezující podmínky (pokračování) 103 16. května 2022 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 Hana Rudová, FI MU: Omezující podmínky (pokračování) 104 16. května 2022 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? Hana Rudová, FI MU: Omezující podmínky (pokračování) 105 16. května 2022 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í Hana Rudová, FI MU: Omezující podmínky (pokračování) 106 16. května 2022 Cvičení: podmínka tabulky Hana Rudová, FI MU: Omezující podmínky (pokračování) 107 16. května 2022 Cvičení: podmínka tabulky Hana Rudová, FI MU: Omezující podmínky (pokračování) 108 16. května 2022 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 Hana Rudová, FI MU: Omezující podmínky (pokračování) 109 16. května 2022 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 Hana Rudová, FI MU: Omezující podmínky (pokračování) 110 16. května 2022 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} Hana Rudová, FI MU: Omezující podmínky (pokračování) 111 16. května 2022 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; Hana Rudová, FI MU: Omezující podmínky (pokračování) 112 16. května 2022 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í Hana Rudová, FI MU: Omezující podmínky (pokračování) 113 16. května 2022 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]) Hana Rudová, FI MU: Omezující podmínky (pokračování) 114 16. května 2022 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á Hana Rudová, FI MU: Omezující podmínky (pokračování) 115 16. května 2022 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; Hana Rudová, FI MU: Omezující podmínky (pokračování) 116 16. května 2022 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 Hana Rudová, FI MU: Omezující podmínky (pokračování) 117 16. května 2022 Způsoby větvení 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ší např. proměnné s nejmenší doménou: doména se snadněji vyprázdní nebo proměnné s nejvíce podmínkami: pro proměnné s více podmínkami je obecně obtížnější nalézt hodnotu proměnné definuje tvar prohledávacího stromu výběr proměnné s malou velikostí domény: malé větvení na této úrovni výběr proměnné s velkou velikostí domény: velké větvení na této úrovni Jaká hodnota má být vyzkoušena první? princip prvotního úspěchu (succeed-first) preferuj hodnoty, které nejspíše patří do řešení např. hodnoty s nejvíce podporami v okolních proměnných tato heuristika je obvykle problémově závislá definuje pořadí procházení větví Hana Rudová, FI MU: Omezující podmínky (pokračování) 118 16. května 2022 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í? Hana Rudová, FI MU: Omezující podmínky (pokračování) 119 16. května 2022 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 Hana Rudová, FI MU: Plánování projektu 148 16. května 2022 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 Hana Rudová, FI MU: Plánování projektu 149 16. května 2022 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 Hana Rudová, FI MU: Plánování projektu 150 16. května 2022 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 Hana Rudová, FI MU: Plánování projektu 151 16. května 2022 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 Hana Rudová, FI MU: Plánování projektu 152 16. května 2022 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 Hana Rudová, FI MU: Plánování projektu 153 16. května 2022 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 Hana Rudová, FI MU: Plánování projektu 154 16. května 2022 Plánování úloh (na jednom stroji) 16. května 2022 23 Řídící pravidla 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í Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 156 16. května 2022 Ří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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 157 16. května 2022 Ří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á Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 158 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 159 16. května 2022 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ý? Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 160 16. května 2022 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í? Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 161 16. května 2022 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í Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 162 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 163 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 164 16. května 2022 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í) Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 165 16. května 2022 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) Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 166 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 167 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 168 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 169 16. května 2022 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ší Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 170 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 171 16. května 2022 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,*,* Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 172 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 173 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 174 16. května 2022 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) Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 175 16. května 2022 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 Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 176 16. května 2022 Plánování job-shopu 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 178 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 179 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 180 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 181 16. května 2022 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) Hana Rudová, FI MU: Plánování job-shopu 182 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 183 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 184 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 185 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 186 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 187 16. května 2022 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) Hana Rudová, FI MU: Plánování job-shopu 188 16. května 2022 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 zdržení 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 Hana Rudová, FI MU: Plánování job-shopu 189 16. května 2022 Příklad: aktivní vs. neaktivní rozvrh Neaktivní rozvrh: 105 M3 M2 M1 0 15 20 Aktivní rozvrh: 105 M3 M2 M1 0 15 20 Hana Rudová, FI MU: Plánování job-shopu 190 16. května 2022 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 Ω Hana Rudová, FI MU: Plánování job-shopu 191 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 192 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 193 16. května 2022 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í Hana Rudová, FI MU: Plánování job-shopu 194 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 195 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 196 16. května 2022 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í Hana Rudová, FI MU: Plánování job-shopu 197 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 198 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 199 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 200 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 201 16. května 2022 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í) strojů z M0 na základě ostatních daných (zafixovaných) rozvrhů Hana Rudová, FI MU: Plánování job-shopu 202 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 203 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 204 16. května 2022 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 Hana Rudová, FI MU: Plánování job-shopu 205 16. května 2022 Rozvrhování montážních systémů 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 207 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 208 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 209 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 210 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 211 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 212 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 213 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 214 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 215 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 216 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 217 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 218 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 219 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 220 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 221 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 222 16. května 2022 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í Hana Rudová, FI MU: Rozvrhování montážních systémů 223 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 224 16. května 2022 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í) Hana Rudová, FI MU: Rozvrhování montážních systémů 225 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 226 16. května 2022 Rezervace 16. května 2022 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) Hana Rudová, FI MU: Rezervace 228 16. května 2022 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 Hana Rudová, FI MU: Rezervace 229 16. května 2022 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ě Hana Rudová, FI MU: Rezervace 230 16. května 2022 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 Hana Rudová, FI MU: Rezervace 231 16. května 2022 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} Hana Rudová, FI MU: Rezervace 232 16. května 2022 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 Hana Rudová, FI MU: Rezervace 233 16. května 2022 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∗ J := J ∪ {j}\{j∗ } Hana Rudová, FI MU: Rezervace 234 16. května 2022 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 Hana Rudová, FI MU: Rezervace 235 16. května 2022 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 Hana Rudová, FI MU: Rezervace 236 16. května 2022 Jednotková váha a nelimitovaný počet identických strojů wij = 1 pro všechna i, j Všechny úlohy musí být realizovány 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 Hana Rudová, FI MU: Rezervace 237 16. května 2022 Příklad: jednotková váha a 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 Hana Rudová, FI MU: Rezervace 238 16. května 2022 Příklad: jednotková váha a 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 Hana Rudová, FI MU: Rezervace 239 16. května 2022 Příklad: jednotková váha a 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 Hana Rudová, FI MU: Rezervace 240 16. května 2022 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 Hana Rudová, FI MU: Rezervace 241 16. května 2022 Reformulace na problém barvení grafu Problém s jednotkovou vahou a 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 heuristiky diskutovány v kapitole o timetabling Hana Rudová, FI MU: Rezervace 242 16. května 2022 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: 3 2                         ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ 8 7 ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ 6 5 ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ 1 4 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ © © © © © © © © © © © © © © © © © © © © © © © © ©                                           !!!"""### $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ( ( ( ( ( ( ( ( Hana Rudová, FI MU: Rezervace 243 16. května 2022 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í Hana Rudová, FI MU: Rezervace 244 16. května 2022 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ší Hana Rudová, FI MU: Rezervace 245 16. května 2022 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 ) Hana Rudová, FI MU: Rezervace 246 16. května 2022 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 Hana Rudová, FI MU: Rezervace 247 16. května 2022 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 Hana Rudová, FI MU: Rezervace 248 16. května 2022 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 Hana Rudová, FI MU: Rezervace 249 16. května 2022 Rozvrhování jako timetabling 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 251 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 252 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 253 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 254 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 255 16. května 2022 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                                     ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ 5 1 3 2 4 Úroveň saturace = 2 pro všechny uzly Vyber 4 vzhledem k nejvyššímu stupni                                     ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ 5 1 3 2 4 Úroveň saturace = 2 pro uzel 3 Úroveň saturace = 3 pro uzel 5 Vyber 5 na obarvení                                     ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ 5 1 3 2 4 V posledním kroku obarvi 3 stejnou barvou jako 4 ⇒celkem 4 barvy, tj. makespan=4 Hana Rudová, FI MU: Rozvrhování jako timetabling 256 16. května 2022 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] Hana Rudová, FI MU: Rozvrhování jako timetabling 257 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 258 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 259 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 260 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 261 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 262 16. května 2022 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 . . . Hana Rudová, FI MU: Rozvrhování jako timetabling 263 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování jako timetabling 264 16. května 2022 Rozvrhování předmětů na univerzitě 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 266 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 267 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 268 16. května 2022 Struktura předmětu s jeho třídami (vyučovanými částmi) Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 269 16. května 2022 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í, ...) Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 270 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 271 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 272 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 273 16. května 2022 Konfliktní statistika pro třídu CS 101 Lab 2 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 274 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 275 16. května 2022 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í Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 276 16. května 2022 Interaktivní rozvrhování: návrhy Uvažovány změny s třídou PSY 120 Lec 5 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 277 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 278 16. května 2022 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í Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 279 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 280 16. května 2022 UniTime.org: GUI s vygenerovaným rozvrhem Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 281 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 282 16. května 2022 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ě) Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 283 16. května 2022 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í Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 284 16. května 2022 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 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 285 16. května 2022