Naredni sastanak Seminara biće održan onlajn u sredu, 2. april 2025. godine, sa početkom u 19 časova.

Predavač: Dragutin Ostojić, Prirodno-matematički fakultet, Univerzitet u Kragujevcu

Naslov predavanja: POLINOMIJALNI REGRESIONI MODEL ZA STANDARDIZACIJU INSTANCI P||CMAX PROBLEMA VELIKE PRECIZNOSTI

Apstrakt:
Ovo istraživanje predstavlja napor da se standardizuje dobro poznata grupa testnih instanci, označenih kao „𝐵 instance“, koje se koriste za ocenjivanje rešavača za klasični problem raspoređivanja zadataka na identične procesore, tzv. 𝑃||𝐶𝑚𝑎𝑥 problem koji koriste formulaciju pomoću problema particionisanja brojeva na više delova (Multi-Way Number Partitioning, MWNP). Prvobitno predložene u (Korf, 1998), 𝐵 instance su definisane za konfiguraciju od tri mašine (𝑚 = 3), i odnose se na raspoređivanje do 100 zadataka (𝑛 ≤ 100), pri čemu vremena obrade zadataka (preciznosti) 𝑝𝑖 ∈ 𝑈 [1, 10⁵]. Karakteriše ih mali broj mašina i velika, ravnomerno raspoređena, vremena obrade zadataka. Vremenom, ove instance su evoluirale kako bi obuhvatile razne varijacije u broju mašina, broju zadataka i granicama za vremena obrade, što je dovelo do najobimnijeg objavljenog skupa podataka (Schreiber & Korf, 2014). Ovaj skup podataka je bio od ključne važnosti za mnoga dosadašnja istraživanja vezana za 𝑃||𝐶𝑚𝑎𝑥 problem. Danas, sa napretkom rešavača, javlja se potreba za proširenjem i standardizacijom ovog skupa, koje sa sobom nosi različite izazove.
Da bismo osigurali uključivanje svih značajnih skupova ove vrste iz postojeće literature, predložili smo prošireni standardizovani skup podataka prateći formulaciju iz (Ostojić et al., 2024). Ovaj obimni skup dovodi do ključnih problema:

• Računarski zahtevi: Ukupan potreban vremenski resurs za testiranje ovog broja instanci je značajan, naročito za egzaktne rešavače.
• Lakoća: Mnoge instance su veoma jednostavne za većinu rešavača, što umanjuje fokus na one koje predstavljaju pravi izazov.
• Rast veličine skupa: Veličina skupa podataka brzo raste sa povećanjem maksimalnih vrednosti 𝑛, 𝑚 ili veličine intervala za vremena obrade zadataka (𝑐𝑙𝑎𝑠𝑠), što će verovatno biti nastavljeno sa razvojem rešavača i računarske snage.
  U predavanju ćemo se baviti prevazilaženjem ovih izazova redukujući standardizovani skup 𝐵 instanci tako da obuhvata većinu varijacija pronađenih u literaturi, sa posebnim fokusom na izazovne instance. Kao najadekvatniji alat za postizanje ovog cilja izabran je polinomijalni regresioni model.

Ovo istraživanje sprovedeno je u saradnji sa dr Kristin Zarges sa Univerziteta u Aberistvitu u Ujedinjenom Kraljevstvu.

Napomena:
Registraciona forma za učešće i link za aktivno praćenje predavanja za registrovane korisnike (nakon logovanja):
https://miteam.mi.sanu.ac.rs/asset/CW5nJWDSEZDj7p32p

Neregistrovani korisnici mogu da prate predavanja na ovom linku (bez mogućnosti aktivnog učešća):
https://miteam.mi.sanu.ac.rs/call/hR9vL94nD6QE8qQZj/xET9GcPMyR08nqH8lnS3SE7N5Vf00H7Lp9EBhsv6Lti