Rozvrhování zdravotních sester pomocí omezujících podmínek

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY

Rozvrhování zdravotních sester pomocí omezujících podmínek

Bakalářská práce Pavel Januš

Brno, jaro 2011

Prohlášení Prohlašuji, že tato bakalářská práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.

Vedoucí práce: doc. Mgr. Hana Rudová, Ph.D.

i

Poděkování Rád bych touto cestou poděkoval vedoucí bakalářské práce doc. Mgr. Haně Rudové, Ph.D., za věnovaný čas, trpělivost, podporu a poskytnutí cenných rad, které mi při tvorbě práce pomohly.

ii

Shrnutí Hlavním cílem této bakalářské práce je řešení problému rozvrhování zdravotních sester pomocí omezujících podmínek. Tato bakalářská práce se také zabývá studiem problému rozvrhování zaměstnanců, možností systému ILOG pro řešení tohoto problému a návrhem a analýzou vhodných modelů pro vybraný problém rozvrhování zdravotních sester. Součástí bakalářské práce je implementace modelů v ILOGu a jejich experimentální vyhodnocení.

Annotation The main goal of this Bachelor‟s thesis is to solve the nurse rostering problem with constraint condition. This Bachelor‟s thesis also deal with study of nurse rostering problem, possibilities of the ILOG system for solving this problem and design and analysis of the proper models for selected problem of the nurse rostering. Part of the Bachelor‟s thesis is to implement models in ILOG and their experimental evaluation.

iii

Klíčová slova rozvrhování zdravotních sester, omezující podmínky, pevné omezení, měkké omezení, ILOG, OPL

iv

Obsah 1. Úvod .................................................................................................................................. 1 2. Omezující podmínky........................................................................................................ 3 2.1 Problém splňování podmínek .......................................................................................... 3 2.2 Optimalizační problém s omezujícími podmínkami ........................................................ 3 2.3 Optimalizační problém s měkkými podmínkami............................................................. 4 2.4 Základní řešící metody..................................................................................................... 4 3. Rozvrhování ..................................................................................................................... 6 3.1 Omezení a optimalizační kritéria ..................................................................................... 6 4. Rozvrhování zdravotních sester ..................................................................................... 7 4.1 Pevná omezení ................................................................................................................. 8 4.2 Měkká omezení ................................................................................................................ 9 5. ILOG ............................................................................................................................... 10 5.1 Programovací jazyk OPL ............................................................................................... 10 5.1.1 Základní datové typy ............................................................................................ 10 5.1.2 Základní funkce a klíčová slova ........................................................................... 11 6. Navržený model.............................................................................................................. 13 6.1 Datová reprezentace ....................................................................................................... 13 6.2 Pevná omezení ............................................................................................................... 14 6.3 Měkká omezení .............................................................................................................. 16 7. Experimentální výpočty datových sad ......................................................................... 20 7.1 Popis datových sad......................................................................................................... 20 7.2 Řešení datových sad....................................................................................................... 21 7.3 Závislost doby výpočtu na kvalitě řešení ....................................................................... 25 8. Závěr ............................................................................................................................... 28 Literatura ........................................................................................................................... 29 A Obsah CD ........................................................................................................................ 30 B Popis textového zadání ................................................................................................... 31

v

1. Úvod Zdravotní zařízení po celém světě vytváří rozvrhy směn pro jejich zaměstnance. Ve zdravotnictví je kvalita vytvořeného rozvrhu důležitá, neboť nekvalitní rozvržení zdravotních sester na směny by mohlo vést k přepracování, nadměrnému stresu z práce, což by se citelně projevilo na kvalitě podávaných služeb. Stejně tak není možné, aby na dané směně pracovalo méně, nebo více zaměstnanců než je požadováno. Menší počty zaměstnanců by vedly k nedostatečné pracovní síle, naopak vyšší počty zaměstnanců jsou pro nemocnici finanční zátěži. Ačkoliv je problém rozvrhování zdravotních sester na směny široce prozkoumaným problémem, je stále nedostatek automatizovaných systému pro tvorbu rozvrhů. Existuje mnoho nemocnic, kde se tvorbou rozvrhu zabývá hlavní sestra, rozvrh tvoří „na papíře“ a jeho tvorba ji stojí mnoho času a úsilí. Nedostatek řešících systému je spojen s tím, že rozvrhování zdravotních sester je problém NP úplný a není možné ho řešit pomocí deterministických metod. Tato bakalářská práce se zabývá řešením problému rozvrhování zdravotních sester pomocí omezujících podmínek. Součástí práce je studium problému rozvrhování zaměstnanců a studium možností systému ILOG pro řešení tohoto problému. Úkolem práce je pak návrh a analýza vhodných modelů pro vybraný problém rozvrhování zdravotních sester. Součásti práce je také implementace modelů v ILOGu a jejich experimentální vyhodnocení. Práce řeší vybrané vlastnosti problémů Nurse Rostering Competition 2010 [CHS+10]. K řešení se využívá programovací jazyk OPL a modely jsou implementovány v ILOGu. Práce předkládá výsledky experimentálních výpočtů. V první kapitole vysvětleno, co jsou omezující podmínky, jaké typy omezujících podmínek existují a také k čemu se využívají. Je zde definován problém splňování podmínek, optimalizační problém s omezujícími podmínkami, optimalizační problém s měkkými podmínkami a jsou zmíněny základní řešící metody. Další kapitola definuje základní pojmy používané v rozvrhování a také popisuje omezení a optimalizační kritéria. Kapitola věnovaná rozvrhování zdravotních sester na směny popisuje části, ze kterých je tento problém složený. Zmiňuje metody řešení, které jsou pro tento problém vhodné. Poslední dvě části této kapitoly jsou věnovány pevným a měkkým omezením, které jsou v Nurse Rostering Competition uvažována. V kapitole, která se zabývá jedním z produktů firmy ILOG, který je nazvaný IBM ILOG CPLEX resp. programovacím jazykem OPL na kterém je založen. Jsou popsány datové typy, funkce a klíčová slova, která jsou v práci použita. Následující kapitola popisuje navržený model pro řešení problému rozvrhování zdravotních sester na směny. Popisuje datovou reprezentaci vytvořeného modelu a všechny pevná a měkká omezení, které byly pro řešení problému vytvořeny. Pro každé omezení je uveden slovní popis algoritmu a zdrojový kód napsaný v programovacím jazyku OPL.

1

Na závěr jsou prezentovány experimentální výsledky pro instance řešených datových sad. Jsou popsány rozdíly mezi datovými sadami, tím je ukázaná rozdílná náročnost na řešení. Poslední část této kapitoly ukazuje závislost doby výpočtu na kvalitě řešení na vytvořených grafech.

2

2. Omezující podmínky V této kapitole popíšeme, co jsou omezující podmínky, jaké typy omezujících podmínek existují a k čemu se využívají. Dále pak zavedeme pojmy, jako jsou problém splňování podmínek, optimalizační problém s podmínkami a také jak se pracuje s měkkými podmínkami. V kapitole je také popsána metoda větví a mezí a propagace omezení.

