PKO Piemēri

1. Klātienes darbu organizācija ierobežotu resursu gadījumā
2. (C)VRP(PD)(TW) ... u.c. ... (Miskastes mašīnas, kurjeri, būvgružu konteineri, elektoauto ar uzlādi, utt. ...)
3. Studenti gatavojas eksāmenam - kurus uzdevumus risināt?

Students vakarā atceras, ka viņam rīt ir kontroldarbs, bet viņš neko nav mācījies. Priekš gatavošanās viņam ir atlikušas x minūtes. Viņš zina, ka kontroldarbā būs n uzdevumi katrs par savu tēmu. Tāpat viņš zina katra uzdevuma vērtību v[i] un viņš zina arī laiku t[i], kas nepieciešams, lai sagatavotos katram uzdevumam. Kuriem uzdevumiem viņam ir jāgatavojas, lai iegūtu pēc iespējas labāku vērtējumu? 

1. Šahs - figūru izvietošana, lai neapdraud viena otru (N_Queens)
2. Sanāksmju plānošana

Dots - m telpas offisā, katrā ir ietilpības lielums[i], cilvēku skaits, ko tas var izmitināt; tehniskais aprīkojums - projektora pieejamība p[i] (Jā/Nē), videokonferenču aprīkojuma pieejamība v[i] (Jā/Nē). n darbinieki ar noteiktu darba laiku un iespējamām sanāksmju laika vēlmēm. k projekti, katrs ar sanāksmēm, kurām nepieciešami: obligāto dalībnieku saraksts, neobligāto dalībnieku saraksts, noteikts tehniskais aprīkojums (projektors, videokonference), fiksēts plānotais ilgums sanāksmei. Hard prasības: telpu piešķiršana sapulcēm - telpas sanāksmēm tiek piešķirtas tā, lai telpas ietilpības lielums[i] ir atbilstošs dalībnieku skaitam un nepieciešamais aprīkojums (projektors p[i], videokonference v[i]) ir pieejams. Obligāto dalībnieku grafiki, kas nepārklājas: jāsaplāno sanāksmes, nodrošinot, ka obligātajiem dalībniekiem nav konfliktu un tie noteikti spēs apmeklēt sanāksmi. Sanāksmes ilguma ievērošana: jāievēro fiksēto plānoto sanāksmju ilgumu darba laikā. Unikālo telpu rezervēšana: nodrošiniet, lai katra telpa vienlaikus būtu rezervēta tikai vienai sapulcei. Soft prasības: izvēlēto dalībnieku uzņemšana - plānojiet sanāksmes, ņemot vērā neobligāto dalībnieku pieejamību; sapulces laika vēlmes - pēc iespējas ņemiet vērā darbinieku un projekta sanāksmes laika vēlmes (no rīta, pēcpusdienā). Vienmērīga telpas izmantošana - vienmērīgi sadaliet sapulces visās pieejamajās telpās. Bufera laiks starp sanāksmēm - ideālā gadījumā jāieplāno bufera periodu (piemēram, 15 minūtes) starp secīgām sanāksmēm tajā pašā telpā, lai varētu tās izvēdināt.

1. Dinamiskās darba telpas aizpildīšana

Pamata problēma: ir darba vieta ar dinamisko darba telpu, kur nāk tie darbinieki, kas nevēlas/nevar pilno laiku strādāt klātienē. 80 darbiniekus nepieciešams izvietot 30 vietās tā, lai vismaz trešo daļu no ceturkšņa katrs no trim biznesa centriem (struktūrvienība darbiniekiem) pavadītu klātienē. Jāņem vērā iepriekš saskaņots regulāro sapulču grafiks, kur ir piezīme - klātiene vai online, kur klātienes sapulču laikā darbiniekiem jābūt klātienē, online - attālināti. Ja vienam darbiniekam ir vienāds skaits gan klātienes, gan attālināto sapulču vienā dienas pusē, tad vēlams nodrošināt attālinātu. Vērā jāņem arī darbinieku grafiks - kuros laikos noteikti darbinieki nevarēs būt klātienē. (Iespējams! pievienot arī darbinieku vēlmes - vairāk/mazāk klātieni, labāk rītus/pēcpusdienas, u.tml.) Lai atvieglotu darbinieku transporta grafiku, laiks šeit nozīmē vienu no divām vērtībām - rīts un pēcpusdiena, tā kā cilvēki nevēlēsies braukt uz/no darba vairākkārt vienā dienā vai, piemēram, pastrādāt stundu mājās un tad braukt uz darbu 4 stundas un tad atkal mājās. Sastādītajam grafikam vajadzētu būt pēc iespējas regulāram, ieturot vienu grafiku vai nu katrai nedēļai, vai katrām divām. Sēdvietu iedalījums neeksistē.

