56

Rozvrhov´an´ı Radek Maˇr´ık CVUT FEL, K13133

16. dubna 2013

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

1 / 56

Obsah 1

2

Pl´anov´an´ı a rozvrhov´an´ı Vztah pl´anov´an´ı a rozvrhov´an´ı ´ Uvod do rozvrhov´an´ı Pˇrehled metodik Pˇr´ıklady re´aln´ych probl´em˚ u Terminologie

3

Klasifikace rozvrhovac´ıch probl´emu Vlastnosti stroje Omezen´ı Optimalizace

4

Metody lok´aln´ıho prohled´av´an´ı Obecnˇe Tabu prohled´av´an´ı

5

Rozvrhov´an´ı a CSP Formulace probl´emu

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

2 / 56

Pl´ anov´ an´ı a rozvrhov´ an´ı

Vztah pl´ anov´ an´ı a rozvrhov´ an´ı

Pl´anov´an´ı a rozvrhov´an´ı ve skuteˇcn´em svˇetˇe [RN10]

Aktivity vesm´ırn´ych lod´ı, v tov´arn´ach, ˇci vojensk´ych operace jsou sloˇzit´e. Jazyk reprezentace mus´ı b´yt rozˇs´ıˇren. Akce s dobou trv´ an´ı a omezen´ı zdroj˚ u. Metody jsou hierarchicky organizov´ any (HTN). Jak pˇristoupit k prostˇred´ım s neurˇcitost´ı.

Pl´anovaˇc potˇrebuje komunikovat s prostˇred´ım. Prostˇred´ı obsahuje dalˇs´ı agenty.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

4 / 56

Pl´ anov´ an´ı a rozvrhov´ an´ı

ˇ Cas, rozvrhy a zdroje

Vztah pl´ anov´ an´ı a rozvrhov´ an´ı

[RN10]

Reprezentace klasick´eho pl´anov´an´ı Co se m´a dˇelat, V jak´em poˇr´adku.

Rozˇs´ıˇren´ı Jak dlouho se vykon´av´a dan´a akce, Kdy se zah´aj´ı.

Rozvrhov´an´ı ˇcasov´a omezen´ı, omezen´ı na zdroje.

Pˇr´ıklady Rozvrh aerolinie, Kter´a letadla jsou pˇriˇrazena ke kter´ym let˚ um, ˇ Casy odlet˚ u a pˇr´ılet˚ u, Aerolinie m´a omezen´y poˇcet zamˇestnanc˚ u. Obsluha, kter´a je na jednom letu, nem˚ uˇze b´yt v tom sam´em ˇcasu na letu jin´em. Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

5 / 56

Pl´ anov´ an´ı a rozvrhov´ an´ı

Vztah pl´ anov´ an´ı a rozvrhov´ an´ı

Pˇr´ıstup ”Nejprve pl´anuj, pak rozvrhuj”

[RN10]

V´yroba ve skuteˇcn´em svˇetˇe, logistick´e probl´emy 1

F´aze pl´anov´an´ı Jsou vybr´ any akce. Omezen´ı uspoˇr´ ad´ an´ı. ˇ Casto je vykon´ av´ ano lidmi-experty.

2

F´aze rozvrhov´an´ı Pˇrid´ ana informace o ˇcasu a dob´ ach, Omezen´ı na zdroje, Omezen´ı na koneˇcn´y term´ın/uz´ avˇerku.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

6 / 56

Pl´ anov´ an´ı a rozvrhov´ an´ı

Vztah pl´ anov´ an´ı a rozvrhov´ an´ı

Pˇr´ıstup ”Nejprve pl´anuj, pak rozvrhuj”

[RN10]

V´yroba ve skuteˇcn´em svˇetˇe, logistick´e probl´emy 1

F´aze pl´anov´an´ı Jsou vybr´ any akce. Omezen´ı uspoˇr´ ad´ an´ı. ˇ Casto je vykon´ av´ ano lidmi-experty.

2

F´aze rozvrhov´an´ı Pˇrid´ ana informace o ˇcasu a dob´ ach, Omezen´ı na zdroje, Omezen´ı na koneˇcn´y term´ın/uz´ avˇerku.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

7 / 56

´ Uvod do rozvrhov´ an´ı

Obecn´e metodiky

Pˇrehled metodik

[Rud13]

´ Uvod Grahamova klasifikace rozvrhovac´ıch probl´em˚ u Obecn´ e ˇreˇs´ıc´ı metody Pˇresn´e ˇreˇs´ıc´ı metody metoda vˇetv´ı a mez´ı

Heuristiky ˇr´ıd´ıc´ı pravidla (dispatching rules) paprskov´e prohled´av´an´ı (beam search) lok´aln´ı prohled´av´an´ı: simulovan´e ˇz´ıh´an´ı, tabu prohled´av´an´ı, genetick´e algoritmy

Matematick´e programov´an´ı: formulace line´arn´ı celoˇc´ıseln´e