2.1 Problém splňování podmínek Problém splňování podmínek [BLN01, Dech03] (Constraint Satisfaction Problem – dále jen CSP) obsahuje konečnou množinu hodnot (domain), konečnou množinu proměnných (variables) nabývající hodnoty z příslušné domény. Nad množinami proměnných jsou potom definována omezení (constraints). Omezení je relace určující, které hodnoty z definičního oboru mohou proměnné současně nabývat. CSP je tedy určeno trojicí (V, D, C), kde X = {x1, …, xn} je konečná množina doménových proměnných, D = D1 … Dn je konečná množina domén (doména Dk je množina hodnot, které může proměnná xk nabývat) a C = {c1, …, cn} je konečná množina omezení. Omezení c definováno na proměnných x1, …, xn je splněno (satisfied), pokud pro hodnoty d1 ∊ D1, …, dk Dk platí (d1, …, dk) C. V opačném případě říkáme, že omezení není splněno (unsatisfied). Úkolem je nalézt hodnotu pro každou proměnnou tak, aby byla splněna všechna omezení. Úplné ohodnocení (přiřazení) proměnných znamená, že všechny proměnné mají přiřazenu hodnotu. V částečném ohodnocení proměnných mají některé proměnné přiřazenu hodnotu. Řešení CSP je úplné ohodnocení proměnných splňující všechna omezení. Příklad 1. Uvažujme proměnné A, B, jejichž doménami jsou množiny DA = {0, 1, 2}, DB = {1, 2}. Dále uvažujme omezení c, které je implicitně zadané jako c je A B a problém splňování podmínek ({A, B}, {DA, DB}, {c}). Omezení je splněno pro dvojice (0, 1), (0, 2), (1, 2), (2, 1), není splněno pro dvojice (1, 1), (2, 2).

2.2 Optimalizační problém s omezujícími podmínkami V CSP jsou všechna řešení rovnocenná, což vždy nemusí být nejlepší přístup. Při řešení reálných problémů často hledáme nejlepší řešení vzhledem k určitému kritériu [Dech03, Rud10]. Pro řešení těchto problémů byl zaveden optimalizační problém s omezujícími podmínkami (Constraint Satisfaction Optimalization Problem – dále jen CSOP). CSOP je CSP rozšířené o objektivní funkci. Sol je množina řešení a obj: Sol → W je objektivní funkce. Objektivní funkce je tedy funkce z množiny všech řešení CSP do úplně uspořádané množiny W. Objektivní funkce umožňuje porovnat kvalitu jednotlivých řešení. Hledáme takové řešení pro CSOP, že objektivní funkce je optimální např. maximální

3

nebo minimální. V praxi je často nalezení optimálního řešení časově velmi náročné a cílem je nalezení sub-optimálního řešení, které se blíží optimálnímu řešení.

2.3 Optimalizační problém s měkkými podmínkami CSP může být příliš podmíněný nebo špatně definovaný, potom můžeme požadovat nalezení řešení, které je v jistém smyslu nejlepší (splňuje nejvíce daných omezení). Měkká omezení jsou omezení, u kterých předpokládáme, že je nebude možné všechny splnit. Naopak pevná omezení musejí být vždy splněna. Nejčastěji používaným přístupem pro řešení problému s měkkými podmínkami je CSP s váhami, kde má každé omezení přidělenu svou váhu, která určuje jak je splnění kterého omezení důležité. Váha a omezení tvoří dvojici (c, w(c)), potom řešíme problém trojice (V, D, Cw). Snažíme se minimalizovat součet vah nesplněných omezení, který určuje úroveň splnění. Úroveň splnění [Rud10] je funkce na množině přiřazení ω(θ) = ∑θ⊨¬c w(c). Speciálním případem CSP s váhami je MAX-CSP, kde mají všechna omezení přiřazenu stejnou váhu. Váha je rovna jedné a účelem je maximalizace počtu splněných omezení Příklad 2. Jsou dána tři omezení s váhami, úkolem je přidělit výuku Matematiky I a Matematiky II tak, aby byl součet nesplněných omezení minimální. @ znamená hodnotu dané váhy c1: Matematika I < Matematika II @ 7 c2: Matematika I in 3..4 @ 3 c3: Matematika II in 1..3 @ 2 Při přiřazení σ = {Matematika I/1, Matematika II/2} odpovídá úroveň splnění σ součtu vah nesplněných omezení, neboli je rovna 3. Při řešení θ = {Matematika I/3, Matematika II/4} je úroveň splnění rovna 2, takže se jedná o lepší řešení. Dalším možným přístupem je pravděpodobnostní CSP, které udává pro každé omezení pravděpodobnost, s jakou omezení náleží do problému [Rud10]. Lze použit i Fuzzy CSP, kde každý prvek přísluší do množiny zadané číslem z intervalu [0, 1]. Fuzzy omezení je relace μ(d1, …, dk) udávající úroveň preference, poté řešíme problém trojice (V, D, Cf), kde Cf je množina fuzzy omezení a V uspořádaná množina proměnných.

2.4 Základní řešící metody Mezi základní řešící metody patří metoda větví a mezí (Branch and Bound search) [Rud10a]. Je to heuristická metoda založená na postupném rozdělování prohledávacího prostoru. Jedná se obecný algoritmus pro hledání optimálních řešení. Prohledávací prostor se rychle zvětšuje s rostoucím počtem proměnných, tato metoda je vhodná pro malé problémy (do 30 úloh).

4

Potřebujeme spočítat hranici rozdělení prostoru. Části stavového prostoru, které dávají horší řešení, než tato hranice již nemusíme prohledávat. Častým způsobem zjišťování hranic je relaxovat (zjednodušit) původní prostor odstraněním některých požadavků a vytvořit tak snadno řešitelný problém. Neexistuje-li řešení pro relaxovaný problém, neexistuje ani řešení pro původní problém. 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ím řešením. Není-li optimální řešení řešením původního problému, udává pak hranici na jeho řešení (původní problém bude mít horší řešení). Pravidla pro větvení jsou taková, že první úroveň má n větví, ve kterých je každá z n úloh rozvrhována jako první. V úrovni k – 1 jsou úlohy j1, …, jk-1 rozvrhovány v pořadí 1, …, k – 1. Máme-li již přiřazenu hodnotu některé proměnné, můžeme využít propagace omezení [Rud10] jsou vyvolány před přiřazováním hodnoty další proměnné. Většinou se přiřazují proměnné, které nejvíce omezují stavoví prostor. Po provedení propagace omezení lze mnohem lépe rozhodnout, kterou proměnnou přiřadit a také kterou hodnotu proměnné přiřadit (snaha o výběr hodnoty, která umožní v budoucnu nejvíce voleb přiřazení).

5

3. Rozvrhování Rozvrhování [Pin05, Rud10a] se obecně zabývá přiřazením množiny entit (jako např. úloh, činností nebo osob) ke zdrojům v čase a prostoru tak, aby byly dodrženy požadavky daného problému a byl maximalizován zisk z naplánování úloh a minimalizovány náklady. Minimalizovat se snažíme časové, peněžní, materiálové, lidské, strojové a další náklady. Maximalizovat se snažíme nejen peněžní zisky, ale také efektivitu výroby, využívání zdrojů a prostorů a další. Zdroj je přitom nějaký prostředek (např. místnost, strojový čas, peníze a pod…), který zpracovává jednotlivé operace a je k dispozici pouze v omezeném množství. Úloha je objekt, který rozvrhujeme a operace (podúloha) je její dílčí část. Rozvrh je 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. V úplném rozvrhu jsou umístěny všechny úlohy ze zadání problému. V částečném rozvrhu některé úlohy umístěny nejsou. Konzistentní rozvrh je úplný rozvrh, ve kterém jsou splněna všechna omezení kladená na zdroje a úlohy. Rostering umísťuje zdroje za daných podmínek do slotů pomocí vzorů (pattern). Roster (rozpis) je seznam jmen lidí, který určuje, kdy a jaké úlohy budou osoby provádět (např. rozpis zdravotních sester).

