Наредни састанак Семинара биће одржан онлајн у среду, 2. април 2025. године, са почетком у 19 часова.
Предавач: Драгутин Остојић, Природно-математички факултет, Универзитет у Крагујевцу
Наслов предавања: ПОЛИНОМИЈАЛНИ РЕГРЕСИОНИ МОДЕЛ ЗА СТАНДАРДИЗАЦИЈУ ИНСТАНЦИ P||CMAX ПРОБЛЕМА ВЕЛИКЕ ПРЕЦИЗНОСТИ
Апстракт: Ово истраживање представља напор да се стандардизује добро позната група тестних инстанци, означених као „𝐵 instance“, које се користе за оцењивање решавача за класични проблем распоређивања задатака на идентичне процесоре, тзв. 𝑃||𝐶𝑚𝑎𝑥 проблем који користе формулацију помоћу проблема партиционисања бројева на више делова (Multi-Way Number Partitioning, MWNP). Првобитно предложене у (Korf, 1998), 𝐵 инстанце су дефинисане за конфигурацију од три машине (𝑚 = 3), и односе се на распоређивање до 100 задатака (𝑛 ≤ 100), при чему времена обраде задатака (прецизности) 𝑝𝑖 ∈ 𝑈 [1, 10⁵]. Карактерише их мали број машина и велика, равномерно распоређена, времена обраде задатака. Временом, ове инстанце су еволуирале како би обухватиле разне варијације у броју машина, броју задатака и границама за времена обраде, што је довело до најобимнијег објављеног скупа података (Schreiber & Korf, 2014). Овај скуп података је био од кључне важности за многа досадашња истраживања везана за 𝑃||𝐶𝑚𝑎𝑥 проблем. Данас, са напретком решавача, јавља се потреба за проширењем и стандардизацијом овог скупа, које са собом носи различите изазове. Да бисмо осигурали укључивање свих значајних скупова ове врсте из постојеће литературе, предложили смо проширени стандардизовани скуп података пратећи формулацију из (Остојић et al., 2024). Овај обимни скуп доводи до кључних проблема:
- Рачунарски захтеви: Укупан потребан временски ресурс за тестирање овог броја инстанци је значајан, нарочито за егзактне решаваче.
- Лакоћа: Многе инстанце су веома једноставне за већину решавача, што умањује фокус на оне које представљају прави изазов.
- Раст величине скупа: Величина скупа података брзо расте са повећањем максималних вредности 𝑛, 𝑚 или величине интервала за времена обраде задатака (𝑐𝑙𝑎𝑠𝑠), што ће вероватно бити настављено са развојем решавача и рачунарске снаге.
У предавању ћемо се бавити превазилажењем ових изазова редукујући стандардизовани скуп 𝐵 инстанци тако да обухвата већину варијација пронађених у литератури, са посебним фокусом на изазовне инстанце. Као најадекватнији алат за постизање овог циља изабран је полиномијални регресиони модел.
Ово истраживање спроведено је у сарадњи са dr Kristin Zarges са Универзитета у Абериствиту у Уједињеном Краљевству.
Напомена: Регистрациона форма за учешће и линк за активно праћење предавања за регистроване кориснике (након логовања):
https://miteam.mi.sanu.ac.rs/asset/CW5nJWDSEZDj7p32p
Нерегистровани корисници могу да прате предавања на овом линку (без могућности активног учешћа):
https://miteam.mi.sanu.ac.rs/call/hR9vL94nD6QE8qQZj/xET9GcPMyR08nqH8lnS3SE7N5Vf00H7Lp9EBhsv6Lti