1. Produktu sapakošana
2. Chineese Postman Problem (sniega tīrīšana)

Dots orientēts grafs Map=(Intersectrions,Steets), kas reprezentē Latvijas valsts karti kā ceļa tīklu. Intersectrions ir virsotņu kopa (krustojumi) un Streets ir svarotu šķautņu kopa (ielas), kur svari apzīmē ielas garumu. Automašīnai ir dots uzdevums apbraukt kādu Latvijas pilsētu (vai pilsētas daļu) areaToTraverse, kas ir sakarīgs Map apakšgrafs, ievērojot sekojošus nosacījumus: 1. Automašīnai sāk savu ceļu no autoparka, kas var nepiederēt areaToTraverse grafam. Tāpēc automašīnai ir jānonāk līdz kādam areaToTraverse grafam piederošam krustojumam. 2. Ceļš sākas un beidzas autoparkā3. Braukšanas ceļš ir cikls ar vismazāko šķautņu svaru summu, kur ceļš sākas un beidzas autoparkā. 4. Automašīnai jāapmeklē visas ielas no grafa Town tā, ka katra iela tika apmeklēta visos atļautos braukšanas virzienos vismaz vienu reizi, t.i., vienvirziena ielas apmeklētas vismaz vienu reizi atļautā virzienā, savukārt divvirziena ielas ir apmeklēta vismaz vienu reizi abos virzienos. 5. Dažas ielas vai ielas virzieni var būt slēgti dēļ remontdarbiem vai kādiem citiem ierobežojumiem.

1. Vakcinācijas plānošana
2. Skolēnu piekārtošana skolām
3. Paciņu izvietošana pa mašīnām
4. Blēžu bildēšana

Uzdevums ir sastādīt plānošanas grafiku detektivem, lai noķertu visus blēžus. Detektīvi: ķer blēžus ar mērķi vienas dienas laikā noķert pēc iespējas vairāk blēžu. Katram detektīvam ir savs protokola sastādīšanas laiks. Katram detektīvam ir savs darba laika sākums un beigas. Katrs detektīvs pārvietojas, vai nu ar sabiedrisko transportu, vai nu ar auto. Ne visiem detektīviem ir auto. Katram detektīvam ir savs pieredzes līmenis (strādājošo mēnešu skaits). No tā ir atkarīgs laiks, kas nepieciešams, lai nofotografētu blēžu grupu. Katrs detektīvam ir ofiss, kur viņš strādā un kurā jāatgriežās pēc grupas ķeršanas. Katram detektīvam ir maksimālais blēžu grupu skaits, kuru var noķert. Katram detektīvam ir jāmaksā par veicamo darba ilgumu atkarībā no viņa stundas likmes. Detektīvi darbojas brīvajā darba režīmā un drīkst atpūsties ārpus tie ķer blēžu grupas. Tāpēc ir jāmaksā tikai par laiku, kad tie brauc no vai līdz blēžu grupai. Katram detektīvam ir jāmaksā par auto izmaksām (proti, ja tam ir auto). Ja detektīvam ir auto, tad katru blēžu grupa viņš ķer, pārvietojoties ar auto. Blēžu grupas: blēži satiekas grupās. Visas grupas var būt dažādas! Viens blēdis var būt vairākas grupās. Katrs blēdis satiekas vismaz viena grupā. Katrai blēžu grupai ir piekārtots pieredzes līmenis jeb novērtējums, cik grūti ir noķert šo grupu. Katram grupai ir savs tikšanas laiks un tikšanas beigu laiks. Nosacījums blēžu grupas noķeršanai: visi detektīvi sākumā atrodas ofisos. Detektīvs ir noķēris blēžu grupu, ja atbrauca pie grupas šīs grupas tikšanas laikos un sava darba laikā. Nofotografējis grupu. Atbrauca atpakaļ ofisā viņa darba laikā. Hard ierobežojumi: pēc katras grupas apmeklēšanas detektīvam jāatgriežas sava ofisā. Detektīva pieredzes līmenim jābūt lielākam vai vienādam ar blēžu grupas pieredzes līmeni. Visas blēžu grupas ir jāķer to tikšanas laikos. Visas blēžu grupas ir jāķer detektīva darba laikā Detektīvs nedrīkst ķert vairāk nekā tam paredzēts grupu skaits. Soft ierobežojumi: kopējam attālumam jābūt pēc iespējas mazākam. Izmaksām par detektīva darba laiku jābūt pēc iespējas mazākām. Izmaksām par detektīva auto lietošanu jābūt pēc iespējas mazākām.