Programov´an´ı s omezuj´ıc´ımi podm´ınkami Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

9 / 56

´ Uvod do rozvrhov´ an´ı

Specifick´e metodiky

Pˇrehled metodik

[Rud13]

Pl´ anov´ an´ı projektu: reprezentace projektu, kritick´a cesta, kompromis mezi ˇcasem a cenou, pracovn´ı s´ıla. Pl´ anov´ an´ı u ´loh: ˇr´ıd´ıc´ı pravidla, metoda vˇetv´ı a mez´ı, paprskov´e prohled´av´an´ı, matematick´e prohled´av´an´ı, posunov´an´ı kritick´eho m´ısta. Rozvrhov´ an´ı mont´ aˇ zn´ıch syst´ em˚ u: mont´aˇzn´ı linka s flexibiln´ım ˇcasem, s fixn´ım ˇcasem, s paraleln´ımi pracovn´ımi stanicemi. Rezervace: intervalov´e rozvrhov´an´ı, rezervaˇcn´ı syst´emy s rezervou. Timetabling: rozvrhov´an´ı s oper´atory, rozvrhov´an´ı s pracovn´ı silou. Rozvrhov´ an´ı zamˇ estnanc˚ u: rozvrhov´an´ı voln´ych dn˚ u, rozvrhov´an´ı smˇen, cyklick´e rozvrhov´an´ı smˇen. Univerzitn´ı rozvrhov´ an´ı: teorie a praxe

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

10 / 56

´ Uvod do rozvrhov´ an´ı

Definice pojmu rozvrhov´an´ı

Pˇrehled metodik

[Rud13]

Rozvrhov´an´ı optim´aln´ı alokace/pˇriˇrazen´ı zdroj˚ u mnoˇzinˇe u ´loh v ˇcase omezen´e mnoˇzstv´ı zdroj˚ u, maximalizace zisku za dan´ych omezen´ı Stroj Mi , i = 1, . . . , m ´ Uloha Jj , j = 1, . . . , n

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

11 / 56

´ Uvod do rozvrhov´ an´ı

´ Ulohy, stroje

Pˇrehled metodik

[Rud13]

Stroje (zdroje, prostˇredky) i = 1, . . . , m ´ Ulohy (aktivity) j = 1, . . . , n (i, j) operace nebo prov´adˇen´ı u ´lohy j na stroji i u ´loha se m˚ uˇze skl´adat z nˇekolika operac´ı pˇr´ıklad: u ´loha 4 m´a tˇri operace s nenulovou dobou trv´an´ı (2,4),(3,4),(6,4), tj. je prov´adˇena na stroj´ıch 2,3,6

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

12 / 56

´ Uvod do rozvrhov´ an´ı

Pˇrehled metodik

Statick´e a dynamick´e parametry u´lohy

[Rud13]

Statick´e parametry u ´lohy doba trv´ an´ı pij , pj : doba prov´adˇen´ı u ´lohy j na stroji i term´ın dostupnosti j (release date) rj : nejdˇr´ıvˇejˇs´ı ˇcas, ve kter´em m˚ uˇze b´yt u ´loha j prov´adˇena term´ın dokonˇ cen´ı (due date) dj : ˇcas, do kdy by mˇela b´yt u ´loha j nejpozdˇeji dokonˇcena (preference) vs. deadline: ˇcas, do kdy mus´ı b´yt u ´loha j nejpozdˇeji dokonˇcena (poˇzadavek) v´ aha wj : d˚ uleˇzitost u ´lohy j relativnˇe vzhledem k ostatn´ım u ´loham v syst´emu

Dynamick´e parametry u ´lohy ˇ cas startu u ´lohy (start time) Sij , Sj : ˇcas zah´ajen´ı prov´adˇen´ı u ´lohy j na stroji i ˇ cas konce u ´lohy (completion time) Cij , Cj : ˇcas, kdy je dokonˇceno prov´adˇen´ı u ´lohy j na stroji i Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

13 / 56

´ Uvod do rozvrhov´ an´ı

Rozvrh

Pˇrehled metodik

[Rud13]

Rozvrh: d´an um´ıstˇen´ım u ´loh do konkr´etn´ıho ˇcasu a na konkr´etn´ı zdroje, kde maj´ı b´yt u ´lohy prov´adˇeny ´ y rozvrh: Upln´ v rozvrhu jsou um´ıstˇeny vˇsechny u ´lohy ze zad´an´ı probl´emu ˇ C´ asteˇ cn´ y rozvrh: nˇekter´e u ´lohy ze zad´an´ı probl´emu nejsou um´ıstˇeny/pˇriˇrazeny Konzistentn´ı rozvrh: rozvrh, ve kter´em jsou splnˇena vˇsechna omezen´ı kladen´a na zdroje a um´ıstˇen´e/pˇriˇrazen´e u ´lohy, napˇr. u ´loha je napl´anov´ana v ˇcase, kdy je dostupn´a na jednom stroji (s jednotkovou kapacitou) bˇeˇz´ı nejv´yˇse jedna u ´loha

