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.

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

Streszczenie: W pierwszej części seminarium zaprezentuję efekty początkowych prac nad biblioteką do numerycznego wspomagania rozwiązywania problemów szeregowania zadań — Scheduling.jl. W drugiej części seminarium skupię się na wynikach dotyczących jedno- i wielomaszynowych problemów szeregowania zadań, w których zmienne czasy wykonywania zadań zależą nie tylko od pozycji zadania w uszeregowaniu, ale także – w dowolny sposób – od samego zadania i maszyny, do której zadanie zostało przydzielone. Dla takiej mieszanej zależności oraz wybranych funkcji celu (maksymalny czas zakończenia i łączny czas zakończenia) przedstawię pełną klasyfikację złożoności obliczeniowej. Przypomnę także wyniki dotyczące analogicznych problemów, w których zadania muszą być wykonywane w określonej kolejności (ograniczenia w postaci łańcucha), a także rozpocznę dyskusję na temat analizy problemów, w których ograniczenia kolejnościowe są opisane bardziej złożonymi grafami.

Prelegent: dr hab. Marta Szachniuk, prof. IChB PAN (Instytut Chemii Bioorganicznej PAN & Wydział Informatyki i Telekomunikacji Politechniki Poznańskiej)
Miejsce: B1-7/8
Data i godzina:  21 kwietnia 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.

W związku z zarządzeniem Rektora UAM nr 431/2019/2020 z dnia 11 marca 2020 roku w sprawie działań podejmowanych w celu przeciwdziałania rozprzestrzenianiu się wirusa COVID-19 wśród członków społeczności Uniwersytetu im. Adama Mickiewicza w Poznaniu wykład dr hab. Marty Szachniuk został odwołany. 

Prelegent: dr hab. Piotr Faliszewski, prof. AGH (Akademia Górniczo-Hutnicza w Krakowie)
Miejsce: B1-7/8
Data i godzina:  31 marca 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 sedziowie), 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.

W związku z zarządzeniem Rektora UAM nr 431/2019/2020 z dnia 11 marca 2020 roku w sprawie działań podejmowanych w celu przeciwdziałania rozprzestrzenianiu się wirusa COVID-19 wśród członków społeczności Uniwersytetu im. Adama Mickiewicza w Poznaniu wykład dra hab. Piotr Faliszewskiego został odwołany. 

Prelegent: Stanisław Gawiejnowicz (Pracownia Algorytmiki)
Miejsce: B4-6
Data i godzina:  3 marca 2020 r., g. 12:30

Streszczenie: W referacie przedstawione zostaną wybrane wyniki dotyczące szeregowania zadań czasowo-zależnych, otrzymane w ciągu ostatnich 10 lat, ze szczególnym uwzględnieniem stosowanych metod oraz technik dowodowych.

Prelegent: Professor Hans Kellerer (University of Graz, Austria)
Miejsce: Sala posiedzeń Rady Wydziału
Data i godzina:  14 stycznia 2020 r., g. 13:30

Streszczenie: We consider four single-machine scheduling problems with release times, with the aim of minimizing the maximum lateness. In the first problem we have a common deadline for all the jobs. The second problem looks for the Pareto frontier with respect to the two objective functions maximum lateness and makespan. The third problem is associated with a non-availability constraint. In the fourth one, the non-availability interval is related to the operator who is organizing the execution of jobs on the machine. For each of the four problems, we establish the existence of a polynomial time approximation scheme (PTAS).

Prelegent: dr Marcin Żurowski (Zakład Algorytmiki i Metod Numerycznych)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  10 grudnia 2019 r., g. 12:30

Streszczenie: Szeregowanie zadań z pozycyjno-zależnymi czasami wykonywania jest popularnym modelem szeregowania ze względu na łatwe zastosowanie takiego modelu w praktyce. Za pomocą tego modelu możemy symulować szybsze wykonywanie zadań spowodowane efektem uczenia się, bądź wolniejsze -spowodowane zmęczeniem pracownika. Tego typu modele opisane w literaturze zwykle dotyczą zadań niepodzielnych. W niniejszym referacie chciałbym przedstawić próby zaadoptowania kilku modeli podzielności występujących w klasycznym szeregowaniu do szeregowania zadań z efektem uczenia się.

Prelegent: dr hab. Krzysztof Rządca, prof. UW (Uniwersytet Warszawski & Google)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  3 grudnia 2019 r., g. 12:30

Streszczenie: When working on scheduling theory, I used to start the description of my model with a magic phrase: „We assume jobs’ resource requirements are known (a clairvoyant model)”. In this talk I’ll describe how this assumption might be achieved in a real-world, large scale infrastructure.

When submitting a job to a cloud, a user specifies limits on the job’s resource usage. However, humans are notoriously bad at predicting, especially predicting non-tangible resources such as CPU cores or GB of memory. Under-prediction has potentially disastrous consequences in particular for user-facing jobs: a job exceeding its limits might be throttled or killed, resulting in end-user requests delayed or dropped. Thus, human operators tend to err on the side of caution and over-allocate. Summed over the whole infrastructure, such widespread over-allocation and the resulting low utilization of hardware leads to significant costs in infrastructure over-expansion.

In my talk I will describe Autopilot, a production automation tool that Google uses in its internal cloud. Autopilot sets jobs’ resource limits using a combination of heuristics and machine learning. The context – a low-level production system many other higher-level services depend on – translates into ambitious reliability and efficiency requirements that are challenging for an ML application.

Prelegent: dr Bartłomiej Przybylski (Zakład Algorytmiki i Metod Numerycznych)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  26 listopada 2019 r., g. 12:30

Streszczenie: Problemy szeregowania zadań jednostkowych stanowią przedmiot zainteresowania badaczy nie tylko ze względu na szerokie zastosowania praktyczne, ale także ze względu na interesujące własności teoretyczne. Obszar ten, choć na pozór szeroko zbadany, kryje wciąż pytania, na które odpowiedzi nie znamy. Przez ostatnie lata zastanawiano się nad tym, czy istnieje wielomianowy algorytm pozwalający rozwiązać optymalizacyjny problem wielomaszynowego szeregowania zadań jednostkowych z ograniczeniami w postaci drzewa typu in-tree, ze średnim czasem zakończenia jako kryterium oceny uszeregowania. Intrygującą naturę tego pytania pogłębiał fakt, że od lat znamy wielomianowe algorytmy rozwiązujące niemal wszystkie problemy o podobnej charakterystyce. W czasie seminarium zaprezentujemy i skomentujemy opublikowany w lutym br. dowód NP-zupełności wspomnianego wyżej problemu.