Kategoria: Seminarium

Prelegent: Dr Bartłomiej Przybylski (Pracownia Algorytmiki)
Data i godzina:  16 listopada 2021 r., g. 10:30

Streszczenie: As the gap between compute and I/O performance tends to grow, modern High-Performance Computing (HPC) architectures include a new resource type: an intermediate persistent fast memory layer, called burst buffers. This is just one of many kinds of renewable resources which are orthogonal to the processors themselves, such as network bandwidth or software licenses. Ignoring orthogonal resources while making scheduling decisions just for processors may lead to unplanned delays of jobs of which resource requirements cannot be immediately satisfied. We focus on a classic problem of makespan minimization for parallel-machine scheduling of independent sequential jobs with additional requirements on the amount of a single renewable orthogonal resource. We present an easily-implementable log-linear algorithm that we prove is (2 + 5/6)-approximation. In simulation experiments, we compare our algorithm to standard greedy list-scheduling heuristics and show that, compared to LPT, resource-based algorithms generate significantly shorter schedules. (joint work with A. Naruszko and K. Rządca)

This is a retake of the presentation presented during the 27th International European Conference on Parallel and Distributed Computing (Euro-Par).

Prelegent: Dr Joanna Berlińska (Pracownia Algorytmiki)
Data i godzina:  9 listopada 2021 r., g. 10:30

Streszczenie: We consider scheduling on parallel machines under the constraint that some pairs of jobs cannot be processed concurrently. Each job has an associated weight, and all jobs have the same deadline. The objective is to maximize the total weight of on-time jobs. The problem is known to be strongly NP-hard in general. A polynomial-time algorithm for scheduling unit execution time jobs on two machines is proposed. The performance of a broad family of approximation algorithms for scheduling unit execution time jobs on more than two machines is analyzed. For the case of arbitrary job processing times, two integer linear programming formulations are proposed and compared with two formulations known from the earlier literature. An iterated variable neighborhood search algorithm is also proposed and evaluated by means of computational experiments.

Prelegent: Dr Marcin Żurowski (Pracownia Algorytmiki)
Data i godzina:  19 października 2021 r., g. 10:30

Streszczenie: W referacie zostanie przedstawiona wersja wstępna aplikacji służącej do graficznej reprezentacji uszeregowań zadań pozycyjno-zależnych na równoległych identycznych maszynach.

Prelegent: Dr Bartłomiej Przybylski (Pracownia Algorytmiki)
Data i godzina:  29 czerwca 2021 r., g. 12:30

Streszczenie: In Function as a Service (FaaS), a serverless computing variant, customers deploy functions instead of complete virtual machines or Linux containers. It is the cloud provider who maintains the runtime environment for these functions. FaaS products are offered by all major cloud providers (e.g. Amazon Lambda, Google Cloud Functions, Azure Functions); as well as standalone open-source software (e.g. Apache OpenWhisk) with their commercial variants (e.g. Adobe I/O Runtime or IBM Cloud Functions). We take the bottom-up perspective of a single node in a FaaS cluster. We assume that all the execution environments for a set of functions assigned to this node have been already installed. Our goal is to schedule individual invocations of functions, passed by a load balancer, to minimize performance metrics related to response time. Deployed functions are usually executed repeatedly in response to multiple invocations made by end-users. Thus, our scheduling decisions are based on the information gathered locally: the recorded call frequencies and execution times. We propose a number of heuristics, and we also adapt some theoretically-grounded ones like SEPT or SERPT. Our simulations use a recently-published Azure Functions Trace. We show that, compared to the baseline FIFO or round-robin, our data-driven scheduling decisions significantly improve the performance.

This is a retake of the presentation presented during 2021 21th IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid 2021).

Prelegent: Weronika Skowrońska
Data i godzina:  8 czerwca 2021 r., g. 12:30

Streszczenie: In the talk, first we summarize known properties of the so-called V-shaped sequences. Next, we show how the sequences can be generated and applied to solving of some scheduling problems. We complete our presentation with results of numerical experiments with implementations of discussed algorithms.

