PA167 Rozvrhování 13. května 2021 Hodnocení Ústní/písemná zkouška: 80 bodů minimální počet bodů za zkoušku: 40 bodů otázky z několika různých oblastí předmětu zkoušené znalosti budou vyžadovat porozumění, orientaci a přehled v problematice Domácí úkoly: 20 bodů 2x úkol za 10 bodů minimální počet bodů za domácí úkoly: 8 bodů úkoly zadány na přednášce a mailem, řešení do přednášky za dva týdny postup řešení musí být součástí odevzdaného úkolu Bonusové body: až 2 body za aktivní účast na 1 videokonferenci reakce na předem připravené i další dotazy na videokonferenci diskuse/otázky studentů na videokonferenci 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 13. května 2021 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 13. května 2021 Literatura Michael Pinedo: Planning and Scheduling in Manufacturing and Services, Springer, 2005. 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, 2008 (2012). Hana Rudová, FI MU: PA167 Rozvrhování 4 13. května 2021 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 13. května 2021 Předběžný přehled přednášky (I. část) Úvod Příklady rozvrhování v průmyslu a ve službách Grahamova klasifikace rozvrhovacích problémů Obecné řešící metody Přesné řešící metody metoda větví a mezí Heuristiky řídící pravidla (dispatching rules) paprskové prohledávání (beam search) lokální prohledávání: simulované žíhání, tabu prohledávání, genetické algoritmy Matematické programování: formulace lineární, celočíselné Programování s omezujícími podmínkami Hana Rudová, FI MU: PA167 Rozvrhování 6 13. května 2021 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. Rozvrhování zaměstnanců: rozvrhování volných dnů, rozvrhování směn, cyklické rozvrhování směn. Univerzitní rozvrhování: teorie a praxe (rozvrhování na Masarykově univerzitě) Hana Rudová, FI MU: PA167 Rozvrhování 7 13. května 2021 Úvod do rozvrhování 13. května 2021 1 Terminologie 2 Klasifikace rozvrhovacích problémů 3 Složitost 4 Reálné problémy 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 13. května 2021 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 13. května 2021 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 13. května 2021 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í 12 13. května 2021 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í 13 13. května 2021 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í 14 13. května 2021 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í 15 13. května 2021 Ú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í 16 13. května 2021 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í 17 13. května 2021 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í 18 13. května 2021 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í 19 13. května 2021 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í 20 13. května 2021 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í 21 13. května 2021 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í 22 13. května 2021 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 plnění limonád do lahví problém obchodního cestujícího 1|sjk |Cmax Hana Rudová, FI MU: Úvod do rozvrhování 23 13. května 2021 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í 24 13. května 2021 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í 25 13. května 2021 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í 26 13. května 2021 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í 27 13. května 2021 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í 28 13. května 2021 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í 29 13. května 2021 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í 30 13. května 2021 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í 31 13. května 2021 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í 32 13. května 2021 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 Z Google OR-Tools https://developers.google.com/optimization/routing/vrp Hana Rudová, FI MU: Úvod do rozvrhování 33 13. května 2021 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í 34 13. května 2021 Řídící pravidla 13. května 2021 5 Ří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 13. května 2021 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 13. května 2021 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 13. května 2021 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 13. května 2021 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 13. května 2021 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 13. května 2021 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 13. května 2021 Ří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 13. května 2021 Matematické programování 13. května 2021 6 Matematické 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 na FI PV027 Optimalizace Hana Rudová, FI MU: Matematické programování 45 13. května 2021 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 Hana Rudová, FI MU: Matematické programování 46 13. května 2021 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í 47 13. května 2021 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í 48 13. května 2021 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í 49 13. května 2021 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 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 ) relaxované lineární programy 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í 50 13. května 2021 Příklad: 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: Matematické programování 51 13. května 2021 Příklad: 1| | n j=1 wjCj, 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 běží právě jedna úloha: n j=1 t−1 s=max(t−pj ,0) xjs = 1 ∀t Hana Rudová, FI MU: Matematické programování 52 13. května 2021 Lokální prohledávání 13. května 2021 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í 54 13. května 2021 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í 55 13. května 2021 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í 56 13. května 2021 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í 57 13. května 2021 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í 58 13. května 2021 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í 59 13. května 2021 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í 60 13. května 2021 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í 61 13. května 2021 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í 62 13. května 2021 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í 63 13. května 2021 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í 64 13. května 2021 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í 65 13. května 2021 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í 66 13. května 2021 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í 67 13. května 2021 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í 68 13. května 2021 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í 69 13. května 2021 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í 70 13. května 2021 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í 71 13. května 2021 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í generaci nejvhodnější jedinci přežijí do další generace Hana Rudová, FI MU: Lokální prohledávání 72 13. května 2021 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 Částečné mapované křížení P1=[1 6 3 4 5 2] P2=[4 3 1 2 6 5] O2=[2 1 3 4 5 6] O1=[3 5 1 2 6 4] bod rezu 1 bod rezu 2 Konstrukce O1: 126 dám místo 345, 3 dám tam, kde byla 1; 4 dám tam, kde byla 2; 5 dám tam, kde byla 6 Máme nějaký problém? Jak křížit P1=[12|465|3] P2=[34|216|5] ? Hana Rudová, FI MU: Lokální prohledávání 73 13. května 2021 PMX částečné mapované křížení: příklad 1. Rodič 1: 8 4 7 3 6 2 5 1 9 0 kopírujeme náhodný pás alel Rodič 2: 0 1 2 3 4 5 6 7 8 9 z rodiče 1 potomkovi Potomek 1: ___3 6 2 5 1__ 2. Rodič 1: 8 4 7 3 6 2 5 1 9 0 4 je první hodnotou v pásu rodiče 2, Rodič 2: 0 1 2 3 4 5 6 7 8 9 která není v potomkovi, nalezneme 6 Potomek 1: ___3 6 2 5 1 __ 6 stále v pásu => pokračujeme s 6 3. Rodič 1: 8 4 7 3 6 2 5 1 9 0 6 odpovídá 5, 5 stále v pásu Rodič 2: 0 1 2 3 4 5 6 7 8 9 pokračujeme s 5 Potomek 1: ___3 6 2 5 1 __ 4. Rodič 1: 8 4 7 3 6 2 5 1 9 0 5 odpovídá 2, 2 není v pásu Rodič 2: 0 1 2 3 4 5 6 7 8 9 na pozici 2 dáme 4 (z 2.) Potomek 1: __4 3 6 2 5 1 __ 5. Rodič 1: 8 4 7 3 6 2 5 1 9 0 7 je další hodnota v pásu rodiče 2, Rodič 2: 0 1 2 3 4 5 6 7 8 9 která není v potomkovi, nalezneme 1 Potomek 1: _7 4 3 6 2 5 1 __ 1 není v pásu, na pozici 1 dáme 7 6. Rodič 1: 8 4 7 3 6 2 5 1 9 0 na zbývající pozice potomka Rodič 2: 0 1 2 3 4 5 6 7 8 9 dáme alely z rodiče 2 Potomek 1: 0 7 4 3 6 2 5 1 8 9 Hana Rudová, FI MU: Lokální prohledávání 74 13. května 2021 PMX částečné mapované křížení: algoritmus 1 Náhodně vybereme pás alel z rodiče 1 a okopírujeme ho do potomka 2 V segmentu odpovídajících pozic rodiče 2 vybereme postupně hodnoty, které ještě nebyly zkopírovány do potomka Pro každou z těchto hodnot A: 1 Zapamatujeme si index této hodnoty v rodiči 2. Nalezneme hodnotu V z rodiče 1 na stejné pozici. 2 Nalezneme V u rodiče 2. 3 Pokud patří index hodnoty V v rodiči 2 mezi indexy určující původní pás, pokračujeme krokem 2.1 s použitím této hodnoty. 4 Pokud index hodnoty V není částí původního pásu, přidáme hodnotu A do potomka na této pozici. 3 Zkopírujeme zbývající pozice z rodiče 2 do potomka 2. Rodič 1: 8 4 7 3 6 2 5 1 9 0 4 je první hodnotou v pásu rodiče 2, Rodič 2: 0 1 2 3 4 5 6 7 8 9 která není v potomkovi, nalezneme 6 Potomek 1: ___3 6 2 5 1 __ 6 stále v pásu => pokračujeme s 6 Cvičení: určete potomky pro [12|465|3] a [34|216|5] ... řešení: 324651,542163 Hana Rudová, FI MU: Lokální prohledávání 75 13. května 2021 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í 76 13. května 2021 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ů generace: 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 generace 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í 77 13. května 2021 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é generace přežijí? Elitářský model: nejlepší člen generace je vybrán jako člen následující generace nebo nejlepší potomci a rodiče jsou vybírání do následující generace Hana Rudová, FI MU: Lokální prohledávání 78 13. května 2021 Implementace genetického algoritmu 1 k = 1 vyber N iniciálních rozvrhů S1,1, . . . , S1,N použitím heuristiky vyhodnoť jednotlivce generace 2 vytvoř nové jednotlivce spojením jednotlivců současné generace pomocí křížení a mutace smaž členy existující generace, 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í 79 13. května 2021 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 pro reprodukci je použita párová výměna sousedů vybraných náhodně počet možných potomků: 4 každý vybrán s pravděpodobností 1/4 potomci se mohou reprodukovat jako ostatní jednotlivci populace Iniciální populace: náhodné posloupnosti permutací Hana Rudová, FI MU: Lokální prohledávání 80 13. května 2021 Příklad: genetické algoritmy (řešení) Generace 1 Jedinec 25314 14352 12345 Cena 25 17 16 Vybraný jedinec: 12345 s potomkem 13245, cena 20 Generace 2 Jedinec 13245 14352 12345 Cena 20 17 16 Vybraný jedinec: 12345 s potomkem 12354, cena 17 Generace 3 Jedinec 12354 14352 12345 Cena 17 17 16 Vybraný jedinec: 12345 s potomkem 12435, cena 11 Generace 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í 81 13. května 2021 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í Hana Rudová, FI MU: Lokální prohledávání 82 13. května 2021 Omezující podmínky 13. května 2021 11 Problém splňování podmínek 12 Rozvrhování jako problém splňování podmínek 13 Podmínky pro zdroje 14 Globální omezení 15 Rozvrhovací strategie Omezení (constraint) Dána množina (doménových) proměnných Y = {y1, . . . , yk } konečná množina hodnot (doména) D = D1 ∪ . . . ∪ Dk Omezení c na Y je podmnožina D1 × . . . × Dk omezuje hodnoty, kterých mohou proměnné nabývat současně Příklad: proměnné: A,B domény: {0,1} pro A {1,2} pro B omezení: A=B nebo (A,B) ∈ {(0,1),(0,2),(1,2)} Omezení c definováno na y1, . . . yk je splněno, pokud pro d1 ∈ D1, . . . dk ∈ Dk platí (d1, . . . dk) ∈ c příklad (pokračování): omezení splněno pro (0, 1), (0, 2), (1, 2), není splněno pro (1, 1) Hana Rudová, FI MU: Omezující podmínky 84 13. května 2021 Problém splňování podmínek (CSP) Dána konečná množina proměnných V = {v1, . . . , vn} konečná množina hodnot (doména) D = D1 ∪ . . . ∪ Dn konečná množina omezení C = {c1, . . . , cm} omezení je definováno na podmnožině V Problém splňování podmínek je trojice (V , D, C) (constraint satisfaction problem CSP) Příklad: proměnné: A,B,C domény: {0,1} pro A {1} pro B {0,1,2} pro C omezení: A=B, B=C Řešení CSP přiřazení hodnot všem proměnným, které splňuje všechna omezení (d1, . . . , dn) ∈ D1 × . . . × Dn je řešení (V , D, C) pro každé ci ∈ C na vi1 , . . . vik platí (di1 , . . . dik ) ∈ ci Hana Rudová, FI MU: Omezující podmínky 85 13. května 2021 Filtrace domén Příklad: Da = {1, 2}, Db = {1, 2, 3} a < b ⇒ hodnota 1 může být z Db bezpečně vyřazena Podmínky se používají aktivně pro odstranění nekonzistencí z problému nekonzistence = hodnota, která nemůže být součástí žádného řešení (nesplňuje nějakou podmínku) Tato tzv. filtrace domén je realizována procedurou REVISE, kterou má každá podmínka Hana Rudová, FI MU: Omezující podmínky 86 13. května 2021 Hranová konzistence (arc consistency AC) Říkáme, že podmínka je hranově konzistentní, pokud pro každou hodnotu každé její proměnné existuje kombinace hodnot pro další proměnné v podmínce tak, že je podmínka splněna Říkáme, že hodnota je podporována/má podporu. REVISE procedura pro hranovou konzistenci odstraní z domén proměnných všechny hodnoty, které nemají podporu Příklad: A=B+C je hranově konzistentní pro B,C ∈ {1,2}, A ∈ {2,3,4} (hodnota 3 proměnné A má např. podporu (3,1,2) pro (A,B,C)) A=B je hranově konzistentní pro A ∈ {0,1}, B ∈ {1,2,3} A=B není hranově konzistentní pro A ∈ {1,2,3}, B ∈ {1,2} (hodnota 3 proměnné A není podporována) CSP je hranově konzistentní, pokud jsou všechny podmínky hranově konzistentní. Hana Rudová, FI MU: Omezující podmínky 87 13. května 2021 Zajištění hranové konzistence Jak zařídit hranovou konzistenci v CSP? Každá podmínka musí být zrevidována Příklad: X in 1..6, Y in 1..6, Z in 1..6, X lct(Ω) − est(A) ⇒ ¬A << Ω A(2) C(4) B(5) 6 16 157 4 16 Ω = {B, C} ¬A << Ω ⇒ start(A) ≥ min{ect(B)|B ∈ Ω} A(2) B(5) C(4) 16 157 4 8 16 Hana Rudová, FI MU: Omezující podmínky 104 13. května 2021 Odvozovací pravidla pro ne-první/ne-poslední Ne-první pravidla: (co se stane, pokud aktivita A bude zpracována jako první?) p(Ω ∪ {A}) > lct(Ω) − est(A) ⇒ ¬A << Ω ¬A << Ω ⇒ start(A) ≥ min{ect(B)|B ∈ Ω} Ne-poslední (symetrická) pravidla: (co se stane, pokud aktivita A bude zpracována jako poslední?) p(Ω ∪ {A}) > lct(A) − est(Ω) ⇒ ¬Ω << 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 105 13. května 2021 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 106 13. května 2021 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 107 13. května 2021 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 108 13. května 2021 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 109 13. května 2021 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 110 13. května 2021 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 Jak jsou inicializovány proměnné X(j,t)? Jak se jejich hodnoty mění při použití odvozovacích pravidel podmínky tabulky? Jak by mohly vypadat výsledné rozvrhy po aplikaci pravidel? Hana Rudová, FI MU: Omezující podmínky 111 13. května 2021 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 112 13. května 2021 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 113 13. května 2021 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 114 13. května 2021 Produkovatelné/spotřebovatelné zdroje Zdroj = rezervoár Aktivita konzumuje nějaké množství zdroje cap(A)<0 nebo aktivita produkuje nějaké množství zdroje cap(A)>0 Požadována minimální kapacita zdroje (při konzumaci) a maximální kapacita zdroje nemůže být překročena (produkcí) −1 −1 +1 Kumulativní zdroj může být chápan jako speciální případ rezervoáru každá aktivita konzumuje cap(A) při startu a produkuje cap(A) na konci Hana Rudová, FI MU: Omezující podmínky 115 13. května 2021 Relativní uspořádání Pokud je čas relativní (uspořádání aktivit) potom techniky edge finding a agregovaných požadavků nic neodvodí Pořád ale můžeme používat informace o uspořádání aktivit a spotřebě/produkci daného zdroje Příklad: reservoár: aktivity konzumují a produkují zdroj −1−1−1 +1 lze odvodit nezbytnost přídavné aktivity produkující jednotku zdroje Hana Rudová, FI MU: Omezující podmínky 116 13. května 2021 Optimistický zdrojový profil (orp) Cesta&Stella 1997 orp(A): maximální možná úroveň zdroje v čase, kdy se A začne zpracovávat Aktivity, které musí být před A, se vezmou dohromady s produkčními aktivitami, které mohou být před A orp(A) = InitLevel + cap(A) + B<0 cap(B) Příklad: B??A znamená, že pořadí A a B ještě není známé Hana Rudová, FI MU: Omezující podmínky 117 13. května 2021 orp odvozovací pravidla I. orp(A) < MinLevel ⇒ fail i když je veškerá produkce plánována před A není dosažena minimální požadovaná úroveň zdroje orp(A) = InitLevel + cap(A) + B<0 cap(B) Hana Rudová, FI MU: Omezující podmínky 118 13. května 2021 orp odvozovací pravidla II. orp(A) − cap(D) − D<0 cap(B) < MinLevel ⇒ D << A Uvažujme časový okamžik, kdy začne aktivita A pro libovolné D takové, že D??A a cap(D) > 0: pokud je produkce v D plánována za A a minimální požadovaná úroveň zdroje není dosažena, pak musí být D před A Příklad: Hana Rudová, FI MU: Omezující podmínky 119 13. května 2021 Optimistický zdrojový profil: cvičení orp(A) = InitLevel + cap(A) + B<0 cap(B) orp(A) − cap(D) − D<0 cap(B) < MinLevel ⇒ D << A Máme dány aktivity A, B, C, X, Y , Z a jejich požadované kapacity jsou po řadě 1, 2, 3, 4, 5, −1 Jsou dány precedence: A << B << C, X << Y InitLevel = MinLevel = 0 Jaká je hodnota orp(A)? Může být X naplánováno po A? Co se změní, pokud bychom přidali aktivitu D s následujícími vlastnostmi? cap(D) = −2 D << A Hana Rudová, FI MU: Omezující podmínky 120 13. května 2021 Pesimistický zdrojový profil (prp) Cesta&Stella 1997 prp(A): minimální možná úroveň zdroje v čase, kdy se A začne zpracovávat Aktivity, které musí být před A, se vezmou dohromady s konzumačními aktivitami, které mohou být před A prp(A) = InitLevel + cap(A) + B< MaxLevel ⇒ fail i když je veškerá konzumace plánována před A, maximální povolená kapacita zdroje je překročena InitLevel cap(B): all B with B??A and cap(B)<0 cap(B): all B with B< MaxLevel ⇒ D << A Uvažujme časový okamžik, kdy začne aktivita A: pro libovolné D takové, že D??A a cap(D) < 0: jestliže je konzumace v D plánována po A a je překročena maximální povolená úroveň zdroje, pak musí být D před A Příklad: InitLevel cap(B): all B with B??A and cap(B)<0 cap(B): all B with B< 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 163 13. května 2021 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 164 13. května 2021 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 165 13. května 2021 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 166 13. května 2021 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 167 13. května 2021 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 168 13. května 2021 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 169 13. května 2021 Plánování úloh (na jednom stroji) 13. května 2021 21 Řídící pravidla 22 Metoda větví a mezí 23 Paprskové prohledává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) 171 13. května 2021 Ří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) 172 13. května 2021 Ří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) 173 13. května 2021 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) 174 13. května 2021 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) 175 13. května 2021 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) 176 13. května 2021 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) 177 13. května 2021 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) 178 13. května 2021 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) 179 13. května 2021 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) 180 13. května 2021 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) 181 13. května 2021 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) 182 13. května 2021 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) 183 13. května 2021 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) 184 13. května 2021 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) 185 13. května 2021 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) 186 13. května 2021 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) 187 13. května 2021 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) 188 13. května 2021 Plánování job-shopu 13. května 2021 24 Disjunktivní grafová reprezentace 25 Matematické programování a job shop 26 Metoda větví a mezí pro job shop 27 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 190 13. května 2021 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 191 13. května 2021 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 192 13. května 2021 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 193 13. května 2021 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 194 13. května 2021 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 195 13. května 2021 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 196 13. května 2021 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 197 13. května 2021 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 198 13. května 2021 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 199 13. května 2021 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 200 13. května 2021 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 201 13. května 2021 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 202 13. května 2021 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 203 13. května 2021 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 204 13. května 2021 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 205 13. května 2021 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 206 13. května 2021 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 207 13. května 2021 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 208 13. května 2021 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 209 13. května 2021 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 210 13. května 2021 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 211 13. května 2021 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 212 13. května 2021 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 213 13. května 2021 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 214 13. května 2021 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 215 13. května 2021 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 216 13. května 2021 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 217 13. května 2021 Rozvrhování montážních systémů 13. května 2021 28 Montážní linka s flexibilním časem 29 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ů 219 13. května 2021 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ů 220 13. května 2021 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ů 221 13. května 2021 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ů 222 13. května 2021 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ů 223 13. května 2021 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ů 224 13. května 2021 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 225 13. května 2021 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 1 2 3 4 5 6 7 doba cyklu=2 Hana Rudová, FI MU: Rozvrhování montážních systémů 226 13. května 2021 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ů 227 13. května 2021 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 Hana Rudová, FI MU: Rozvrhování montážních systémů 228 13. května 2021 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ů 229 13. května 2021 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ů 230 13. května 2021 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ů 231 13. května 2021 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ů 232 13. května 2021 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ů 233 13. května 2021 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ů 234 13. května 2021 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ů 235 13. května 2021 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ů 236 13. května 2021 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ů 237 13. května 2021 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ů 238 13. května 2021 Rezervace 13. května 2021 30 Úvod 31 Intervalové rozvrhování 32 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 240 13. května 2021 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 241 13. května 2021 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 242 13. května 2021 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 243 13. května 2021 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 244 13. května 2021 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 245 13. května 2021 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 246 13. května 2021 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 247 13. května 2021 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 248 13. května 2021 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 249 13. května 2021 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 250 13. května 2021 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 251 13. května 2021 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 252 13. května 2021 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 253 13. května 2021 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 254 13. května 2021 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 255 13. května 2021 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 256 13. května 2021 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 257 13. května 2021 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 258 13. května 2021 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 259 13. května 2021 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 260 13. května 2021 Rozvrhování jako timetabling 13. května 2021 33 Úvod 34 Rozvrhování s operátory 35 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 262 13. května 2021 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 263 13. května 2021 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 264 13. května 2021 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 265 13. května 2021 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 266 13. května 2021 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 267 13. května 2021 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 268 13. května 2021 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 269 13. května 2021 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 270 13. května 2021 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 271 13. května 2021 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 272 13. května 2021 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 273 13. května 2021 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 274 13. května 2021 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 275 13. května 2021 Rozvrhování zaměstnanců 13. května 2021 36 Rozvrhování volných dnů 37 Rozvrhování směn 38 Cyklické rozvrhování směn Reálný problém: rozvrhování sester v nemocnici Klasický 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: Rozvrhování zaměstnanců 277 13. května 2021 Rozvrhování zaměstnanců Jedná se o problém přípravy pracovních rozvrhů a přiřazení zaměstnanců na směny tak, aby byly pokryty požadavky na počty zaměstnanců, které se v průběhu času liší Aplikace rozvrhování zdravotních sester v nemocnici rozvrhování telefonních operátorů rozvrhování policejních zaměstnanců rozvrhování v dopravě (posádky letadel, řidiči autobusů) . . . Uvažované problémy rozvrhování volných dnů (základní problém) rozvrhování směn (obecný problém) cyklické rozvrhování směn (speciální případ) Hana Rudová, FI MU: Rozvrhování zaměstnanců 278 13. května 2021 Problém rozvrhování volných dnů Nalezněte minimální počet zaměstnanců R, kteří jsou požadováni na pokrytí 7-denního týdne tak, že platí stanoven požadavek na každý pracovní den nj , j = 1 . . . 7 n1 je neděle, n7 je sobota každý zaměstnanec má k1 volných víkendů z každých k2 víkendů každý zaměstnanec pracuje přesně 5 ze 7 dnů od neděle do soboty každý zaměstnec pracuje nejvýše 6 po sobě jdoucích dnů Hana Rudová, FI MU: Rozvrhování zaměstnanců 279 13. května 2021 Dolní hranice počtu zaměstnanců Omezení víkendu z k2 víkendů každý zaměstnanec pracuje k2 − k1 víkendů n = max(n1, n7) (k2 − k1)R ≥ k2n, tj. R ≥ k2n k2 − k1 Omezení celkového požadavku 5R ≥ 7 j=1 nj , tj. R ≥     1 5 7 j=1 nj     Maximální denní požadavek R ≥ max(n1, . . . , n7) Hana Rudová, FI MU: Rozvrhování zaměstnanců 280 13. května 2021 Algoritmus a příklad (krok 1) Den 1 2 3 4 5 6 7 Ne Po Út St Čt Pá So Zaměstnanců 3 5 5 5 7 7 3 Zaměstnanec požaduje volné 3 víkendy z 5: k1 = 3, k2 = 5 1 Spočítej minimální počet zaměstnanců R je rovno maximu ze tří omezení dolní hranice R ≥ 5 · 3 5 − 3 = 8 R ≥ 3 + 5 + 5 + 5 + 7 + 7 + 3 5 = 7 R ≥ max(3, 5, 5, 5, 5, 7, 7, 3) = 7 ⇒ R = 8, n = 3 Hana Rudová, FI MU: Rozvrhování zaměstnanců 281 13. května 2021 Algoritmus a příklad (krok 2) 2 Rozvrhuj volné víkendy 1 přiřaď do prvního volného víkendu prvních (R − n) zaměstnanců 2 přiřaď do druhého volného víkendu dalších (R − n) zaměstnanců 3 opakuj tento proces cyklicky zaměstnanec 1 je brán jako následující zaměstnanec po zaměstnanci R R − n = 8 − 3 = 5 So Ne Po Út St Čt Pá So Ne Po Út St Čt Pá So Ne Po Út St Čt Pá So 1 X X X X X 2 X X X X X 3 X X X X X 4 X X X X X 5 X X X X 6 X X X X 7 X X X X 8 X X X Hana Rudová, FI MU: Rozvrhování zaměstnanců 282 13. května 2021 Algoritmus (krok 3) 3 Urči dodatečné páry volných dnů celkový počet volných dnů: 2R (každý má dva dny v týdnu volné) (R − n) volných sobot a (R − n) volných nedělí je už určeno (2R − 2n) ⇒ 2n volných dnů musí být přiřazeno Sj přebytek zaměstnanců v j-tém dni Sj = R − nj pro j = 2, . . . , 6 (od pondělí do pátku zatím všech R zaměstnanců pracuje) S1 = n − n1 S7 = n − n7 (R − n zaměstnanců má každý víkend zatím volno, tj. n zam. pracuje) 7 j=1 Sj = 6 j=2 (R − nj ) + n − n1 + n − n7 = = 5R − 7 j=1 nj + 2n ≥ 2n z omezení celkového požadavku 5R − 7 j=1 nj ≥ 0 Hana Rudová, FI MU: Rozvrhování zaměstnanců 283 13. května 2021 Algoritmus a příklad (krok 3) Iterativně konstruuj seznam n párů volných dnů: 1 vyber den k takový, že Sk = max(S1, . . . , S7) 2 vyber libovolný i = k takový, že Si > 0 jestliže Si = 0 pro všechna i = k, nastav i = k 3 přidej pár (k, i) do seznamu a sniž Si a Sk o 1 Opakuj tento postup n-krát páry stejných volných dnů (k, k) mohou být na konci seznamu Příklad: Ne Po Út St Čt Pá So Den 1 2 3 4 5 6 7 Sj 0 3 3 3 1 1 0 2 2 1 2 0 1 seznam párů volných dnů (n = 3): (Po,Út), (Út,St), (Út,St) Hana Rudová, FI MU: Rozvrhování zaměstnanců 284 13. května 2021 Algoritmus (krok 4) 4 Přiřazení párů volných dnů v týdnu 1 1 rozděl zaměstnance do kategorií (i = 1) Kategorie Víkend i Týden i Víkend i + 1 T1 volný nejsou třeba volné dny volný T2 volný 1 volný den potřeba zaměstnaný T3 zaměstnaný 1 volný den potřeba volný T4 zaměstnaný 2 volné dny potřeba zaměstnaný |T3| + |T4| = n (plyne z víkendu i) |T2| + |T4| = n (plyne z víkendu i + 1) ⇒ |T2| = |T3| páruj T2 a T3 2 přiřaď páry volných dnů nejprve přiřaď páry volných dnů T4 zaměstnancům přiřaď T3 a T2: T3 je dřívější den páru, T2 je pozdější Hana Rudová, FI MU: Rozvrhování zaměstnanců 285 13. května 2021 Algoritmus (krok 5) 5 Přiřazení párů volných dnů v týdnu i 1 rozděl zaměstnance do kategorií 2 přiřaď páry volných dnů 1 pokud existuje pár stejných prvků (k, k) – týden i je rozvrhován stejně jako týden 1, nezávisle na týdnu (i − 1) 2 pokud jsou všechny páry různé – všichni zaměstnanci typu T3 a T4 v týdnu i jsou přiřazeni stejnému páru volných dnů, který dostali od týdne (i − 1) – T4 má oba dny volné – T3 dostane dřívější den z určeného páru – a na T2 zůstanou pozdější dny z páru Hana Rudová, FI MU: Rozvrhování zaměstnanců 286 13. května 2021 Příklad (krok 4+5) Kategorie Víkend i Týden i Víkend i + 1 T1 volný nejsou třeba volné dny volný T2 volný 1 volný den potřeba zaměstnaný T3 zaměstnaný 1 volný den potřeba volný T4 zaměstnaný 2 volné dny potřeba zaměstnaný Seznam párů volných dnů (n = 3): A:(Po,Út), B:(Út,St), C:(Út,St) So Ne Po Út St Čt Pá So Ne Po Út St Čt Pá So Ne 1 X T1 X X T2 X A 2 X T1 X X T2 X B 3 X T2 X A T3 A X X 4 X T2 X B T3 B X X 5 X T2 X C T3 C X X 6 T3 A X T1 X X X 7 T3 B X T1 X X X 8 T3 C X T2 X C Hana Rudová, FI MU: Rozvrhování zaměstnanců 287 13. května 2021 Příklad II. (pár stejných volných dnů) Den 1 2 3 4 5 6 7 Ne Po Út St Čt Pá So Zaměstnanců 1 0 3 3 3 3 2 Zaměstnanci požadují 1 volný víkend ze 3 R ≥ 3 · 2 3 − 1 = 3 R ≥ k2n k2−k1 R ≥ 1 + 0 + 3 + 3 + 3 + 3 + 2 5 = 3 R ≥ 1 5 7 j=1 nj R ≥ max(1, 0, 3, 3, 3, 3, 3, 2) = 3 R ≥ max(n1, . . . , n7) ⇒ R = 3, n = 2 Hana Rudová, FI MU: Rozvrhování zaměstnanců 288 13. května 2021 Příklad II. (dokončení) R − n = 3 − 2 = 1 víkendů volných So Ne Po Út St Čt Pá So Ne Po Út St Čt Pá So Ne 1 X X 2 X X 3 X X Ne Po Út St Čt Pá So Den 1 2 3 4 5 6 7 Sj 1 3 0 0 0 0 0 0 2 1 0 Seznam párů volných dnů (n = 2): A:(Ne,Po), B:(Po,Po) So Ne Po Út St Čt Pá So Ne Po Út St Čt Pá So Ne Po 1 X T2 X B T4 A A T3 B 2 T3 B X T2 X B T4 A A 3 T4 A A T3 B X T2 X B Hana Rudová, FI MU: Rozvrhování zaměstnanců 289 13. května 2021 Diskuse k algoritmu Každý zaměstnanec má alespoň k1 víkendů z k2 víkendů volných Každý zaměstnanec pracuje přesně 5 dnů v týdnu od neděle do soboty Žádný zaměstnanec nepracuje více než 5 po sobě jdoucích dnů, pokud jsou všechny páry volných dnů různé Lze také ukázat, že žádný zaměstnanec nepracuje více než 6 po sobě jdoucích dnů, když jsou některé páry volných dnů stejné Algoritmus dává dolní hranici na počet zaměstnanců Algoritmus přiřazuje volné dny, než aby se snažil splnit minimální denní požadavky Hana Rudová, FI MU: Rozvrhování zaměstnanců 290 13. května 2021 Rozvrhování směn Řešili jsme problém rozvrhování volných dnů různé vzorky jsou přiřazovány v rámci cyklu cena přiřazení zaměstnance ke vzorku není závislá na vzorku vzorky mají stejnou cenu ⇒ řešení problému relativně snadné cíl: minimalizace celkového počtu zaměstnanců 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 Hana Rudová, FI MU: Rozvrhování zaměstnanců 291 13. května 2021 Značení m period (hodin) např. od 10:00 do 21:00 V periodě i, i = 1, . . . , m je potřeba bi zaměstnanců např. 10:00: 3, 11:00: 4, 12:00 6, ... n vzorků směn např. 10:00 – 18:00, 13: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 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ů Hana Rudová, FI MU: Rozvrhování zaměstnanců 292 13. května 2021 Model celočíselného lineárního programování Minimalizace c1x1 + c2x2 + · · · + cnxn za předpokladu a11x1 + a12x2 + · · · + a1nxn ≥ b1 a21x1 + a22x2 + · · · + a2nxn ≥ b2 · · · am1x1 + am2x2 + · · · + amnxn ≥ bm xj ≥ 0 ∀j = 1, . . . , n kde x1, . . . , xn jsou celá čísla V maticovém zápisu: minimalizace c x za předpokladu Ax ≥ b x ≥ 0 Problém je NP-těžký, nicméně A má často speciální tvar např. 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: Rozvrhování zaměstnanců 293 13. května 2021 Příklad: rozvrhování směn v obchodě (kontinuální posloupnost 1) 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: Rozvrhování zaměstnanců 294 13. května 2021 Cyklické rozvrhování směn Cyclic Staffing Problem Další problém rozvrhování směn, který je polynomiálně řešitelný Cíl: minimalizace ceny přiřazení zaměstnanců do m period za předpokladu dostatečné množství zaměstnanců každou periodu i vzhledem k bi každý zaměstanec pracuje k po sobě jdoucích period a je volný následujících m − k period (k, m) problém Poznámka k číslování period po periodě m opět následuje perioda 1 Příklad: (3, 5) problém A =       1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1       Hana Rudová, FI MU: Rozvrhování zaměstnanců 295 13. května 2021 Řešení problému cyklického rozvrhování směn Nejedná se o problém s kontinuálními 1 Lze ukázat: řešení lineární relaxace problému je velmi blízké řešení celočíselného programu A tedy: následující algoritmus vede k optimálnímu řešení Algoritmus 1 řešením lineární relaxace dostaneme x1, . . . , xn pokud jsou x1, . . . , xn celá čísla ⇒ máme řešení, jinak 2 vytvoř linerární programy LP’ a LP” s následujícími přidanými omezeními LP’: x1 + · · · + xn = x1 + · · · + xn LP”: x1 + · · · + xn = x1 + · · · + xn LP” vždy nalezne optimální celočíselné řešení LP’ nemusí být řešitelný ⇒ LP” řešení optimální pro LP pokud má LP’ celočíselné optimální řešení, pak optimální řešení LP je lepší z řešení LP’ a LP” Hana Rudová, FI MU: Rozvrhování zaměstnanců 296 13. května 2021 Shrnutí Rozvrhování volných dnů základní problém Rozvrhování směn obecný problém Cyklické rozvrhování směn speciální případ Hana Rudová, FI MU: Rozvrhování zaměstnanců 297 13. května 2021 Rozvrhování předmětů na univerzitě 13. května 2021 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ě 299 13. května 2021 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ě 300 13. května 2021 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ě 301 13. května 2021 Struktura předmětu s jeho třídami (vyučovanými částmi) Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 302 13. května 2021 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/událost předmětu Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 303 13. května 2021 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ě 304 13. května 2021 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ě 305 13. května 2021 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ě 306 13. května 2021 Konfliktní statistika pro třídu CS 101 Lab 2 Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 307 13. května 2021 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ě 308 13. května 2021 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ě 309 13. května 2021 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ě 310 13. května 2021 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ě 311 13. května 2021 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ě 312 13. května 2021 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ě 313 13. května 2021 UniTime.org: GUI s vygenerovaným rozvrhem Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 314 13. května 2021 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ě 315 13. května 2021 International Timetabling Competition 2019 Mezinárodní soutěž, kterou organizuje 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 tři množiny datových sad publikovány 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 srpen 2018: zveřejnění listopad 2018: publikována první soutěžní data listopad 2019: konec Aktuálně 130 uživatelů ze 44 zemí Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 316 13. května 2021 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ě 317 13. května 2021 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.public.iastate.edu/~olafsson/ie514_2001.html, 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ě 318 13. května 2021