Konzistentn´ı u ´pln´y rozvrh vs. konzistentn´ı ˇc´asteˇcn´y rozvrh Optim´ aln´ı rozvrh: um´ıstˇen´ı u ´loh na stroje je optim´aln´ı vzhledem k zadan´emu optimalizaˇcn´ımu krit´eriu, napˇr. min Cmax : makespan (ˇcas dokonˇcen´ı posledn´ı u ´lohy) je minim´aln´ı Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

14 / 56

´ Uvod do rozvrhov´ an´ı

Pˇr´ıklad: mont´aˇz kola

Pˇr´ıklady re´ aln´ ych probl´ em˚ u

[Rud13]

10 u ´loh s danou dobou trv´an´ı Precedenˇcn´ı podm´ınky u ´lohu lze prov´est aˇz po proveden´ı zadan´e mnoˇziny u ´loh

Nepreemtivn´ı u ´lohy u ´lohy nelze pˇreruˇsit

Optimalizaˇcn´ı krit´eria minimalizace makespan minim´aln´ı poˇcet pracovn´ık˚ u Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

16 / 56

´ Uvod do rozvrhov´ an´ı

Pˇr´ıklad: ˇreˇsen´ı mont´aˇz kola

Pˇr´ıklady re´ aln´ ych probl´ em˚ u

[Rud13]

10 u ´loh s danou dobou trv´an´ı Precedenˇcn´ı podm´ınky u ´lohu lze prov´est aˇz po proveden´ı zadan´e mnoˇziny u ´loh

Nepreemtivn´ı u ´lohy u ´lohy nelze pˇreruˇsit

Optimalizaˇcn´ı krit´eria minimalizace makespan minim´aln´ı poˇcet pracovn´ık˚ u

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

17 / 56

´ Uvod do rozvrhov´ an´ı

Pˇr´ıklady rozvrhov´an´ı

Pˇr´ıklady re´ aln´ ych probl´ em˚ u

[Rud13]

Pl´anov´an´ı v´yroby polovodiˇc˚ u velk´e mnoˇzstv´ı r˚ uznorod´ych v´yrobk˚ u, odliˇsn´e mnoˇzstv´ı vyr´abˇen´ych poloˇzek cena za nastaven´ı stroj˚ u, dodrˇzen´ı poˇzadovan´e doby v´yroby

Pl´anov´an´ı z´asobovac´ıch ˇretˇezc˚ u napˇr. lesnat´a oblast − v´yroba pap´ıru − v´yrobky z pap´ıru − distribuˇcn´ı centra − koncov´y z´akazn´ık minimalizace ceny v´yroby, dopravy, skladov´an´ı

Pl´anov´an´ı v´yroby pap´ıru vstup dˇrevo, v´ystup role pap´ıru, drah´e stroje, r˚ uzn´e typy pap´ıru, minimalizace v´yroby na sklad

Automobilov´a mont´aˇzn´ı linka v´yroba r˚ uzn´ych typ˚ u aut s r˚ uzn´ym vybaven´ım optimalizace v´ykonu, rovnomˇern´a z´atˇeˇz

Plnˇen´ı limon´ad do lahv´ı 4 pˇr´ıchutˇe, kaˇzd´a pˇr´ıchut’ m´a vlastn´ı dobu plnˇen´ı minimalizovat dobu cyklu, jeden stroj Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

18 / 56

´ Uvod do rozvrhov´ an´ı

Pˇr´ıklady rozvrhov´an´ı II

Pˇr´ıklady re´ aln´ ych probl´ em˚ u

[Rud13]

Rozvrhov´an´ı sester v nemocnici odliˇsn´y poˇcet sester v pracovn´ı dny a o v´ıkendu, menˇs´ı n´aroky pˇri obsazov´an´ı noˇcn´ıch smˇen, urˇcit pˇriˇrazen´ı sester na smˇeny, splnˇen´ı poˇzadavk˚ u, minimalizace ceny

Pl´anov´an´ı v prostˇred´ı Grid˚ u clustery, superpoˇc´ıtaˇce, desktopy, speci´aln´ı zaˇr´ızen´ı pl´anov´an´ı v´ypoˇcetn´ıch u ´loh na zdroje pl´anov´an´ı datov´ych pˇrenos˚ u a datov´e zpracov´an´ı

Univerzitn´ı rozvrhov´an´ı pˇredmˇet˚ u Nalezen´ı ˇcasu a m´ıstnosti pro v´yuku pˇredmˇet˚ u na univerzitˇe omezen´ı kladena na um´ıstˇen´ı pˇredmˇet˚ u optimalizace preferenˇcn´ıch poˇzadavk˚ u na ˇcas a m´ıstnosti minimalizace poˇctu pˇrekr´yvaj´ıc´ıch se pˇredmˇet˚ u pro vˇsechny studenty

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

19 / 56

´ Uvod do rozvrhov´ an´ı

Scheduling vs. timetabling

