Kategoria: Seminarium

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.

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.

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.

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.

Prelegent: mgr Tytus Pikies (Politechnika Gdańska)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  11 grudnia 2018 r., g. 12:30

Streszczenie: Problem kolorowania kosztowego polega na znalezieniu kolorowania wierzchołkowego danego grafu o minimalnym łącznym koszcie dla zadanych kosztów kolorów. Podczas wystąpienia zostanie przedstawiona analiza tego problemu względem ważonych grafów dwudzielnych. Zostaną scharakteryzowane sekwencje kosztów dla których problem jest NP-trudny. Zostanie również przedstawiony wielomianowy algorytm optymalny dla pozostałych przypadków.

Prelegent: prof. dr hab. inż. Piotr Formanowicz (Politechnika Poznańska)
Miejsce: Sala seminaryjna B2-8/9
Data i godzina: 4 grudnia 2018 r., g. 12:30

Streszczenie: Spektrometria masowa jest jedną z najważniejszych technik wysokoprzepustowych wykorzystywanych do badania cząsteczek związków biochemicznych. Standardowym podejściem stosowanym przy analizie uzyskiwanych widm, zwłaszcza w przypadku badania peptydów, jest porównywanie otrzymanego widma z wcześniej otrzymanymi i zidentyfikowanymi widmami, przechowywanymi w publicznie dostępnych bazach danych. Podejście to ma jednak wiele ograniczeń. Stąd, istotne znaczenie mają metody de novo. Metody takie umożliwiają m.in. analizę nieznanych wcześniej cząsteczek. Pojawia się przy tym wiele interesujących problemów algorytmicznych, które należy rozwiązać, by zidentyfikować badany związek chemiczny. W ramach referatu zostaną omówione niektóre z tego typu problemów.

Prelegent: prof. dr hab. Czesław Smutnicki (Politechnika Wrocławska)
Miejsce: Sala seminaryjna B2-8/9
Data i godzina: 6 listopada 2018 r., g. 12:30

Streszczenie: Problemy planowania i sterowania w dyskretnych systemach wytwarzania, problemy rozmieszczenia, pakowania, cięcia, kolekcjonowania, transportu, dystrybucji produktów, dostarczania towarów, planowania zajęć dydaktycznych, harmonogramowania pracy personelu, planowania tras robotów, etc. stanowią szczególnie trudną klasę zadań optymalizacji kombinatorycznej. Wśród wielu narzędzi dedykowanych do modelowania i optymalizacji wymienia się te zaliczane do dziedziny badań operacyjnych, która charakteryzuje się znaczną rozmaitością modeli i algorytmów rozwiązywania. Ograniczenie ogólności modeli ma na celu wykrycie tych szczególnych własności problemu, których umiejętne wykorzystanie w algorytmie zdecydowanie poprawia jego cechy numeryczne takie, jak czas obliczeń, szybkość zbiegania do rozwiązania optymalnego, lub bliskiego optymalnemu. Badania prowadzone od lat na WE PWr dotyczą problemów generowanych przez praktykę systemów wytwarzania, transportu, magazynowania, etc. Odwołują się m.in do do pewnych analiz teoretycznych, modeli grafowych, metaheurystyk, obliczeń równoległych, analizy wielokryterialnej.  Przedstawione zostaną główne wyniki zespołu zajmującego się tą tematyką na WE PWr, na tle tendencji zmian w dziedzinie obserwowanej w ostatnich latach.

Prelegent: prof. UAM dr hab. Stanisław Gawiejnowicz
Miejsce: Sala seminaryjna B2-8/9
Data i godzina: 16 października 2018 r., g. 12:30

Streszczenie: W referacie zostanie przedstawiony przegląd tematyki jednej z istotnych gałęzi współczesnej teorii szeregowania zadań zwanej szeregowaniem zadań czasowo-zależnych. Omówione zostaną główne wyniki dotyczące środowisk maszyn równoległych i dedykowanych, jak również najistotniejsze rezultaty dotyczące wybranych nowych kierunków w tej teorii, takich jak szeregowanie zadań czasowo-zależnych na maszynach z ograniczoną dostępnościa, dwukryterialne szeregowanie zadań czasowo-zależnych, klasy wzajemnie powiązanych problemów szeregowania zadań czasowo-zależnych czy dwu-agentowe szeregowanie zadań czasowo-zależnych. Referat zostanie zakończony przedstawieniem głównych otwartych problemów z omawianej dziedziny.

Prelegent: dr Polina Kononova (Sobolev Institute of Mathematics, Russian Federation)
Miejsce: Sala seminaryjna B1-8
Data i godzina: 25 czerwca 2018 r., g. 13:00

Abstract: We consider the following single machine scheduling problem originated from the tile industry. A factory produces homogeneous products of several types. Products of the same type are produced in batches. Minimum batch size is known. The sequence-dependent batch setup time is given. We know a set of jobs. Each job consists of a set of operations. Each operation corresponds to manufacturing of a product with a certain type and quantity. The factory has storage with unlimited capacity and some quantity of each product. We can use the product from the storage instead of producing it. The tardiness of job is defined as the positive time difference between the due date of job and the completion time of the last operation of this job. Our aim is to find a schedule minimizing the total weighted tardiness. We design a stochastic tabu search to tackle this NP-hard problem. Computational results for real-world instances from the tile industry are also discussed.

Prelegent: dr Maksim Barketau (National Academy of Sciences of Belarus, Belarus)
Miejsce: Sala seminaryjna B1-8
Data i godzina: 25 czerwca 2018 r., g. 12:00

Abstract: Product partition problems are the recognition problems that have a multiplicative operation in their formulation. First, we will recall the well-known NP-complete problem SUBSET PRODUCT and its properties. Next, we will formulate another problem of this type, PRODUCT PARTITION, and present the intuition behind the proof of its strong NP-completeness. Finally, we will consider the problem 3-PRODUCT PARTITION and give the sketch of the proof of its strong NP-completeness.