Modele i algorytmy szeregowania zadań w systemach just-in-time

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.

Reprezentacje macierzowe wybranych problemów szeregowania zadań

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.

 

Algorytmy odkrywania reguł klasyfikacyjnych z niezbalansowanych przykładów uczących

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.

Szeregowanie zadań z kryterium minimalnego czasu cyklu

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.

O obliczaniu skojarzeń w rozproszonym modelu obliczeń

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.

Podzielne szeregowanie zadań z pozycyjno-zależnymi czasami wykonywania na dwóch równoległych identycznych maszynach (prezentacja wyników rozprawy doktorskiej)

Prelegent: mgr Marcin Żurowski (Zakład Algorytmiki i Metod Numerycznych)
Miejsce: Sala seminaryjna B1-37
Data i godzina:  14 maja 2019 r., g. 13:00

Streszczenie: Przedstawione zostaną własności pewnego problemu szeregowania podzielnych zadań pozycyjno-zależnych na dwu identycznych równoległych maszynach z kryterium minimalizacji długości uszeregowania oraz, na bazie tych własności, dwa algorytmy dokładne i dwa algorytmy heurystyczne dla rozważanego problemu

Rząd pewnych kombinacji macierzy

Prelegent: Prof. UAM Tomasz Szulc
Miejsce: B1-7/8
Data i godzina:  14 maja 2019 r., g. 12:30

Streszczenie: Przedstawione zostaną nowe wyniki, otrzymane wspólnie  z prof. Charlesem R. Johnsonem (College of William and Mary, Williamsburg, USA) oraz prof. Juanem M. Peną (Uniwesytet w Saragossie, Hiszpania), dotyczące problemu odporności rzędu macierzy na pewne zaburzenia jej elementów. Rozważa się pełność rzędu kwadratowych kombinacji trzech macierzy oraz pełność rzędu pewnych uogólnień tych kombinacji. Odpowiada się również na pytanie kiedy wszystkie wypukłe kombinacje dwóch macierzy rzędu 1 są rzędu 1.

Spectra of tridiagonal matrices

Prelegent: Professor Charles R. Johnson (College of William and Mary, Williamsburg, USA)
Miejsce: Sala posiedzeń Rady Wydziału
Data i godzina:  28 maja 2019 r., g. 12:00

Abstract: We discuss the possible spectra of tridiagonal matrices over a field and the possible Jordan structure. We also discuss „arrow matrices” and their Jordan structure by contrast.

Szeregowanie zadań czasowo-zależnych w systemie otwartym

Prelegent: prof. UAM Stanisław Gawiejnowicz
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  2 kwietnia 2019 r., g. 12:30

Streszczenie: System otwarty jest jednym z trzech głównych środowisk maszyn dedykowanych. W referacie przedstawione zostaną pewne nowe wyniki dotyczące szeregowania w tym środowisku zadań z czasowo-zależnymi proporcjonalnymi czasami wykonywania.

Scheduling in a data gathering network to minimize maximum lateness

Prelegent: dr Joanna Berlińska
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  12 marca 2019 r., g. 12:30

Abstract: We study scheduling in a data gathering network consisting of a set of worker nodes and a single base station. The workers produce datasets that have to be sent to the base station for processing. Each dataset can be released at a different moment. The time required to transfer a dataset to the base station, and the time necessary to process it, are proportional to the dataset size. At most one worker can communicate with the base station at a time, and hence, the network works in a flow shop mode. A dataset transfer or processing can be preempted at any time and resumed later at no cost. Each dataset is assigned a due date by which it should be fully processed by the base station. The scheduling problem is to organize the communication and computation in the network so that the maximum dataset lateness is minimized. We prove that this problem is strongly NP-hard, and show some special cases that can be solved in polynomial time. A branch-and-bound algorithm and several polynomial-time heuristics are proposed for the general version of the problem. The performance of the algorithms is tested in a series of computational experiments.