Terminologie

[Rud13]

Scheduling . . . rozvrhov´an´ı/pl´anov´an´ı alokace zdroj˚ u za dan´ych podm´ınek na objekty um´ıstˇen´ych v ˇcasoprostoru tak, ˇze je minimalizov´ana celkov´a cena dan´ych zdroj˚ u d˚ uraz je kladen na uspoˇr´ad´an´ı objekt˚ u, precedenˇcn´ı podm´ınky pˇr. pl´anov´an´ı v´yroby: stanoven´ı poˇrad´ı operac´ı, d˚ uleˇzitost ˇcasov´ych n´avaznost´ı operac´ı

schedule . . . rozvrh: zahrnuje prostorov´e a ˇcasov´e informace Timetabling . . . rozvrhov´an´ı alokace zdroj˚ u za dan´ych podm´ınek na objekty um´ıstˇen´ych v ˇcasoprostoru tak, ˇze jsou co nejl´epe splnˇena zadan´a krit´eria d˚ uraz kladen na konkr´etn´ı ˇcasov´e um´ıstˇen´ı objekt˚ u ˇcasto vymezen pˇredem ˇcasov´y horizont (poˇcet rozvrhovan´ych slot˚ u) pˇr. ˇskoln´ı rozvrhov´an´ı: pˇredmˇet˚ um pˇriˇrazen ˇcas a m´ısto vyuky

timetable . . . rozvrh: ukazuje, kdy a kde se budou ud´alosti konat. Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

21 / 56

´ Uvod do rozvrhov´ an´ı

Sequencing a Rostering

Terminologie

[Rud13]

Sequencing . . . seˇrazen´ı za dan´ych podm´ınek: konstrukce poˇrad´ı u ´loh, ve kter´em budou prov´adˇeny

sequence . . . posloupnost poˇrad´ı, ve kter´em jsou u ´lohy prov´adˇeny

pˇr. plnˇen´ı limon´ad do lahv´ı Rostering . . . rozpis sluˇzeb um´ıstˇen´ı zdroj˚ u za dan´ych podm´ınek do slot˚ u s pomoc´ı vzor˚ u (pattern) roster . . . rozpis seznam jmen lid´ı, kter´y urˇcuje, kter´e u ´lohy budou prov´adˇet a kdy

pˇr. rozpis sester v nemocnici, rozpis ˇridiˇc˚ u autobus˚ u Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

22 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Grahamova klasifikace

Vlastnosti stroje

[Rud13]

Grahamova klasifikace α|β|γ pouˇz´ıv´a se pro popis rozvrhovac´ıch probl´em˚ u α: charakteristiky stroje popisuje zp˚ usob alokace u ´loh na stroje

β: charakteristiky u ´loh popisuje omezen´ı aplikovan´a na u ´lohy

γ: optimalizaˇcn´ı krit´eria sloˇzitost pro jednotliv´e rozvrhovac´ı probl´emy Pˇr´ıklady P 3|prec|Cmax : mont´aˇz kola P P m|rj | wj Cj : paraleln´ı stroje

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

24 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Vlastnosti stroje α

Vlastnosti stroje

[Rud13]

Jeden stroj 1: 1| . . . | . . . Identick´ e paraleln´ı stroje P m m identick´ych stroj˚ u zapojen´ych paralelnˇe (se stejnou rychlost´ı) u ´loha je d´ana jedinou operac´ı u ´loha m˚ uˇze b´yt prov´adˇena na libovoln´em z m stroj˚ u

Paraleln´ı stroje s r˚ uznou rychlost´ı Qm doba trv´an´ı u ´lohy j na stroji i pˇr´ımo z´avisl´a na jeho rychlosti vi pij = pj /vi pˇr. nˇekolik poˇc´ıtaˇc˚ u s r˚ uznou rychlost´ı procesoru

Nez´ avisl´ e paraleln´ı stroje s r˚ uznou rychlost´ı Rm stroje maj´ı r˚ uznou rychlost pro r˚ uzn´e u ´lohy stroj i zpracov´av´a u ´lohu j rychlost´ı vij pij = pj /vij pˇr. vektorov´y poˇc´ıtaˇc poˇc´ıt´a vektorov´e u ´lohy rychleji neˇz klasick´e PC

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

25 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Vlastnosti stroje

Multi-operaˇcn´ı (shop) probl´emy

[Rud13]

Multi-operaˇ cn´ı (shop) probl´ emy jedna u ´loha je prov´adˇena postupnˇe na nˇekolika stroj´ıch u ´loha j se skl´ ad´ a z nˇekolika operac´ı (i, j) operace (i, j) u ´lohy j je prov´ adˇena na stroji i po dobu pij pˇr´ıklad: u ´loha j se 4 operacemi (1, j), (2, j), (3, j), (4, j)

