- (C)VRP(PD)(TW) ... u.c. ... (miskastes mašīnas, kurjeri, būvgružu konteineri, elektoauto ar uzlādi, pārvākšanās serviss utt. ...)
VRP - apmeklēt noteiktus punktus ātrāk/tuvāk/letāk. TW - laika logi, kad drīkst ierasties. C - mašīnas ietilpība. PD - paņemšana/nolikšana.
- 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?
- Šahs - figūru izvietošana, lai neapdraud viena otru (N_Queens)
Dots nxm šaha galdiņš uz kura izvietoti x kauliņi, izvietot kauliņus tā lai tie pēc iespējas mazāk apdraudētu viens otru. Kauliņš var būt: tornis, zirgs, laidnis, dāma, karalis. Attiecīgi kauliņi apdraudēšanu veic tāpat kā klasiskajos šaha noteikumos. ProgrSamma spēj apstrādāt situāciju kur būs daudz kauliņi, kas neizbēgami apdraudēs viens otru, bet programmai jāatrod variants kur kauliņi apdraud pēc iespējas mazāk citus kauliņus (resp mazāk pārklājās).
- Sagatavju optimāla griešana
Darbnīcā ir n metāla cauruļu sagataves, katra garumā I[i], kur 0<i<=n. Ir pasūtījums izgatavot m caurules garumos p[j]. Uzdevums ir saplānot, no kurām sagatavēm izgatavot pasūtītās caurules, lai būtu pēc iespējas mazāk atlikumu - nogriezto, bet neizmantoto sagatavju gabalu.
- 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.
- 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ē.
- Produktu sapakošana
Uzņēmumā ir n pakošanas mašīnas. Tam ir jāizpilda k pakošanas uzdevumi, kur katrs uzdevums ir iepakot noteiktu produktu p[i] līdz noteiktam termiņam T[i]. Ir zināms, ka katrs uzdevums veicams laikā t[i]. Tāpat arī zināms, ja pakošanas mašīnā nomainās produkts, tad tā ir jāiztīra un tas konkrētam produktam aizņem laiku c[j]. Saplānot kādā secībā un kurās pakošanas mašīnās veikt visus uzdevumus tā, lai visi pasūtījumi būtu laikā un viss process aizņemtu pēc iespējas mazāku laiku.
- 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.
- Vakcinācijas plānošana
Ir k vakcinācijas centri, kur katram ir brīvi laika logi w[i], kad var nākt vakcinēties. Saplānot vakcināciju n cilvēkiem, tā, lai kopējais attālums līdz vakcinācijas centriem būtu pēc iespējas mazāks. Doti attālumi starp visiem cilvēkiem un centriem, kā arī katram cilvēkam ir pateikts, no cikiem līdz cikiem viņi tiek uz vakcināciju!
- Skolēnu piekārtošana skolām
Doti n skolas un m skolēni. Zināma katras skolas ietilpība s[i], kur 0<i<=n un attālumi a[k,j] no k-tā skolēna līdz j-tajai skolai, kur 0<k<=m un 0<j<=n. Zināms, ka s[1]+...+s[n]<=m, t.i., skolās kopumā vietu pietiek. Piekārtot skolēniem skolas tā, lai kopējais attālums, kas jāveic skolēniem būtu pēc iespējas mazāks.
- Paciņu izvietošana pa mašīnām
Dotas m automašīnas, katra ar kravas kastes izmēru w[i] x l[i]. Dotas n kastes ar izmēriem p[j] x g[j].Salikt visas kastes pēc iespējas mazāk automašīnās. Var arī 3D!
- 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.
- Japāņu krustvārdu mīklas
Atrisināt melnbaltu Japāņu krustwārdu mīklu.
- Sudoku visvisādi varianti
Atrisināt Sudoku mīklu.
- 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.
- Pacientu gultasvietu plānošana
Pastāv slimnīca ar vairākām nodaļām, kurās pastāv istabas ar gultām, kur tiks novietoti slimnīcas pacienti, lai tie varētu pavadīt vienu nakti slimnīcā. Pacientu ierašanās un aiziešanās no slimnīcas datumi ir noteikti. Katrā istabā pastāv maksimāls gultu skaits, kuru iespējams novietot tajā, un pacientam ir vēlme būt novietotam ar istabu ar noteiktu izmēru (velme tiek nodefinēta kā istabas maksimālais izmērs, kura apmierina pacientu. Ja pacients tiek novietots istabā ar mazāku izmēru, tad pacients joprojām būs apmierināts). Pacienta ir iespējams novietot gan departamenta, kas nodarbojas ar slimības ārstēšanu, gan istabā, kura ir aprīkota ar nepieciešamām iekārtām pacienta slimības ārstēšanai. Pastāv pacienti, kuriem iekārtas ir nepieciešamas un tie, kuri vēlās, lai istabā būtu tās iekārtas. Istabām pastāv savi ierobežojumi: sieviešu istaba, vīriešu istaba, viena dzimuma pacienti vienā naktī, bez ierobežojuma. Tātad vīrieši nevar pavadīt nakti sieviešu istabā un sievietes nevar pavadīt nakti vīriešu istabā. Vienu dzimuma istabā kopā var pavadīt nakti vienlaikus tikai vīrieši vai tikai sievietes.
- Lekciju saraksta sastādīšana (Timetabling)
Uzdevums ir daļa no Timetabling uzdevumu klases, precīzāk Educational Timetabling klases. University Timetabling ietver dažādus apakšuzdevumus, piemēram, sastādīt lekciju sarakstu, sastādīt eksāmenu sarakstu, sastādīt konferencēm grafikus, aizstāvēšanu grafikus, utt. Šajā uzdevumā tiks apskatīts tieši lekciju saraksta sastādīšana. Uzdevumā ir dotas vairākas lekcijas, piemēram, “Lineārā algebra I”, “Kombinatorika”, utt., katrai no šīm lekcijām ir vajadzīgs piekārtot nedēļā lekciju konkrētā telpā, konkrētā laikā, kas nemainās visu semestri, ja tas nav 2 KP kurss, bet lielāks, piemēram, 4 KP, tad var būt 2 lekcijas nedēļā, utml. Toties jāņem vērā dažādi ierobežojumi, piemēram, vienā laikā un vienā telpā nevar notikt 2 lekcijas, vienā laikā pasniedzējs nevar pasniegt 2 lekcijas, vienā laikā grupa studentu nevar būt divās lekcijās vienlaicīgi. Kā arī var definēt citus ierobežojumus. Kopumā ir vērts skatīt šo uzdevumu, kā daļu no lielāka resursu (telpu, ierīču, personāla, ...) plānošanas uzdevuma.
- Grāmatu draugi
Grāmatu draugu biedrībā ir n lasītāji un n grāmatas. Pie katra lasītāja ir viena grāmata, kuru viņš ir izlasījis. Tāpat par katru citu grāmatu ir zināms, vai viņš to ir lasījis, vai nē. Kurjera uzdevums ir savākt un izvadāt grāmatas tā, lai beigās pie visiem lasītājiem būtu grāmata, ko viņš nav lasījis. Ir zināmi attālumi starp lasītājiem! Saplānot kurjera maršrutu tā, lai viņam būtu jānobrauc pēc iespējas mazāks attālums!
- Darba grafika plānošana
Sastādīt darbinieku maiņu grafiku - piekārtot darba vietai darbinieku ar atbilstošām prasmēm, ņemot verā darba likumdošanu un darbinieku vēlmes.
- Darbu un resursu plānošana
Sastādīt darbu izpildes grafiku, ņemot vērā pieejamo resursu daudzumu un termiņus.
- Šņū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ā.
- 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”
- F1 grafika plānošana
F1 sacensības notiek nedēļas nogalēs, laikā no marta līdz novembrim. Tātad mums ir n nedēļas nogales (apzīmēsim ar w[i], kārtējo nogali), kurās rīkot šo posmu. Ir k posmi (apzīmēsim ar p[j]), kas notiek noteiktā vietā uz pasaules un ir zināmas izmaksas, lai komandas aizceļotu no katra punkta uz katru (izm[p[j]]), kas iekļauj sevī arī radītās emisijas. Ir arī zināmi ieņēmumi no katra posma, ja tas tiek rīkots noteiktā laika posmā ien[p[j],w[i]). Bahreinā vasaras vidū varētu būt par karstu. Piekārtot katram posmam nedēļas nogali tā tā, peļņa būtu vislielākā!
- 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.
- Aktieru nolīgšana
Pieņemsim, ka mums ir jāizveido filmu ar vairākām ainām. Katrā ainā ir jāuzņem vienam vai vairākiem aktieriem. Aktieris uzņemt tikai vienu ainu dienā. Šo aktieru algas tiek aprēķinātas pa dienām. Šajā problēmā aktieris tiek pieņemts darbā līdz laikam, kad aktieris nofilmē visas savas ainas. Piemēram, mēs nevaram pieņemt darbā aktieri pirmajā un trešajā dienā, bet ne otrajā dienā. Nomas perioda laikā aktieriem joprojām ir jāmaksā, pat ja viņi nav iesaistīti filmēšanā. Vienā dienā var tikt filmēta tikai viena aina. Talantu plānošanas mērķis ir samazināt aktieru kopējo algu, pielāgojot ainu secību. Dots aktieru skaits N. Katram aktierim tiek piešķirta alga dienā. Dots ainu skaits M. Katrā M ainā tiek definēts aktieru masīvs, kur tiek ietverti aktieru numuri, kas piedalās ainā.
- Rogainings, utml.
Dotam grafam ar virsotnēm un zināmiem ceļu garumiem, atrast ceļu, kas savāc visaugstāko apmeklēto virsotņu vērtību, nepārsniedzot laika ierobežojumu.Katrai virsotnei ir punktu skaits ko var nopelnīt to apmeklējot. Katrai virsotnei ir tās veikšanai nepieciešamais laiks. Zināma distance starp virsotnēm. Zināms pārvietošanās ātrums. Zināms sākuma un beigu virsotnes, nokļūšana no/uz tiem iekļauta laikā. Sāk sākuma virsotnē. Beidz beigu virsotnē. Nepārsniedz laiku. Savāc maksimāli lielu punktu skaitu (ne obligāti var visas apmeklēt). Veic pēc iespējas mazāku distanci. Pēc iespējas mazāka kāpšana augšā/lejā kalnā.
- Izvietot k punktus nxn režģī - no-3-in-a-row
Dots uzdevums, kas sastāv no 𝑛∙𝑛 režģa, kur uz režģa krustpunktiem ir izvietots 𝑘daudzums ar punktiem. Uzdevuma mērķis ir atrast tādu punktu 𝑘 izvietojumu, ka nav iespējams novilkt taisnu līniju cauri trim vai vairāk punktiem. Tātad uz katras taisnes drīkst atrasties maksimums divi punkti.
- Pentamino
Ar dotajiem pentamino kauliņiem maksimāli noklāt doto ģeometrisko figūru. Kauliņi nedrīkst pārklāties vai iziet ārpus figūras robežas.
- Kameru izvietošana telpās
Dotas N telpas un K kameras . Ir M vietas, kur izvietot kameras , kur katrai vietai ir dotas tās telpas, kas ir no turienes redzamas. Izvietot kameras tā, lai visas telpas būtu redzamas vismaz no 2 kamerām un kameru skaits būtu pēc iespējas mazāks.
- Testēšanas darbu plānošana
Ir testēšanas sistēma, kurai laikā L ir nepieciešams izpildīt T testus. Katram no testiem ir platformu saraksts, uz kurām ir nepieciešams notestēt doto testu (praksē platformu skaits ir neliels, ~10). Testus būtu labi patestēt uz dažādām arhitektūrām (katrai platformai tādas var būt vairākas; praksē skaits arī ir neliels, <20). Testi tiek palaisti uz N ierīcēm (N ir novērojami mazāks nekā T), katrai ierīcei ir viena vai vairākas platformas (piem., linux + android [izmantojot emulatoru]) un viena vai vairākas arhitektūras (piem., uz x86_64 var palaist arī x86). Katram testam ir zināms tā darbības laiks (uz kādas “etalona” ierīces ar “jaudu/ātrumu” 1). Katrai ierīcei ir rēķināšanas “jauda/ātrums”, kas ir izteikts kā attiecība pret etalona ierīces jaudu. (Tad testa darbības laiks ir kādas ierīces x ir testa darbības laiks uz etalona ierīces / ierīces x jauda). Uzdevums ir izveidot plānu: kad, uz kādas ierīces, kādas platformas un izmantojot kādu arhitektūru ir nepieciešams palaist kādu testu, tā, lai: kopā visi T testi tiktu izpildīti, kopējais testēšanas laiks nepārsniedz L, katrs no testiem tiktu palaists uz katras platformas (no testam atbilstošām platformām), katram testam tiktu pārbaudītas pēc iespējas vairākas arhitektūras... (šeit var diskutēt par to, kā to novērtēt. Būtība ir tāda, ka nevajadzētu dot priekšroku "alkatīgi" izvēlēties tikai visātrākos testus un tos pārbaudīt uz vairākām arhitektūrām, bet lēnākus palaist tikai uz vienas. Tāpēc šajā uzdevumā prasība ir, lai minimālā vērtība "pārbaudīto arhitektūru skaits" / "visu testam iespējamo arhitektūru skaits" starp visiem testiem būtu maksimāla). Starp plāniem ar vienādu minimālo "pārbaudīto arhitektūru skaitu" / "visu testam iespējamo arhitektūru skaitu" starp testiem (no iepriekšējā punkta) jāatrod to, kuram vidējā vērtība (vai summa) pārbaudīto arhitektūru skaitu procentam visiem testiem ir vislielākā.
- Towers mīkla
Torņu mīkla
- 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.
- Sporta spēļu (turnīra) kalendāra plānošana
Create an optimization service, that makes a games calendar for football tournaments. As input, there is a list of stadiums, teams with their names and stadium names, where they play home games (one stadium can belong to many teams), and available Date/time slots. Every team pair plays against each other twice: once as a home team, and once as an away team. Games are always played in the home team's stadium. Constraints: No more than 1 game per day for each team. No more than 1 game per day at each stadium. A game can start only between 10.00 and 23.00. Games should be scheduled on weekends and Fridays. Minimum 2 free days between games for each team. On workdays, games start not earlier than 18.00. On weekends games start no earlier than 12.00. On weekends games start before 21.00. No more than one game for each time slot.
- Lidostu skrejceļu izmantošanas plānošana
Dati ir par lidmašīnu ierašanās laikiem lidostā un mērķis ir atrast optimālo plānu, kuros skrejceliņos, kurām lidmašīnām ir atļauts nolaisties, lai minimizētu citu lidmašīnu gaidīšanas laiku.
- Bioinformātika - sequence alignment
Dotas divas virknes a un b alfabētā A. Ļausim mainīt virknes sekojošā veidā ar funkcijas edit(x,y) palīdzību, kur x un y pieder A+{gap}, iespējamās darbības: 1) Ievietot gap vienā no virknēm 2) izdzēst gap vienā no virknēm 3) samainīt 2 blakus esošus simbolus vienā no virknēm. Nodefinēsim edit f-jas izmaksas cost(x,y). Tad izmaiņu virknes S kopējā izmaksās, būs visu izmaiņu izmaksu summa. Uzdevums ir atrast tādus a' un b', kas pieder A+{gap}, |a'|=|b'|, a' ir iegūstams no a, pievienojot {gap} simbolus, bet b' iegūstams no b pievienojot tam {gap} simbolus un izmaksas, kas nepieciešamas, lai no a' iegūtu b' ir vismazākās!