3.1 Omezení a optimalizační kritéria Mezi používaná omezení patří [Pin05, Rud10a] precedenční podmínky, které určují lineární posloupnost provádění úloh. Např. pro úlohy a, b píšeme a → b, což znamená Sa + pa Sb neboli, že úloha b může nejdříve začínat v čase, kdy už je úloha a dokončena. Dalším omezením je přerušení úlohy (preemptions), při příchodu úlohy s vyšší prioritou je současná úloha přerušena. Vhodnost stroje určuje podmnožinu strojů Mj, na níž lze úlohu j provádět. Omezení na pracovní sílu znamená, že do problému zavedeme další typ zdroje. Stroje mohou potřebovat operátory a úlohy lze provádět jen, jsou-li dostupní. Jde-li o optimalizaci, velmi často se používá optimalizační kritéria pro makespan značený Cmax. Makespan je maximální čas konce úloh a je roven Cmax = max(C1, …, Cn). Minimalizace makespan maximalizuje výkon (throughput) a vede k rovnoměrnému zatížení strojů (load balancing). Dále se optimalizuje zpoždění (lateness), které se značí Lj a vyjadřuje zpoždění úlohy j a je rovno Lj = Cj - dj. Maximální zpoždění se pak značí Lmax a je rovno Lmax = max(L1, …, Ln). Nezáporné zpoždění (tardiness) úlohy j se značí Tj a je rovno Tj = max(Cj – dj, 0). Další optimalizační kritéria jsou cena za skladování, cena za dopravu, robustnost (vyžaduje méně změn), cena za nastavení, cena za pracovní sílu a další.

6

4. Rozvrhování zdravotních sester Vzhledem k [CB10, CHS+10] společenské a ekonomické závažnosti je problém rozvrhování zdravotní sester na směny intenzivně zkoumaným problémem. Ačkoliv první výsledky zkoumání byly zveřejněny před 30 roky, dochází neustále k inovacím. Pořád není známa univerzálně použitelná metoda řešení. Mezi problémy rozvrhování zaměstnanců patří rozvrhování zdravotních sester mezi nejtěžší problémy. Rozvrhování sester se vzhledem ke kladené důraznosti na flexibilitu modelů a obtížnosti optimalizovat řešení stalo atraktivním problémem pro mnoho metod optimalizace. První metody řešení se objevily v 70. letech a byly založeny na matematickém programování. Metody matematického programování garantují nalezení optimálního řešení, ale pro velmi obsáhlý problém, jakým rozvrhování zdravotních sester je, se nedají použít. Při řešení problému rozvrhování zdravotních sester na směny se využívají aproximační, genetické, heuristické a pravděpodobnostní algoritmy. Problém rozvrhování zdravotních sester [CHS+10] zahrnuje rozvržení zdravotních sester na různé směny dne během určitého časového období daného počtem dnů a pro určené oddělení v nemocnici. Ukázka rozvrhu pro 6 sester, 4 druhy směn a na jeden pracovní týden je na Obrázku 4.1. Obrázek 4.1: Ukázka rozvrhu zdravotních sester na směny

Problém, kterým se zabýváme v této práci, vychází ze soutěže nazvané [CHS+10] Nurse Rostering Competition pořádané v roce 2010. Problém je složen z následujících částí: Časová perioda: Vymezuje období, ve kterém vytváříme rozvrh sester, je dána startovním a koncovým datem. Odbornost: Určuje pro danou sestru její odbornost, která vymezuje na které směny může být sestra přiřazena.

7

Směny: Směna je určena svým typem (např. ranní, denní, večerní), dnem a týdnem, ve kterých směna probíhá, časem, kdy směna začíná a kdy končí (z těchto hodnot lze vypočíst dobu trvání směny, jelikož jsou směny brány jako nepřerušený časový úsek), počtem zaměstnanců pracujících na dané směně a požadovanou odborností na každého zaměstnance. Kontrakty: Kontrakt určuje specifické požadavky pro skupinu sester, které k tomuto kontraktu náleží. Sestra může náležet pouze k jednomu kontraktu. Každý kontrakt určuje: počet pracovních dnů za měsíc, kolik dnů v řadě chce sestra pracovat a kolik dnů v řadě chce mít volno, počet pracovních víkendů v řadě, počet pracovních víkendů za měsíc, jestli chce sestra pracovat o víkendu stejné směny, jestli pracuje oba dny víkendu, apod. Poslední údaj určuje, které nežádoucí kombinace směn sestra nechce pracovat. Nežádoucí kombinace směn: Obsahují různé kombinace nežádoucích směn, týkají se buď specifického dne, nebo jsou vztaženy na celé časové období, stejně tak se mohou týkat specifické směny, nebo jsou určeny pro jakoukoliv směnu. Příkladem nežádoucí kombinace směn vztažené na celé období je, že sestra nechce pracovat v řadě noční a ranní směny, nebo naopak požadavek, že sestra nechce mít volný pátek před pracovním víkendem, je ukázkou omezení vázaného na určitou část časové periody. Zaměstnanci: Zdravotní sestra náleží vždy právě k jednomu kontraktu, který specifikuje její osobní požadavky. Do jednoho kontraktu může náležet více sester. Každý kontrakt obsahuje hodnoty omezení, které jsou v něm definované. Preference zaměstnanců: Pro každého zaměstnance existuje možnost, aby kdykoliv během rozvrhovací periody požadoval volný den, nebo volnou směnu. Zaměstnanec má omezený počet možností, kdy volno uplatní.

4.1 Pevná omezení Pevná omezení musí být vždy splněna, abychom dosáhli konzistentního rozvrhu. U problému rozvrhování zdravotních sester je dodržení pevných omezení velmi důležité. Kdyby nebyla dodržena, mohlo by to vést k přepracování zdravotních sester, nebo k nespokojenosti s pracovní dobou, a to by se mohlo promítnout do kvality zdravotních služeb. Stejně tak není možné, aby na směnách zaměstnanci chyběli, nebo jich naopak bylo více, než je požadováno. V Nurse Rostering Competition jsou uvažována následující pevná omezení.

8

Všechny požadované směny jsou přiřazeny: Na každý den a směnu je určený počet zaměstnanců s danou odborností, který musí být splněn. Kdyby nebyl požadovaný počet zaměstnanců splněn, došlo by buď k nedostatečným počtům personálu, nebo naopak k přeplnění. Sestra má přiřazenu maximálně jednu směnu za den: Sestra nemůže mít v jeden den přiřazeny dvě směny, ale může se stát, že sestra slouží směnu, která probíhá během dvou dnů (např. noční směna 22:00 – 06:00), a další den už opět může mít přiřazenu novou směnu.

4.2 Měkká omezení Měkká omezení jsou omezení, u kterých předpokládáme, že nebude možné je všechny splnit. V problému rozvrhování zdravotních sester se používají dva přístupy k měkkým omezením, v prvním jsou všechny váhy rovny jedné a jedná se tedy o maximalizaci počtu splněných omezení. Ve druhém případě mají váhy různé hodnoty, splnění některých omezení je tedy důležitější. Maximální (minimální) počet přiřazení: Určuje maximální a minimální počet přiřazených směn pro jednoho zaměstnance za rozvrhovanou periodu. Maximální (minimální) počet pracovních dnů v řadě: Určuje maximální a minimální počet pracovních dnů v řadě, během kterých může být danému zaměstnanci přiřazena směna. Maximální (minimální) počet volných dnů v řadě: Určuje maximální a minimální počet volných dnů v řadě, během kterých nemá zaměstnanec přiřazenu žádnou směnu. Maximální (minimální) počet po sobě jdoucích pracovních víkendů: Určuje maximální a minimální počet přiřazených pracovních víkendů v řadě. Maximální (minimální) počet pracovních víkendů za měsíc: Určuje maximální a minimální počet přiřazených pracovních víkendů během jednoho měsíce. Celý pracovní víkend: Požadavek zaměstnance nato, aby pracoval celý víkend, je-li mu nějaká směna o víkendu přiřazena. Identické směny během víkendu: Sestra požaduje, aby o víkendu pracovala na identických směnách.