Multi-operaˇcn´ı probl´emy jsou klasick´e detailnˇe studovan´e probl´emy operaˇ cn´ıho v´ yzkumu Re´aln´e probl´emy ale ˇcasto mnohem komplikovanˇejˇs´ı vyuˇzit´ı znalost´ı o podprobl´emech nebo zjednoduˇsen´ych probl´emech a jejich ˇreˇsic´ıch metod´ach

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

26 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Flow shop α

Vlastnosti stroje

[Rud13]

Flow shop F m multi-operaˇcn´ı probl´em s m stroji v s´erii kaˇzd´a u ´loha mus´ı b´yt prov´adˇena na vˇsech stroj´ıch u ´loha mus´ı b´yt prov´adˇena na vˇsech stroj´ıch ve stejn´em poˇrad´ı nejdˇr´ıve se u ´loha prov´ ad´ı na 1. stroji, pak na 2., . . .

Flexible flow shop F F s zobecnˇen´ı flow shop probl´emu s f´az´ı, kaˇzd´e f´azi pˇr´ısluˇs´ı paraleln´ı stroj tj. multi-operaˇcn´ı probl´em s s paraleln´ımi stroji u ´loha mus´ı proj´ıt vˇsemi f´azemi ve stejn´em poˇrad´ı nejprve se u ´loha prov´ ad´ı na paraleln´ım stroji 1. f´ aze, pak na paraleln´ım stroji 2. f´ aze, . . .

na paraleln´ım stroji pˇr´ısluˇsej´ıc´ım dan´e f´azi m˚ uˇze b´yt u ´loha prov´adˇena na libovoln´em stroji

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

27 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Open shop & job shop

Vlastnosti stroje

[Rud13]

Job shop Jm multi-operaˇcn´ı probl´em s m stroji poˇrad´ı prov´adˇen´ı operac´ı pro kaˇzdou u ´lohu je pˇredem urˇceno doba zpracov´ an´ı u ´lohy na nˇekter´ych stroj´ıch m˚ uˇze b´yt nulov´ a

(i, j) → (k, j) urˇcuje, ˇze u ´loha j m´a b´yt prov´adˇena na stroji i dˇr´ıve neˇz na stroji k pˇr´ıklad: (2, j) → (1, j) → (3, j) → (4, j)

Open shop Om multi-operaˇcn´ı probl´em s m stroji doba zpracov´an´ı u ´lohy na nˇekter´ych stroj´ıch m˚ uˇze b´yt nulov´a rozvrhovaˇc urˇc´ı, v jak´em poˇrad´ı je u ´loha prov´adˇena na stroj´ıch

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

28 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Omezen´ı β

Omezen´ı

[Rud13]

Precedenˇ cn´ı podm´ınky prec line´arn´ı posloupnost, stromov´a struktura pro u ´lohy a, b p´ıˇseme a → b, coˇz znamen´a Sa + pa ≤ Sb pˇr´ıklad: mont´aˇz kola

Pˇreruˇsen´ı u ´lohy (preemptions) pmtn pˇri pˇr´ıchodu u ´lohy s vyˇsˇs´ı prioritou je souˇcasn´a u ´loha pˇreruˇsena

Vhodnost stroje Mj podmnoˇzina stroj˚ u Mj , na n´ıˇz lze prov´adˇet u ´lohu j pˇriˇrazen´ı m´ıstnost´ı: postaˇcuj´ıc´ı velikost uˇcebny hry: poˇc´ıtaˇc s HW grafickou knihovnou

Omezen´ı na pracovn´ı s´ılu W, Wl do probl´emu zavedeme dalˇs´ı typ zdroje stroje mohou potˇrebovat oper´atory a u ´lohy lze prov´adˇet jen tehdy, pokud jsou dostupn´ı, W oper´ator˚ u mohou existovat r˚ uzn´e skupiny oper´ator˚ u se specifickou kvalifikac´ı Wl je poˇcet oper´ator˚ u ve skupinˇe l Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

30 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Omezen´ı (pokraˇcov´an´ı) β

Omezen´ı

[Rud13]

Smˇ erovac´ı (routing) omezen´ı ud´avaj´ı, na kter´ych stroj´ıch mus´ı b´yt u ´loha prov´adˇena poˇrad´ı prov´adˇen´ı u ´lohy v multi-operaˇcn´ıch probl´emech job shop probl´em: poˇrad´ı operac´ı pˇredem stanoveno open shop probl´em: poˇrad´ı operac´ı u ´lohy (route for the job) stanoveno aˇz pˇri rozvrhov´ an´ı

Nastavovac´ı (setup) doba a cena sijk , cijk , sjk , cjk z´avisl´e na posloupnosti prov´adˇen´ı sijk ˇcas nutn´y pro prov´adˇen´ı u ´lohy k po u ´loze j na stroji i cijk cena nutn´a pro prov´adˇen´ı u ´lohy k po u ´loze j na stroji i sjk , cjk ˇcas/cena nez´avisl´y na stroji pˇr´ıklady plnˇen´ı limon´ ad do lahv´ı probl´em obchodn´ıho cestuj´ıc´ıho 1|sjk |Cmax

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

