Семинар за рачунарство и примењену математику, 16. новембар 2021.

• 15. Новембар, 2021
• Коментари (0)

Наредни састанак Семинара биће одржан онлајн у уторак, 16. новембра 2021. са почетком у 14.15 часова.

Предавач: Уна Станковић, Математички институт САНУ

Наслов предавања: THE WEIGHTED SCHEDULING PROBLEM WITH DEADLINES AND RELEASE TIMES

Апстракт:
We consider a non-preemptive scheduling problem with deadlines and release times, where each task is associated with a nonnegative weight. The problem consists of finding a subset of tasks that are going to be scheduled and executed in such a way that the sum of weights of all scheduled tasks is maximized. This problem has many potential applications, one of them in energy efficient BlockChain systems, the ones that use Proof-of-Useful-Work (PoUW) consensus protocols. For the considered problem, we propose two mathematical formulations in the form of Mixed Integer Linear Programs, and test them on a set of randomly generated instances using GLPK solver. Since the problem is proven to be NP-hard, we consider a metaheuristic approach, based on the General Variable Neighborhood Search (GVNS) method. This approach is tested on the same set of randomly generated instances, and compared with the exact solver. The obtained results suggest that GVNS is able to find high-quality solutions in short amount of time.

This is a joint work with Luka Matijević and Tatjana Davidović presented at SYMOPIS 2021.

Због тренутне епидемиолошке ситуације, предавања се могу пратити искључиво на даљину преко линка
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So

За активно учешће на Семинару (дискусија, евиденција присуства) неопходно је да се на том линку и улогујете (ставка "login" у горњем десном углу). Уколико нисте већ регистровани то можете учинити преко линка:
https://miteam.mi.sanu.ac.rs/asset/xzGqvSp7aWbg8WpYX