9

5. ILOG ILOG je mezinárodní softwarová společnost vlastněná firmou IBM, která vytváří softwarové produkty pro řízení managementu, vizualizaci a optimalizaci. Podporuje programovací jazyky, jako jsou C++, C#, .NET, Java a další. Společnost byla založena roku 1987 v Paříži. Jméno ILOG vzniklo ze zkratky kombinace dvou francouzských slov "Intellience" a "Logiciel", která se dají přeložit jako "Inteligentní software". Firma ILOG vytvořila mnoho produktů, pro tuto práci je nejdůležitějším IBM ILOG CPLEX a jeho verze využívající CP Optimizer, který umožňuje využívat programování s omezujícími podmínkami. IBM ILOG CPLEX je optimalizační software určený pro matematické programování založený na programovacím jazyku OPL (Optimization Programming Language), který vytvořil Pascal Van Hentenryck.

5.1 Programovací jazyk OPL V této kapitole budou popsány základní datové typy využívané v programovacím jazyku OPL, základní funkce a klíčová slova, které jsou pro tuto práci důležité.

5.1.1 Základní datové typy Jedním ze základních datových typů je boolean, který je specifický tím, že se může používat pouze pro doménové proměnné (domain variables). Doménové proměnné se definují jako „dvar datovýTyp názevProměnné“. Použití doménové proměnné a datového typu boolean je „dvar boolean x“. Doménová proměnná datového typu integer s rozmezím hodnot od 0 do 1 má stejný význam, jako bychom použili datový typ boolean. Tato doménová proměnná má tvar „dvar int x in 0..1“ (máli doménová proměnná hodnotu 0, pak je rovna hodnotě false, hodnota rovna 1 odpovídá hodnotě true). Množina se definuje pomocí složených závorek. Uvnitř závorek je definovaný datový typ prvků množiny. Syntax množiny je „{string} NázevMnožiny = …“. Pole může být jednorozměrné, nebo vícerozměrné. Definuje se pomocí hranatých závorek. Dvourozměrné pole typu integer se zapisuje jako „int NázevPole[Řádky][Sloupce] = …“. V jazyku OPL existuje možnost seskupit propojená data a vytvořit z nich n-tici (tuple). Pro definování unikátních identifikátorů se používá slovo key napsané před datovým typem. tuple employee { key int ID; key string name; int payRate; string skill; }

10

5.1.2 Základní funkce a klíčová slova Tato kapitola popisuje klíčová slova a základní funkce používané v programovacím jazyku OPL, která jsou v navrženém modelu použita. using CP: Použitím tohoto klíčového slova specifikujeme, že model musí být řešen pomocí stroje využívajícího programování s omezujícími podmínkami. execute: Klíčové slovo označující začátek bloku pro předzpracování nebo následné zpracování dat. Využívá se, např. pro stanovení doby běhu programu, výpis výsledných dat a další. Jeho použití je ukázáno v příkladu 5.2 na řádcích 10 až 12. maxl: Programovací jazyk OPL obsahuje mnoho předdefinovaných funkcí. Jednou z nich je funkce maxl, která navrací maximální hodnotu prvku ze seznamu typu integer nebo float. Syntaxe je „int maxl(int,...)“ resp. “float maxl(int,...)”. sum: Na hodnotách typu integer a float může být použit operátor pro sumarizaci. Zapisuje se následovně „sum (Kvantifikátory) Výraz“. Využití tohoto klíčového slova je ukázáno na Příkladu 5.2 na řádcích 20 a 21. forall: Klíčové slovo pro specifikaci omezení. Postupně prochází určené kvantifikátory. Zapisuje se následovně „forall (Kvantifikátory) Omezení“. Jeho použití je ukázáno v příkladu 5.2 na řádcích 18 až 21. subject to: Klíčové slovo definující začátek bloku programu, ve kterém jsou napsána omezení. Objektivní funkce bývá umístěna před tímto blokem. Ukázka jeho použití je v příkladu 5.2 na řádcích 17 až 22. minimize/maximize: Optimalizační instrukce vyžadující objektivní funkci typu integer nebo float. Umísťují se před blok s omezeními (subject to). Jejích úkolem je minimalizace/maximalizace objektivní funkce. Ukázka použití funkce maximize je v příkladu 5.2 na řádcích 14 a 15.

11