1. Japāņu krustvārdu mīklas
2. Sudoku visvisādi varianti
3. Sociālā dienesta,ārstu apmeklējumu plānošana

CVRPTW tipa uzdevums. Slimnīca piedāvā pakalpojumu kur viņu ārsti ir gatavi apciemot pacientus viņu mājās. Katram pacientam ir vajadzīga noteikta specialitāte no ārsta, lai viņs spētu to apkalpot, kā arī noteikts spēks gadījumā ja ar pacientu ir jārīkos fiziskā mērā, piemēram, pacientu vajadzētu pārvietot no gultas uz kaut kur citu viet. Ārsti braucot pie pacientiem ved līdzi medikamentus vai citus preperātus, kas viņiem būtu vajadzīgi, lai apkalpotu pacientu. Ārstam braucot pie pacienta var arī būt vajadzība no tā pievākt preperātus, piemeram, asisns analīzes, urīns etc. Ārsti strādā noteiktos darba laikos, jeb laika logos, kā arī viņu pacienti var būt tikt apciemoti tikai to noteiktajos laikos.

1. Detaļu sagriešana minimizējot atlikumus
2. Grāmatu draugi
3. Darba grafika plānošana
4. Darbu un resursu plānošana
5. Šņūksti (@ Dāvis Valts Briedis)

SIA Šņūkstings Bruņuvardes ir bruņuvaržu ražošanas uzņēmums. Uzņēmumā strādā tikai šņūksti. Katru dienu tajā strādājošie šņūksti pabaro bruņuvardes, bet viņiem nav skaidrs kāds ir vislabākais grafiks bruņuvaržu barošanai, tāpēc viņiem ir nepieciešama IT sistēma, kas spēs optimizēt barošanas grafikus. Papildus šņūkstiem jāpaspēj pusdienās iesņūkstēties. Uzņēmuma teritorijā ir iespējams nokļūt tikai caur administrācijas ēku. Tajā arī atrodas ēdnīca. Tālāk ir iespējams no administrācijas ēkas nokļūt uz korpusu 1. No korpusa 1 ir iespējams nokļūt uz korpusu 2 un korpusu 2a. Ir iespējams arī nokļūt no korpusa 2 uz korpusu 2a, bet ceļš starp tiem ir mīnēts. Bruņuvardes tiek uzglabātas bruņuvaržu krātiņos. Katram krātiņam ir numurs. Krātiņi ar secīgiem numuriem arī fiziski atradīsies blakus. Vienā krātiņā ir viena bruņuvarde. Katrā korpusā ir zināms daudzums krātiņu. Administrācijas ēkā nav krātiņu. Ir jāatrod grafiks, kas būs bruņuvaržu barošanas secība. Tas sastāvēs no ierakstiem, katrā ierakstā būs norādīts kāda darbība šņūkstam ir jāveic, kurā korpusā tā ir jāveic un kurā krātiņā tā ir jāveic. Grafikam jābūt saliktam tādam, ka ja šņūksts seko šim grafikam, viņš būs paveicis savu darbu iespējami īsākā laikā.

