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.

Prelegent: prof. dr hab. Joanna Józefowska (Politechnika Poznańska)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  19 listopada 2019 r., g. 12:30

Streszczenie: Mimo, że współcześnie teoria szeregowania zadań nie jest już nowinką w obszarze badań operacyjnych, to nadal inspiruje naukowców różnorodnością zastosowań praktycznych, modeli matematycznych i nowymi ujęciami znanych problemów. Jednym z przykładów jest szeregowanie zadań w systemach just-in-time, które znalazło wiele praktycznych zastosowań w systemach produkcyjnych i informatycznych. Celem tej prezentacji jest omówienie dwóch różnych podejść do modelowania problemu just-in-time. Pierwszy z nich ma korzenie w oryginalnym systemie produkcyjnym Toyoty, a drugi jest rozszerzeniem klasycznego problemu szeregowania zadań. Każdy z nich odnosi się do nieco innych warunków produkcyjnych, a obydwa prowadzą do interesujących wyników teoretycznych.

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

Streszczenie: W referacie zostanie dokonany przegląd zastosowań macierzy w wybranych problemach szeregowania zadań. Szczególna uwaga zostanie zwrócona na jeden z typów takich problemów, dla którego zostaną omówione własności macierzy pozwalające na jego rozwiązanie. Prezentowane pojęcia oraz problemy zostaną zilustrowane przykładami.

Prelegent: dr hab. Jerzy Stefanowski, prof. PP (Politechnika Poznańska)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  5 listopada 2019 r., g. 12:30

Streszczenie: Metody poprawy działania klasyfikatorów uczonych z niezbalansowanych danych są nadal wyzwaniem badawczym w ramach uczenia maszynowego. W szczególności dotyczy to automatycznego odkrywania reguł klasyfikacyjnych z danych, gdyż wiele ze znanych metod jest nadmiernie ukierunkowane w stronę klas większościowych i napotyka trudności w skutecznym rozpoznawaniu przykładów z klas mniejszościowych. Powyższe ograniczenia są także powiązane z trudnościami złożonych rozkładów przykładów klas mniejszościowych w niezbalansowanych danych. W wyniku analizy powyższych źródeł trudności oraz ograniczeń istniejących algorytmów K. Napierała i J. Stefanowski wprowadzili algorytm BRACID. W tym algorytmie wykorzystano informacje o typach trudności przykładów, podwójną reprezentację wiedzy (reguły i pojedyncze przypadki), nowe strategie konstrukcji reguł (poprzez stopniowe uogólnianie) oraz specjalizowane techniki rozstrzygania konfliktów w trakcie klasyfikowania nowych przypadków. W referacie zostanie podsumowana ocena eksperymentalna algorytmu BRACID i pokazane jego lepsze działanie predykcyjne w stosunku do znanych algorytmów. Ponadto, w końcowej części wystąpienia omówione zostanie autorskie podejście do wspomagania interpretacji pojedynczych reguł, wykorzystujące Bayesowskie miary konfirmacji.

Prelegent: dr hab. Wojciech Bożejko, prof. PWr (Politechnika Wrocławska)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  29 października 2019 r., g. 12:30

Streszczenie: Problemy cykliczne stanowią specyficzną podklasę problemów szeregowania, ciesząc się ostatnio coraz większym zainteresowaniem zarówno praktyków jak i teoretyków. Są obiektem zainteresowań badaczy głównie ze względu na ich silne znaczenie praktyczne oraz kłopoty z uzyskaniem odpowiednio efektywnych algorytmów rozwiązywania. Problemy z kryterium czasu cyklu należą do  trudniejszych zagadnień optymalizacji dyskretnej (m.in. z racji możliwych niecałkowitych wartości minimalnego czasu cyklu dla danych całkowitoliczbowych) i były dotychczas formułowane i analizowane wyłącznie dla systemów o stosunkowo prostej strukturze, np. systemów jednostanowiskowych lub przepływowych. Tematem referatu będzie identyfikacja i formalizacja nowych modeli współczesnych cyklicznych systemów wytwarzania, a także opracowanie i weryfikacja metod rozwiązywania tak zdefiniowanych zagadnień optymalizacji dyskretnej z kryterium minimalizacji czasu cyklu.

Prelegent: dr hab. Michał Hanćkowiak, prof. UAM (Zakład Teorii Algorytmów i Bezpieczeństwa Danych)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  22 października 2019 r., g. 12:30

Streszczenie: Zamierzam pokazać postęp jaki się dokonał w ostatnich 15 latach, jeśli chodzi o obliczanie skojarzeń (i podobnych problemów) w rozproszonym modelu obliczeń. Jako przykłady przedstawię dwa rozproszone algorytmy obliczania skojarzeń: pierwszy, działający w czasie O(log^4(n)) oraz drugi, wykorzystujący do pewnego stopnia narzędzia użyte do konstrukcji pierwszego, o znacząco lepszym czasie działania.