31 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Omezen´ı (pokraˇcov´an´ı) β

Omezen´ı

[Rud13]

V´ yroba na objedn´ avku a na sklad v´yroba zboˇz´ı na sklad, pokud je u nˇej z´aruka spotˇreby nutno uv´aˇzit cenu za skladov´an´ı v´yroba zboˇz´ı na objedn´avku vynucuje u ´vahu term´ın˚ u dokonˇcen´ı vyprodukovan´e mnoˇzstv´ı z´avisl´e na z´akazn´ıkovi

Skladovac´ı prostor a doba ˇ cek´ an´ı pˇri v´ yrobˇ e omezen´e mnoˇzstv´ı prostoru pˇri v´yrobˇe horn´ı hranice poˇctu u ´loh ˇcekaj´ıc´ıch ve frontˇe na stroj blokov´ an´ı: u ´loha je zablokov´ana na souˇcasn´em stroji, protoˇze fronta na n´asleduj´ıc´ım stroji je pln´a

...

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

32 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Optimalizace

Optimalizace: v´ykon a makespan γ

[Rud13]

Makespan Cmax : maxim´aln´ı ˇcas konce u ´loh Cmax = max(C1 , . . . , Cn ) Pˇr´ıklad: Cmax = max{1, 3, 4, 5, 8, 7, 9} = 9

C´ıl: minimalizace makespan ˇcasto maximalizuje v´ ykon (throughput) zajiˇst’uje rovnomˇ ern´ e zat´ıˇ zen´ı stroj˚ u (load balancing) pˇr´ıklad: Cmax = max{1, 2, 4, 5, 7, 4, 6} = 7

Velmi ˇcasto pouˇz´ıvan´e a z´akladn´ı krit´erium Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

34 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Optimalizace: zpoˇzdˇen´ı γ

Optimalizace

[Rud13]

Zpoˇ zdˇ en´ı (lateness) u ´lohy j: Lmax = Cj − dj Maxim´ aln´ı zpoˇ zdˇ en´ı Lmax Lmax = max(L1 , . . . , Ln ) C´ıl: minimalizace maxim´ aln´ıho zpoˇ zdˇ en´ı Pˇr´ıklad:

Lmax = max(L1 , L2 , L3 ) = = max(C1 − d1 , C2 − d2 , C3 − d3 ) = = max(4 − 8, 16 − 14, 10 − 10) = = max(−4, 2, 0) = 2 Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

35 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Optimalizace

Optimalizace: nez´aporn´e zpoˇzdˇen´ı γ

[Rud13]

Nez´ aporn´ e zpoˇ zdˇ en´ı (tardiness) u ´lohy j: Tj = max(Cj − dj , 0) Celkov´ e zpoˇ zdˇ en´ı n X

Tj

j=1

C´ıl: minimalizace celkov´ eho zpoˇ zdˇ en´ı Pˇr´ıklad: 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

Celkov´ e v´ aˇ zen´ e zpoˇ zdˇ en´ı n X

wj Tj

j=1

C´ıl: minimalizace celkov´ eho v´ aˇ zen´ eho zpoˇ zdˇ en´ı Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

36 / 56

Klasifikace rozvrhovac´ıch probl´ emu

Term´ın dokonˇcen´ı a grafy γ

Radek Maˇr´ık ([email protected])

Optimalizace

[Rud13]

Rozvrhov´ an´ı

16. dubna 2013

37 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Obecnˇ e

Konstruktivn´ı vs. lok´aln´ı metody

[Rud13]

Konstruktivn´ı metody zaˇcneme s pr´azdn´ym rozvrhem do rozvrhu pˇrid´av´ame postupnˇe jednotliv´e u ´lohy tak, aby byl rozvrh st´ale konzistentn´ı

Lok´ aln´ı prohled´ av´ an´ı zaˇcneme s u ´pln´ym nekonzistentn´ım rozvrhem trivi´ alnˇe: s n´ ahodnˇe vygenerovan´ym

snaˇz´ıme se naj´ıt lepˇs´ı ”podobn´y”rozvrh lok´aln´ımi zmˇenami kvalitu rozvrhu posuzujeme optimalizaˇcn´ımi krit´erii napˇr. makespan

optimalizaˇcn´ı krit´eria vyhodnocuj´ı tak´e konzistenci rozvrhu napˇr. poˇcet poruˇsen´ych precedenˇcn´ıch omezen´ı

Hybridn´ı pˇr´ıstupy kombinace obou metod

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

39 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Obecnˇ e

Algoritmus lok´aln´ıho prohled´av´an´ı [Rud13]

1

Inicializace k=0 v´ybˇer inici´aln´ıho rozvrhu S0 zaznamen´an´ı dosud nejlepˇs´ıho rozvrhu: Sbest = S0 a costbest = F (S0 )

2