1. Lidmašinu apkalpju darba plānošana

Kaut kāda diena ir X lidojumi, katram lidojumam ir nepieciešams atrast ekipāžu kurš sastav no A pirmā līmeņa pilotiem, B otrā līmeņa pilotiem un C stjuartiem (katram lidojuma A,B un C var būt dažādi). Katram lidojumam ir zinamas izlidošanas un ielidošanas lidosta, ka arī plānotais izlidošanas un ielidošanas laiks. Kompānija strāda Y darbinieki, par katru darbinieku ir zinama viņa profesija, mājas lidosta (t.i. kur strādnieks atrodas tagad) un viņa pieejamība stradāta šaja dienā (piejams, nav pieejams, nevēlams). U-zdevums ir katram lidojumam atrast ekipāžu tā lai: Hard ierobežojumi: - Strādnieks ekipažā aizņem savu profesiju - Stradnieks nevar atrasties 2 dažas lidojumos vienlaikus - Strādnieks startē savā mājas lidostā - Strādnieks atlidojot kaut kāda lidosta, nākamu lidojumu var veikt tikai no šis lidostas - Stradnieks nevar strādat ja vina pieejamība “nav pieejams”. Soft ierobežojumi: - Strādniekam ir nepieciešama vismaz 2 stundu atpūta starp lidojumiem - Strādnieks dienas beigās atgriežas savas mājas lidostā - Stradnieks nevar strādat, ja vina pieejamība “nevēlams”

1. F1 grafika plānošana
2. Skolas autobusu maršrutu plānošana

Optimizēt skolas autobusu maršrutus, lai uzņemtu un izlaistu skolēnus, vienlaikus ievērojot laika ierobežojumus

un transportlīdzekļu ietilpību kā arī maksimāli apmierināt studentu vēlmes.

1. Aktieru nolīgšana
2. Rogainings, utml.
3. Izvietot k punktus nxn režģī - no-3-in-a-row
4. Pentamino
5. Kameru izvietošana telpās
6. Testēšanas darbu plānošana
7. Towers mīklas
8. Noliktavu izvietošanas plānošana, lai nodrošinātu pieprasījumu

Uzdevumā pamatā ir Facility Location Problem, kuru mērķis ir atrast optimālākās atrašanās vietas noliktavām, lai attālums līdz veikaliem būtu pēc iespējas tuvāks, ņemot vērā to, ka katrai noliktavai ir noteikts darba kapacitātes apjoms, kuru nedrīkst pārsniegt. Šī darba kapacitāte balstās uz nobrauktu attālumu starp šo noliktavu no saistītiem veikaliem kopā ar apkalpošanas laiku vienam veikalam (nosacītā laika vienība). Pieņēmumi: noliktava ir spējīga apkalpot vienā izbraukumā tikai vienu veikalu, pēc katra izbraukuma “mašīna” atgriežas līdz noliktavai, uzdevumā tiek uzskatīts, ka visas rēķināšanas tiek veiktas gadījumiem, kad visiem veikaliem dienas laikā ir jānogādā nepieciešamas preces. Jebkurā secībā/laikā, nevis noteiktā laika apgabalā(ne time windows). Ieejas dati: Visas potenciālās noliktavas, kuras ir pieejamas nomai. Visi veikali, kas ir jāapkalpo. Izejas dati: noliktavas ar piesaistītajiem veikaliem, kurus tie apkalpos, karte ar noliktavām un veikaliem.

1. Sporta spēļu (turnīra) kalendāra plānošana
2. Aktivitāšu plānošana personām
3. Lidostu skrejceļu izmantošanas plānošana