Prelegent: Dr Marcin Żurowski (Pracownia Algorytmiki)
Data i godzina:  23 marca 2021 r., g. 12:30

Streszczenie: W referacie przedstawimy nowy model podzielności pozycyjno-zależnych zadań uszeregowanych na dwóch równoległych identycznych maszynach, w którym dzielimy jedno zadanie jednokrotnie. W tym modelu zadanie podzielone na pierwszej maszynie kontynuujemy na dowolnej pozycji na drugiej maszynie.

Prelegent: Dr Joanna Berlińska (Pracownia Algorytmiki)
Data i godzina:  15 grudnia 2020 r., g. 12:30

Streszczenie: W referacie przedstawione zostaną wyniki dotyczące szeregowania zadań w dwumaszynowym flowshopie ze zmieniającą się w czasie ilością dostępnej pamięci. Skupimy się na przypadku zadań z jednostkowymi czasami trwania operacji i różnymi wymaganiami pamięciowymi. Pokażemy, że problem minimalizacji długości uszeregowania jest silnie NP-trudny i przedstawimy dla niego wielomianowy schemat aproksymacji (PTAS). Zaprezentowany zostanie również algorytm dokładny oparty na całkowitoliczbowym programowaniu liniowym oraz algorytmy heurystyczne.

Prelegent: Prof. dr hab. Marta Szachniuk (Instytut Chemii Bioorganicznej PAN & Wydział Informatyki i Telekomunikacji Politechniki Poznańskiej)
Data i godzina:  8 grudnia 2020 r., g. 12:30

Streszczenie: Pseudowęzeł to motyw charakterystyczny dla cząsteczek RNA. Złożoność jego struktury można określić poprzez rzędowość, która jednocześnie wskazuje na moment jego utworzenia w procesie zwijania się cząsteczki. W naszych badaniach zadaliśmy pytanie o możliwość odtworzenia hierarchii zwijania zapętlonych cząsteczek RNA wyłącznie na podstawie ich struktury 3D. Podczas wykładu zaprezentowane zostaną wybrane rozwiązania tego zagadnienia, m. in. bazujące na modelu grafowym i problemie kolorowania grafu.

Prelegent: Dr hab. Piotr Faliszewski, prof. AGH (Akademia Górniczo-Hutnicza w Krakowie)
Data i godzina:  1 grudnia 2020 r., g. 12:30

Streszczenie: Reguły punktowania komitetów stanowią bogatą rodzinę systemów wyborczych pozwalających na wybór grupy osób kandydatów spełniających zadane cechy. Naturalne przykłady takich wyborów to wybory parlamentarne, wybory finalistów w zawodach sportowych (kandydatami są zawodnicy, a wyborcami sędziowie), czy wybór filmów, które zostaną udostępnione pasażerom w samolocie (kandydatami są filmy, a wyborcami przewidywane profile gustów pasażerów). Niestety, problem znalezienia zwycięzcy dla większości reguł punktowania komitetów jest NP-trudny, a dobór odpowiedniej reguły dla danego zadania nie zawsze oczywisty. W ramach referatu przedstawię formalizm reguł punktowania komitetów, podstawowe podejścia algorytmiczne, kilka ważnych własności tych reguł oraz wyniki symulacji.

Prelegent: Dr hab. Stanisław Gawiejnowicz, prof. UAM (Pracownia Algorytmiki)
Data i godzina:  17 listopada 2020 r., g. 12:30

Streszczenie: NP-trudny problem plecakowy jest badany od wielu lat ze względu na istotne zastosowania praktyczne. W literaturze znanych jest kilka różnych wariantów tego problemu, w najbardziej znanym wszystkie parametry problemu (pojemność plecaka, rozmiary i wartości elementów) są liczbami. W referacie przedstawimy dotychczasowe wyniki dotyczące głównych wariantów tego problemu oraz nowe wyniki dla trzech nowych jego wariantów, w których rozmiary i/lub wartości elementów zależą od pozycji tych elementów w sekwencji elementów już upakowanych.