V Příkladu 5.2 je ukázkový program [IBM11], který počítá maximální produkci prvků, při chemické reakci. V programu jsou definovány dvě množiny s prvky typu string nazvané “Products“ resp. “Components“, potom je definováno dvourozměrné pole nazvané “demand“, které má 2 řádky a 3 sloupce. Dále jsou definována dvě jednorozměrná pole typu float nazvaná “profit“ resp. “stock“. Doménová proměnná je typu pozitivní float a je nazvaná “production“. Objektivní funkce maximalizuje součin „profit[p] * production[p]“. Omezení napsané v bloku subject to určuje, že „demand[p][c] * production[p] stock[c]“. V bloku execute je použit limitní parametr cp.param.timeLimit, kterým se dá omezit doba běhu programu na námi definovanou dobu (časovou jednotkou je sekunda). Příklad 5.2 01. {string} Products = { "gas", "chloride" }; 02. {string} Components = { "nitrogen", "hydrogen", "chlorine" }; 03. 04. float demand[Products][Components] = [ [1, 3, 0], [1, 4, 1] ]; 05. float profit[Products] = [30, 40]; 06. float stock[Components] = [50, 180, 40]; 07. 08. dvar float+ production[Products]; 09. 10. execute { 11. cp.param.timeLimit = 5; // omezuje čas běhu 12 } // programu na 5 sekund 13. 14. maximize 15. sum(p in Products) profit[p] * production[p]; 16. 17. subject to { 18. forall (c in Components) 19 ProductionConstraints: // název pevného omezení 20. sum(p in Products) demand[p][c] * production[p] <= 21. stock[c]; 22. }

12

6. Navržený model V této kapitole je popsána datová reprezentace použitá v navrženém modelu, ukázky zdrojového kódu a popis vytvořených omezení rozdělených do skupin podle toho, jak jsou implementovány.

6.1 Datová reprezentace Kapitola popisuje datovou reprezentaci použitou v navrženém modelu. Je popsána datová reprezentace zdravotních sester, směn, času, dovolených a volných směn. Jsou také popsány použité doménové proměnné Zdravotní sestry: V řešeném problému se vyskytují sestry vždy z jednoho oddělení a mají dánu jednu odbornost. Každá sestra je zastupována n-ticí, ve které je unikátní parametr ID. Další parametry jsou číslo kontraktu (contractID) a dovednost sestry (skill). tuple nurse { key int ID; int contractID; string skill; }

Směny: Obecně pracujeme se směnami různé délky. V řešeném problému pracujeme s 8 hodinovými směnami. Jsou možné čtyři druhy směn: ranní (Early), denní (Day), večerní (Late) a noční (Night). Trvání směn je zobrazeno v Tabulce 6.1.

Typ směny Early Day Late Night

Tabulka 6.1 Začátek směny 06:30:00 08:30:00 14:30:00 22:30:00

Konec směny 14:30:00 16:30:00 22:30:00 06:30:00

Každá směna je určena n-ticí obsahující klíčové atributy typ směny (shiftType), den (day) a týden (week), které každou směnu jednoznačně určí. Další parametry jsou začátek směny (startTime), konec směny (endTime), pořadové číslo dne vzhledem k rozvrhovací periodě (dayNum) a požadovaný počet sester na směnu (required). Je využívána též proměnná pro počet směn (NbOfShifts). tuple shift { key string shiftType; key string day; key int week; int dayNum; int required; }

13

Čas: Pro reprezentaci času se využívají proměnné dny týdne (weekDays), týdny (Weeks), pořadová čísla dnů (DayNumbers). Dále je definovaný počet dnů (NbOfDays) a počet týdnů (NbOfWeeks). {string} WeekDays = ...; {int} Weeks = ...; {int} DayNumbers = ...; int NbOfDays = ...; int NbOfShifts = ...; int NbOfWeeks = ...;

Dovolené a volné směny: Pro reprezentaci dovolených (Vacations) a volných směn (ShiftVacations) jsou použita dvojrozměrná pole, kde každý řádek reprezentuje jednu sestru a sloupec jednu směnu. Pole jsou datového typu integer a nabývají hodnoty 0 nebo 1 (1 znamená volný den/směnu). int Vacations[Nurses][Shifts] = ...; int ShiftVacations[Nurses][Shifts] = ...;

Doménové proměnné: Nejdůležitější doménová proměnná se používá pro přiřazení sester na směny (NurseAssignments) a je určena sestrou a směnou. Může nabývat hodnoty 0 nebo 1 (0 znamená, že sestra nemá danou směnu přiřazenu, 1 znamená, že směnu přiřazenu má). Dále používáme doménové proměnné, které se vyskytují v objektivní funkci. Hodnota těchto doménových proměnných se zvýší, dojde-li k porušení měkkého omezení. Jsou to doménové proměnné pro porušení dovolené (VacationViolation), porušení volné směny (VacationShiftViolation), nežádoucí kombinace směn (např. LateDayViolation a další), počet přiřazení za měsíc (max/minNumAssignments), maximální počet pracovních víkendů v řadě (MaxNumWorkingWeekendsInRow2/3), počet pracovních dnů v řadě (maxNumWorkDaysInRow) a pro maximální počet volných dnů v řadě (MaxNumFreeDaysInRow) dvar dvar dvar dvar dvar dvar dvar dvar dvar dvar

int int int int int int int int int int

NurseAssignments[Nurses][Shifts] in 0..1; VacationViolation[Nurses] in 0..NbOfDays; VacationShiftViolation[Nurses] in 0..NbOfDays*NbOfShifts; LateDayViolation[Nurses] in 0..NbOfDays; MaxNumAssignmentsViolation[Nurses] in 0..NbOfDays; MinNumAssignmentsViolation[Nurses] in 0..NbOfDays; MaxNumWorkingWeekendsInRow3[Nurses] in 0 .. NbOfWeeks; MaxNumWorkingWeekendsInRow2[Nurses] in 0 .. NbOfWeeks; MaxNumWorkDaysInRow[Nurses] in 0..NbOfDays; MaxNumFreeDaysInRow[Nurses] in 0..NbOfDays;

6.2 Pevná omezení Tato kapitola popisuje navržená pevná omezení použitá při řešení problému. Pro každé z omezení je nejprve uveden slovní popis a následně syntaxe daného omezení. U prvních dvou níže popsaných omezení bylo požadováno, aby byla pevná. Další čtyři popsaná omezení měla být realizována jako měkká omezení, ale práce navrhuje jejich řešení pouze prostřednictvím pevných omezení.

14

Všechny požadované směny jsou přiřazeny: Pro každou směnu s, musí platit, že počet přiřazení sester n na danou směnu je roven hodnotě requirement určující požadovaný počet zaměstnanců na směnu. forall(s in Shifts) RequiredNumberOfNursesPerShiftConstraints: sum(n in Nurses) NurseAssignments[n][s] == s.requirement;

(P1)

Sestra má přiřazenu maximálně jednu směnu za den: Pro každou zdravotní sestru n a všechny dny rozvrhovací periody dn musí platit, že počet přiřazení dané sestry za den je menší nebo roven jedné. forall(n in Nurses, dn in DayNumbers) OnlyOneShiftPerDayConstraints: sum(s in Shifts: s.dayNum == dn) NurseAssignments[n][s] <= 1;

(P2)

Sestra nepracuje Day-Early-Day směny v řadě: Pro každou zdravotní sestru n a pro všechny dny dn, kromě posledních dvou dnů platí, že počet přiřazení dané sestry ve třech po sobě jdoucích dnech na směnách Day, Early, Day se nesmí rovnat 3. forall(n in Nurses, dn in DayNumbers: dn < 27) DayEarlyDayInRowConstraints: (sum(s in Shifts: s.dayNum == dn && s.shiftType == "Day") NurseAssignments[n][s] + sum(ss in Shifts: ss.dayNum == dn + 1 && ss.shiftType == "Early") NurseAssignments[n][ss] + sum(sss in Shifts: sss.dayNum == dn + 2 && sss.shiftType == "Day") NurseAssignments[n][sss]) != 3; (P3)

Sestra pracuje oba dny víkendu a na stejných směnách: Pro všechny zdravotní sestry n, všechny týdny w a všechny směny s, které probíhají v sobotu a neděli, musí platit, že počet přiřazení sestry za oba dny na stejných směnách se musí rovnat nule nebo dvěma. Tím je zajištěno, že sestra pracuje oba dny víkendu nebo žádný. forall(n in Nurses, w in Weeks, s in Shifts: s.day == "Saturday" && s.week == w, ss in Shifts: ss.day == "Sunday" && ss.week == w && s.shiftType == ss.shiftType) WorkAllWeekendSameShiftsContraints: ((NurseAssignments[n][s] + NurseAssignments[n][ss] == 0) || (NurseAssignments[n][s] + NurseAssignments[n][ss] == 2)); (P4)

Sestra nemá volný pátek před pracovním víkendem: Pro všechny zdravotní sestry n, všechny víkendy w a všechny směny s, které probíhají v pátek, musí platit, že počet přiřazení sestry za pátek, sobotu a neděli se nesmí rovnat dvěma. Tím zajistíme, že sestra nemá volný pátek před pracovním víkendem. Toto omezení je závislé na předchozím pevném omezení, neboť přímo počítá s tím, že sestra pracuje buď oba dny víkendu, nebo ani na jednom z nich. 15

forall(n in Nurses, w in Weeks, s in Shifts: s.day == Friday" && s.week == w) FreeFridayBeforeWorkingWeekendConstraints: sum(ss in Shifts: ss.week ==w && (ss.dayNum - s.dayNum) <= 2 && 0 <= (ss.dayNum - s.dayNum)) NurseAssignments[n][ss]!= 2; (P5)

Sestra pracuje minimálně dva dny v řadě: Pro všechny sestry n s číslem kontraktu rovným ContractID platí, že trojnásobná hodnota počtu přiřazení za prostřední den zmenšená o počet přiřazení sestry za předchozí a následující dny se nesmí rovnat třem. Toto musí platit pro všechny dny, kromě prvního dne, proto má omezení dvě části, druhá část omezuje, aby sestra pracovala první den a následující den byl volný. forall(n in Nurses: n. ContractID) forall(dn in DayNumbers: dn > 1 && dn < 28) MinimalTwoWorkDaysInRowConstraints: (sum(s in Shifts: s.dayNum == dn) 3*NurseAssignments[n][s] sum(ss in Shifts: ss.dayNum == dn - 1 || ss.dayNum NurseAssignments[n][ss]) != 3; forall(n in Nurses: n. ContractID) forall(dn in DayNumbers: dn == 1) MinimalTwoWorkDaysInRowFirstDayConstraints: sum(s in Shifts: s.dayNum == dn) NurseAssignments[n][s]*3 sum(ss in Shifts: ss.dayNum == dn + 1) NurseAssignments[n][ss] != 3;

== dn + 1) (P6a)

(P6b)

6.3 Měkká omezení Tato kapitola popisuje měkká omezení použitá při řešení problému. U každého z omezení je nejprve uveden slovní popis a následně syntaxe daného omezení. Práce neřeší všechna omezení obsažená v řešeném problému, ale pouze vybraná z nich. Dovolené: Pro všechny zdravotní sestry n a všechny směny s, kterým odpovídá prvek pole Vacations s hodnotou 1 se do doménové proměnné VacationViolation přičte hodnota doménové proměnné NurseAssignments. Doménová proměnná VacationViolation indikuje pro každou sestru počet porušení dovolených (nemá-li sestra v danou směnu volno, zvyšuje se hodnota proměnné VacationViolation o jedna). forall(n in Nurses) VacationViolation[n] == sum(s in Shifts: Vacations[n][s] == 1) NurseAssignments[n][s];

16

(M1)

Volné směny: Omezení má stejnou syntaxi jako předchozí omezení, ale používá dvourozměrné pole VacationShiftViolation a doménovou proměnnou ShiftVacations. forall(n in Nurses) VacationShiftViolation[n] == sum(s in Shifts: ShiftVacations[n][s] == 1) NurseAssignments[n][s];

(M2)

Nežádoucí kombinace dvou směn: Pro všechny zdravotní sestry n a všechny směny s typu Late resp. ss typu Day ve dvou po sobě jdoucích dnech se do proměnné Shift1Shift2Violation přičte výsledek funkce maxl z počtu přiřazení sestry na těchto směnách zmenšený o jedna a nuly. Hodnota dané proměnné se zvyšuje, má-li sestra obě procházené směny přiřazeny. Funkci maxl musíme použít kvůli případu, kdy by sestra neměla přiřazenu ani jednu ze směn. Toto omezení má více forem označených dodatkovými písmeny a až f, která znamenají omezení dvojic směn Late-Day, Late-Early, Night-Early, Night-Day, Day-Night a Late-Night. forall(n in Nurses) Shift1Shift2Violation[n] == sum(s in Shifts: s.shiftType == "Shift1" && s.dayNum < 28, ss in Shifts: ss.dayNum == s.dayNum + 1 && ss.shiftType == "Shift2") maxl(0, (NurseAssignments[n][s] + NurseAssignments[n][ss] – 1)); (M3)

Maximální počet přiřazení za měsíc: Pro všechny zdravotní sestry n a číslem kontraktu rovným ContractID se do proměnné MaxNumAssignmentsViolation přičítá výsledek funkce maxl z rozdílu počtu přiřazení za měsíc zmenšeného o maximální počet přiřazení za měsíc (MaxNumAssignments) a nuly. forall(n in Nurses: n.contractID == ContractID) MaxNumAssignmentsViolation[n] == maxl(0, (sum(s in Shifts) NurseAssignments[n][s]) – MaxNumAssignments);

(M4)

Minimální počet přiřazení za měsíc: Pro všechny zdravotní sestry n a číslem kontraktu rovným ContractID se do proměnné MinNumAssignmentsViolation přičítá výsledek funkce maxl z rozdílu minimálního počtu přiřazení za měsíc (MinNumAssignments) zmenšeného počet přiřazení za měsíc a nuly. forall(n in Nurses: n.contractID == ContractID) MinNumAssignmentsViolation[n] == maxl(0, MinNumAssignments - (sum(s in Shifts) NurseAssignments[n][s]));

17

(M5)

Maximální počet pracovních dnů v řadě: Pro všechny zdravotní sestry n s číslem kontraktu rovným ContractID a pro všechny série dnů se do proměnné MaxNumWorkDaysInRow přičte výsledek funkce maxl z rozdílu počtu přiřazení za danou sérii dnů zmenšenou o maximální počet pracovních dnů v řadě (MaxNumWorkDaysInRow) a nuly. Procházíme vždy o jeden jen více, než je hodnota MaxNumWorkDaysInRow. forall(n in Nurses: n.contractID == ContractID) MaxNumWorkDaysInRow[n] == sum(dn in DayNumbers: dn < (NbOfDays – MaxNumWorkDaysInRow - 1)) maxl(0, (sum(s in Shifts: (s.dayNum - dn) <= MaxNumWorkDaysInRow && 0 <= (s.dayNum - dn)) NurseAssignments[n][s]) - MaxNumWorkDaysInRow); (M6)

Maximální počet volných dnů v řadě: Syntaxe omezení je velmi podobná předchozímu omezení, rozdíl je v tom, že výsledek funkce maxl se určí z jedničky zmenšené o počet přiřazení za danou sérii dnů a nuly. forall(n in Nurses: n.contractID == ContractID) MaxNumFreeDaysInRow[n] == sum(dn in DayNumbers: dn < (NbOfDays – MaxNumFreeDaysInRow – 1)) maxl(0, 1 - (sum(s in Shifts: (s.dayNum - dn) <= MaxNumFreeDaysInRow && 0 <= (s.dayNum - dn)) NurseAssignments[n][s])); (M7)

Omezení maximálního počtu pracovních víkendů v řadě má dva typy, jedno omezuje maximální počet pracovních víkendů na 3 a druhé na 2. Každé omezení má odlišnou syntaxi, proto jsou omezení napsána zvlášť. Maximální počet pracovních víkendů v řadě omezen na 3: Pro všechny zdravotní sestry n s číslem kontraktu rovným ContractID se do proměnné MaxNumWorkingWeekendsInRow3 přičte výsledek funkce maxl z počtu přiřazení dané sestry za měsíc a nuly. Stačí sečíst počty přiřazení za soboty, protože se počítá s platností pevného omezení P4. forall(n in Nurses: n.contractID == ContractID) MaxNumWorkingWeekendsInRow3[n] == maxl(0, (sum(s in Shifts: s.day == "Saturday") NurseAssignments[n][s]) - 3);

(M8)

Maximální počet pracovních víkendů v řadě omezen na 2: Pro všechny zdravotní sestry n s číslem kontraktu rovným ContractID se do proměnné MaxNumWorkingWeekendsInRow2 přičte výsledek funkce maxl z počtu přiřazení na směny dané sestry za tři po sobě jdoucí soboty zmenšený o dva a nuly.

18

forall(n in Nurses: n.contractID == ContractID) MaxNumWorkingWeekendsInRow2[n] == sum(w in Weeks: w < 3) maxl(0, (sum(s in Shifts: s.day == "Saturday" && w <= s.week && s.week <= (w + 2)) NurseAssignments[n][s] - 2));

(M9)

Objektivní funkce: Níže je ukázka objektivní funkce používané v navrženém modelu, která se zapisuje před blok Subject to. Objektivní funkce je zapsána bez vah. Pokud jsou hodnoty vah jednotlivých omezení různé od nuly, je hodnota příslušné doménové proměnné vynásobena ještě hodnotou dané váhy. minimize sum(n in Nurses) VacationViolation[n] + VacationShiftViolation[n] + LateDayViolation[n] + MaxNumAssignmentsViolation[n] + MinNumAssignmentsViolation[n] + MaxNumWorkDaysInRow[n] + MaxNumFreeDaysInRow[n] + LateEarlyViolation[n] + NightEarlyViolation[n] + NightDayViolation[n] + DayNightViolation[n] + LateNightViolation[n]);

19

7. Experimentální výpočty Tato kapitola popisuje experimentální výpočty pro čtyři datové sady [CHS+10], týkající se rozvrhování zdravotních sester na směny. Jednotlivé sady se jmenují sprint, sprint_late, sprint_hidden a sprint_hint. Datové sady se liší obtížností a rozsahem. První tři datové sady obsahují každá 10 instancí, poslední zmíněná sada obsahuje 3 instance. Přímé porovnání výsledků, které práce nabízí a výsledků soutěže, ze kterých práce čerpá, bohužel není možné. Práce řeší pouze vybraná omezení, neřeší omezení minimálního počtu pracovních dnů v řadě s hodnotou jinou než dva, minimální počet volných dnů v řadě, minimální počet pracovních víkendů v řadě a omezení, že sestra nepracuje noční směnu před pracovním víkendem.

7.1 Popis datových sad Tato kapitola ukazuje rozsah jednotlivých datových sad. U každé datové sady je uveden počet typů směn, kontraktů, zdravotních sester, nežádoucích kombinací směn, dovolených, volných směn a celkový počet použitých typů omezení (počet typů omezení náležejících do kontraktu). Mají-li jednotlivé instance rozdílné počty omezení, jsou v tabulce uvedeny všechny jejich možnosti (např. je-li uvedeno v buňce pro Dovolené 0, 100, znamená to, že se vyskytovaly instance, které měli 0 definovaných dovolených, ale také instance, které měli 100 dovolených). Kapitola má za účel poukázat na rozdílnou náročnost řešení jednotlivých datových sad. Počty omezení jsou uvedeny v Tabulce 7.1

Datové sady Typy směn Kontrakty Zdravotní sestry Nežádoucí kombinace směn Dovolené

Tabulka 7.1: rozsah datových sad sprint sprint_late sprint_hidden 4 3, 4 3, 4 4 3 3 10 10 10

sprint_hint 4 3 10

3

0, 4, 8

4, 8

0, 8

100

0, 100

100

Volné směny

50

0, 39, 50

Typy omezení

7

13

100, 150, 200, 250 50, 70, 100, 120 14

20

50 13

7.2 Řešení datových sad V kapitole jsou výsledky řešení jednotlivých datových sad. Pro každou datovou sadu je předložena tabulka s řešením (počet porušení jednotlivých omezení) a ukázka jednoho z výsledných rozvrhů. Výpočet probíhal u každé z instancí 180 sekund (do této doby dochází k ustálení hodnoty objektivní funkce) na počítači AMD Athlon(tm) 64 X2 dual Core Processor 3800+ 1.99GHz, 1,00 GB RAM s operačním systémem Microsoft Windows XP Home Edition Verze 2002. Jedná se o deterministický výpočet, proto je řešení vždy stejné. Řešení datové sady sprint je popsáno v Tabulce 7.2. Znak ∑ označuje hodnotu objektivní funkce, hodnoty buněk M1 až M7 označují míru porušení jednotlivých měkkých omezení popsaných v kapitole 6.3. Tato datová sada má hodnoty všech vah rovny jedné, proto nejsou váhy v tabulce uvedeny. Ukázka rozvrhu datové sady sprint01 je na Obrázku 7.1.

∑ M1 M2 M3 M4 M5 M6 M7

01. 65 33 1 0 30 0 1 0

02. 68 31 3 0 32 0 2 0

Tabulka 7.2: řešení datové sady sprint 03. 04. 05. 06. 07. 69 72 67 64 65 38 37 31 31 30 2 0 1 3 1 0 0 0 0 0 28 34 32 30 34 0 0 0 0 0 1 1 3 0 0 0 0 0 0 0

08. 64 31 1 0 30 0 2 0

Obrázek 7.1: výsledný rozvrh pro instanci sprint01

21

09. 66 33 1 0 32 0 0 0

10. 50 21 0 0 28 0 1 0

Výsledky řešení datové sady sprint_late jsou popsány v Tabulce 7.3. Instance sprint_late02 se od ostatních instancí liší tím, že má pouze tři typy směn. Datová sada sprint_late má hodnoty vah různé. Je-li hodnota váhy rovna jedné, pak není váha v tabulce uvedena, je-li větší než jedna, pak je v tabulce uveden součin váhy a hodnoty počtu porušení měkkého omezení. Není-li omezení v instanci použito, je v tabulce místo hodnoty porušení měkkého omezení uveden znak „-„. Ukázka rozvrhu datové sady sprint_late01 je na Obrázku 7.2.

∑ M1 M2 M3a M3b M3c M3d M3e M3f M4 M5 M6 M7 M8

01. 48 37 0 1 0 0 0 0 0 9 0 0 0 1

02. 28 28 0 0 0 0 0 0 0 0

Tabulka 7.3: řešení datové sady sprint_late 03. 04. 05. 06. 07. 08. 60 69 65 45 36 0 45 38 35 28 36 3 1 4 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 11 3*10 22 15 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

09. 0 0 0 0 0 0

Obrázek 7.2: řešení výsledný rozvrh pro instanci sprint_late01

22

10. 31 31 0 0 0 0 0 0

Výsledky řešení datové sady sprint_hidden jsou popsány v Tabulce 7.4. Instance s pořadovými čísly 01, 02, 06, 07 mají tři typy směn, ostatní instance mají 4 typy směn. Datová sada sprint_hidden má hodnoty vah různé. Ukázka rozvrhu datové sady sprint_hidden01 je na Obrázku 7.3.

∑ M1 M2 M3a M3b M3c M3d M3e M3f M4 M5 M6 M7 M8 M9

01. 37 30 3 0 0 0 3 0 0 0 0 1

Tabulka 7.4: řešení datové sady sprint_hidden 02. 03. 04. 05. 06. 07. 08. 17 82 77 57 111 60 126 17 67 48 44 62 60 90 0 0 2 3 10 0 4 1 1 0 1 0 1 3 1 2 0 3 0 0 1 0 2 0 2 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 9 21 7 5*7 0 5*5 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 -

09. 204 92 2 0 3 1 1 0 0 5*21 0 0 0 -

10. 145 99 4 0 2 0 0 0 0 5*8 0 0 0 -

Obrázek 7.3: výsledný rozvrh pro instanci sprint_hidden01

Výsledky řešení datové sady sprint_hint jsou popsány v Tabulce 7.5. Datová sada sprint_hidden má hodnoty vah různé. Ukázka rozvrhu datové sady sprint_hint01 je na Obrázku 7.4. 23

Tabulka 7.5: řešení datové sady sprint_hint 01. 02. 03. 92 40 34 ∑ M1 39 31 31 M2 1 0 0 M3a 0 0 M3b 7*1 0 M3c 0 0 M3d 0 0 M3e 1 0 M3f 0 0 M4 3*15 3*3 3*1 M5 0 0 0 M6 0 0 0 M7 0 0 0 M8 0 0 0 Obrázek 7.4: výsledný rozvrh pro instanci sprint_hint01

24

7.3 Závislost doby výpočtu na kvalitě řešení Tato kapitola ukazuje, po jaké době výpočtu nalezneme řešení a jak se s přibývajícím časem, kdy probíhá výpočet, zlepšuje kvalita řešení. Každé řešení předložené v předchozí kapitole bylo vyřešeno do 180 sekund. V této kapitole jsou pro každou datovou sadu vybrány tři instance a uveden graf (na ose x je čas, na ose y hodnota objektivní funkce) ukazující zlepšování kvality řešení v čase. Na přiloženém CD jsou uvedeny grafy pro všechny řešené instance. Řešení datové sady sprint, instancí sprint01, sprint05 a sprint10 probíhalo 300 sekund. V grafu 7.1 je ukázáno, jak docházelo ke zlepšování hodnoty objektivní funkce s přibývajícím časem. Graf 7.1: Závislost času výpočtu na kvalitě řešení tří instancí datové sady sprint

Řešení datové sady sprint_late, instancí sprint_late01, sprint_late05, sprint_late10 probíhaly 300 sekund. V grafu 7.2 je ukázáno, jak docházelo ke zlepšování hodnoty objektivní funkce s přibývajícím časem.

25

Graf 7.2: Závislost času výpočtu na kvalitě řešení tří instancí datové sady sprint_late

Řešení datové sady sprint_hidden instancí sprint_hidden01, sprint_hidden05 a sprint_hidden10 probíhaly 300 sekund. V grafu 7.3 je ukázáno, jak docházelo ke zlepšování hodnoty objektivní funkce s přibývajícím časem. Graf 7.3: Závislost času výpočtu na kvalitě řešení tří instancí datové sady sprint_hidden

26

Řešení datové sady sprint_hint instancí sprint_hint01, sprint_hint05 a sprint_hidden10 probíhaly 300 sekund. V grafu 7.3 je ukázáno, jak docházelo ke zlepšování hodnoty objektivní funkce s přibývajícím časem. Graf 7.3: Závislost času výpočtu na kvalitě řešení tří instancí datové sady sprint_hint

27

8. Závěr V rámci práce byl prezentován problém rozvrhování zdravotních sester na směny. Komponenty tohoto problému byly diskutovány nejprve z teoretického hlediska, pak byly popsány datové instance řešené v Nurse Rostering Competition a jejich řešené části. Byly popsány všechny vybrané pevné a měkké omezení a pro každé z omezení byl uveden slovní popis. Byl vytvořen vlastní model řešení vybraných instancí v programovacím jazyku OPL, který se skládal z datové reprezentace a omezujících podmínek. Byly implementovány vlastní pevná a měkká omezení. Měkká omezení byla součástí objektivní funkce. Hodnota objektivní funkce byla minimalizována. Pro všechny instance datových sad byl proveden výpočet řešení a byly ukázány jeho výsledky a ukázka výsledného rozvrhu. K řešení byl použit produkt firmy ILOG nazvaný IBM ILOG CPLEX a jeho verze využívající CP Optimizer, který umožňuje využívat programování s omezujícími podmínkami. Dále byly pro vybrané instance uvedeny grafy, které ukazují zlepšování hodnoty objektivní funkce v čase až do doby, kdy dochází k ustálení její hodnoty. Na přiloženém CD jsou uvedeny grafy pro všechny řešené instance. V rámci budoucí práce by bylo vhodné provést rozsáhlejší experimenty. Bylo by zajímavé rozšířit počet řešených datových sad a implementovat další omezení. Budoucí práce by také mohla směřovat k vytvoření snadno použitelného softwaru, který by po zadání vstupních dat generoval potřebné rozvrhy a zároveň je vyobrazoval.

28

Literatura [BLN01]

C. Baptiste, P. LePape, W. Nuijten. Constraint-based scheduling: applying constraint programming to scheduling problems. Kluwer Academic Publishers, 2001.

[CHS+10] Patrick De Causmaecker, Stefaan Haspeslagh, Andrea Schaerf, Martin Stolevik. First International Nurse Rostering Competiton. 2010. [cit. 2011-0424] URL http://www.kuleuven-kortrijk.be/nrpcompetition/ [CB10]

Patrick De Causmaecker, Greet Vanden Berghe. A categorization of nurse rostering problem. 2010, [cit. 2011-04-26] URL http://www.springerlink.com/content/a821277755438620/fulltext.pdf

[IBM11]

IBM corporation. Documentation OPL_Studio. 2011. [cit. 2011-04-28]

[Pin02]

Michael Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice Hall, second edition, 2002.

[Pin05]

Michael Pinedo. Planning and Scheduling in Manufacturing and Services. Springer, 2005.

[Dech03] Rina Dechter. Constraint processing. Morgan Kaufmann publishers, 2003. [Rud10]

Hana Rudová. Omezující podmínky. Učební materiály k předmětu PA163 Programování s omezujícími podmínkami, 2010. [cit. 2011-03-12] URL http://is.muni.cz/el/1433/podzim2010/PA163/

[Rud10a] Hana Rudová. Rozvrhování. Učební materiály k předmětu PA167 Rozvrhování, 2010. [cit. 2011-03-20] URL http://www.fi.muni.cz/~hanka/rozvrhovani/

29

Příloha A Obsah přiloženého CD Přiložené CD obsahuje jednotlivé složky, ve kterých jsou zdrojové kódy pro jednotlivé datové sady a jejich instance, textové zadání datových sad, výsledky řešení datových sad. Dále jsou uvedeny zdrojové kódy pomocných programů využitých v práci, jako je parser na vytváření rozvrhů (pro 3 a 4 typy směn) a parser pro převod dovolených a volných směn do příslušného formátu využívaného v navrženém modelu. CD obsahuje také grafy závislosti času výpočtu na kvalitě řešení pro všechny řešené instance. Komponentou CD je i vlastní text práce ve formátech portable data format (pdf) a ve formátu .doc.

30

Příloha B Popis textového zadání Šablona pro textová zadání, která byla použita, je popsána níže. Booleanová hodnota je 0 nebo 1 (hodnota 0 = FALSE, hodnota 1 = TRUE), int+ znamená kladný pozitivní integer, proměnná stav může nabývat hodnot 0 nebo 1 (0 = omezení je pasivní, 1 = omezení je aktivní). Jestliže položka navazuje na jinou položku, používá se velké písmeno. Např. typ skill(s) pro ShiftType patří pod SHIFT_TYPES a je určen položkou „Skill‟, která je typem „SKILLS.Skill‟. Znak procento, %, se používá v textové šabloně k indikaci položek náležících pod “rodičovskou” položku, která je zapsána pomocí velkých písmen. Všechny řádky začínající znakem „%‟ budou nahrazeny daty z datových sad. SCHEDULING_PERIOD % ID <string>, % StartDate , % EndDate , SKILLS = n1 % Skill <string>; SHIFT_TYPES = n2 % ID <string>, % Descriptions <string>, % StartTyme , % EndTime , % NumberOfRequiredSkills , % RequiredSkill <SKILLS.Skill>; CONTRACTS = n3 % ID <string>, % Description <string>, % SingleAssignmentsPerDay (on | weight) ( | ), % MaxNumAssignments (on | weight | value) ( | | ), % MinNumAssignments (on | weight | value) ( | | ), % MaxConsecutiveWorkingDays (on | weight | value) ( | | ), % MinConsecutiveWorkingDays (on | weight | value) ( | | ), % MaxConsecutiveFreeDays (on | weight | value) ( | | ), % MinConsecutiveFreeDays (on | weight | value) ( | | ), % MaxConsecutiveWorkingWeekengs (on | weight | value) ( | | ), % MinConsecutiveWorkingWeekengs (on | weight | value) ( | | ),

31

% WeekengDefinition <Weekend>, % CompleteWeekends (on | weight) ( | ), % Ident.ShiftTypesDuringWeekend (on | weight) ( | ), % NoNightShiftsBeforeWorkingWeekend (on | weight) ( | ), % TwoFreeDaysAfterNightShifts (on | weight) ( | ), % AlternativeSkillCategory (on | weight) ( | ), % NumberOfUnwantedPatterns , % UnwantedPatterns <Patterns.ID>; PATTERNS = n4; % ID <string> % Weight , % NumberOfShiftTypes , % ShiftType (<SHIFT_TYPES.ID | WeekDays | None>); EMPLOYEES = n5 % ID <string>, % Name <string> % ContractID , % NumberOfSkills , % EmployeeSkills <SKILLS.Skill>; DAY_OF_WEEK_COVER = n6 % Day < WeekDays >, % Shift <SHIFT_TYPES.ID>, % Preferred ; DAY_OFF_REQUESTS = n7 % EmployeeID < EMPLOYEE.ID>, % Date , % weight ; SHIFT_OFF_REQUESTS = n8 % EmployeeID <EMPLOYEE.ID>, % Date , % ShiftTypeID <SHIFT_TYPES.ID>, % weight ;

32