V´ ybˇ er a aktualizace v´ybˇer rozvrhu z okol´ı: Sk+1 ∈ N (Sk ) pokud kriterium pˇrijet´ı rozvrhu nesplˇ nuje ˇz´adn´y prvek N (Sk ), pak algoritmus konˇc´ı jestliˇze F (Sk+1 ) < costbest pak Sbest = Sk+1 a costbest = F (Sk+1 )

3

Ukonˇ cen´ı jestliˇze plat´ı podm´ınky ukonˇcen´ı, pak algoritmus konˇc´ı jinak k = k + 1 a skok na krok 2.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

40 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Obecnˇ e

Jeden stroj + nepreemptivn´ı u´lohy

[Rud13]

Reprezentace rozvrhu permutace n u ´loh pˇr´ıklad se ˇsesti u ´lohami: 1, 4, 2, 6, 3, 5

Definice okol´ı p´arov´a v´ymˇena sousedn´ıch u ´loh n − 1 moˇzn´ych okol´ı pˇr´ıklad: 1, 4, 2, 6, 3, 5 se zmˇen´ı napˇr. na 1, 4, 2, 6, 5, 3

nebo v´ybˇer libovoln´e u ´lohy v rozvrhu a um´ıstˇen´ı na libovolnou pozici ≤ n(n − 1) moˇzn´ych okol´ı pˇr´ıklad: z 1, 4, 2, 6, 3, 5 n´ ahodnˇe vybereme 4 a d´ ame ji jinam: 1, 2, 6, 3, 4, 5

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

41 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Krit´erium v´ybˇeru rozvrhu

Obecnˇ e

[Rud13]

Krit´erium v´ybˇeru rozvrhu krit´ erium pˇrijet´ı/odm´ıtnut´ı rozvrhu

Hlavn´ı rozd´ıl mezi vˇetˇsinou metod akceptovat vˇzdy lepˇs´ı rozvrh? nˇekdy akceptovat i horˇs´ı rozvrh?

Metoda pravdˇepodobnostn´ı n´ ahodn´ a proch´ azka: s malou pravdˇepodobnost´ı (napˇr. 0.01) akceptujeme i horˇs´ı rozvrh simulovan´ eˇ z´ıh´ an´ı

deterministick´a tabu prohled´ av´ an´ı: udrˇzujeme tabu seznam nˇekolika posledn´ıch stav˚ u/zmˇen, kter´e jsou pro dalˇs´ı v´ybˇer nepˇr´ıpustn´e

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

42 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Tabu prohled´av´an´ı

Tabu prohled´ av´ an´ı

[Rud13]

Deterministick´ e krit´ erium pˇrijet´ı/odm´ıtnut´ı rozvrhu Udrˇzov´an tabu seznam nˇekolika posledn´ıch zmˇen v rozvrhu kaˇzd´a nov´a zmˇena je um´ıstˇena na vrchol tabu seznamu pˇr. uchov´ avan´e zmˇeny: v´ymˇena u ´loh j a k

tabu seznam = seznam zak´azan´ych zmˇen okol´ı omezeno na rozvrhy, kter´e nepoˇzaduj´ı zmˇenu z tabu seznamu zabraˇ nuje cyklen´ı pˇr´ıklad trivi´ an´ıho cyklen´ı: prvn´ı krok: prohozen´ı u ´loh 3 a 4, druh´y krok: prohozen´ı u ´loh 4 a 3

pevn´a d´elka seznamu (typicky: 5-9) nejstarˇs´ı zmˇeny z tabu seznamu odstranˇeny pˇr´ıliˇs mal´ a d´elka: nebezpeˇc´ı cyklen´ı pˇr´ıliˇs velk´ a d´elka: m˚ uˇze omezit prohled´ av´ an´ı pˇr´ıliˇs

Aspiraˇ cn´ı krit´ erium urˇcuje, kdy je moˇzn´e akceptovat i zmˇeny v tabu seznamu pˇr. zmˇena z tabu seznamu povolena, pokud zlepˇseno F (Sbest ) Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

44 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Algoritmus tabu prohled´av´an´ı

Tabu prohled´ av´ an´ı [Rud13]

1

k=1 v´ybˇer inici´aln´ıho rozvrhu S1 pouˇzit´ım heuristiky, Sbest = S1

2

v´ybˇer Sc ∈ N (Sk ) jestliˇze je zmˇena Sk → Sc zak´az´ana, protoˇze je v tabu seznamu pak bˇeˇz na krok 2

3

jestliˇze zmˇena Sk → Sc nen´ı zak´az´ana tabu seznamem pak Sk+1 = Sc , uloˇz reversn´ı zmˇenu na vrchol tabu seznamu posuˇ n dalˇs´ı pozice v tabu seznamu o pozici n´ıˇze smaˇz posledn´ı poloˇzku z tabu seznamu jestliˇze F (Sc ) < F (Sbest ) pak Sbest = Sc

4

k =k+1 jestliˇze plat´ı podm´ınka ukonˇcen´ı pak konec jinak bˇeˇz na krok 2.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

45 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Pˇr´ıklad: tabu seznam

Tabu prohled´ av´ an´ı

[Rud13]

Uvaˇzujte rozvrhovac´ı probl´em s 1|dj |

P

wj Tj

opakov´an´ı: Tj = max(Cj − dj , 0) 1 2 3 4 u ´lohy pj 10 10 13 4 4 2 1 12 dj wj 14 12 1 12 Okol´ı: vˇsechny rozvrhy z´ıskan´e p´arovou v´ymˇenou sousedn´ıch u ´loh V´ybˇer rozvrhu z okol´ı: vybereme nejlepˇs´ı rozvrh Tabu seznam: p´ary u ´loh (j, k), kter´e byly pˇrehozeny pˇri posledn´ıch dvou zmˇen´ach Aplikujte tabu prohled´av´an´ı pro inici´aln´ı ˇreˇsen´ı (2, 1, 4, 3) Proved’te ˇctyˇri iterace

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

46 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Tabu prohled´ av´ an´ı

Pˇr´ıklad: tabu seznam - ˇreˇsen´ı I u ´lohy pj dj wj

1 10 4 14

2 10 2 12

3 13 1 1

[Rud13]

4 4 12 12

S1 = (2, 1, P4, 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)} 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)} Radek Maˇr´ık ([email protected])

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)} Rozvrhov´ an´ı

16. dubna 2013

47 / 56

Metody lok´ aln´ıho prohled´ av´ an´ı

Tabu prohled´ av´ an´ı

Pˇr´ıklad: tabu seznam - ˇreˇsen´ı II

u ´lohy pj dj wj

1 10 4 14

2 10 2 12

3 13 1 1

[Rud13]

4 4 12 12

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)}

S4 = (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

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

48 / 56

Rozvrhov´ an´ı a CSP

Formulace probl´ emu

Reprezentace rozloˇzen´eho stavu

Reprezentace stavu svˇeta atomick´y . . . stav je jednoduch´a, d´ale nedˇeliteln´a entita rozloˇzen´y . . . stav je sada promˇenn´ych.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

50 / 56

Rozvrhov´ an´ı a CSP

Probl´em splˇnov´an´ı podm´ınek

Formulace probl´ emu [RN10]

angl. CSP . . . Constraint Satisfaction Problem Rozloˇzen´a reprezentace stavu mnoˇzina promˇenn´ych, kaˇzd´a promˇenn´a m´a hodnotu, mnoˇzina omezen´ı nad promˇenn´ymi.

ˇ sen´ı probl´emu Reˇ pokud kaˇzd´a promˇenn´a m´a hodnotu, kter´a vyhovuje vˇsem omezen´ım kladen´e na danou promˇennou.

Pouˇz´ıvaj´ı se obecn´e heuristiky (sp´ıˇse neˇz probl´emovˇe orientovan´e) Eliminace najednou velk´ych ˇc´ast´ı prostoru ˇreˇsen´ı identifikac´ı kombinac´ı promˇenn´ych/hodnot, kter´e poruˇsuj´ı omezen´ı.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

51 / 56

Rozvrhov´ an´ı a CSP

Formulace probl´ emu

Probl´em splˇnov´an´ı podm´ınek - formalizace

[RN10]

3 komponenty X, D, C: X . . . mnoˇzina promˇenn´ych X = {X1 , . . . , Xn }, D . . . mnoˇzina dom´en, {D1 , . . . , Dn }, pro kaˇzdou promˇennou, C . . . mnoˇzina omezen´ı, kter´e specifikuj´ı povolen´e kombinace hodnot.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

52 / 56

Rozvrhov´ an´ı a CSP

Job-shop Scheduling Example

Formulace probl´ emu [RN10]

The problem of scheduling the assembly of a car. The whole job is composed of tasks. Each task is modeled as a variable. The value of each variable is the time that the tasks starts. The value is expressed as an integer number of minutes. (Precedence constraints) Constraints can assert that one task must occur before another. A wheel must be installed before the hubcap is put on.

Constraints can also specify that a task takes a certain amount of time to complete. Disjunctive constraints

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

53 / 56

Rozvrhov´ an´ı a CSP

Formulace probl´ emu

”Plan first, schedule later”Approach

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

[RN10]

16. dubna 2013

54 / 56

Rozvrhov´ an´ı a CSP

Formulace probl´ emu

Podˇekov´an´ı

Prvn´ı verze t´eto prezentace byla pˇripravena jako zkr´acen´a verze prezentac´ı Hany Rudov´e [Rud13]

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

55 / 56

Rozvrhov´ an´ı a CSP

Formulace probl´ emu

References I

Stuart J. Russell and Peter Norvig. Artificial Intelligence, A Modern Approach. Pre, third edition, 2010. Hana Rudov´ a. PA167 Rozvrhov´ an´ı, lecture notes, in Czech. http://www.fi.muni.cz/ hanka/rozvrhovani/, March 2013.

Radek Maˇr´ık ([email protected])

Rozvrhov´ an´ı

16. dubna 2013

56 / 56