Fairness in repetitive scheduling problems

Zapowiedź seminarium

Prelegent: Professor Dvir Shabtay (Ben Gurion University of the Negev, Israel)
Data i godzina:  23 września 2025 r., g. 11:00
Sala: B3-8/9

Abstract: Recent research found that fairness plays a key role in customer satisfaction. Therefore, many manufacturing and services industries have become aware of the need to treat customers fairly. Still, there is a huge lack of models that enable industries to make operational decisions fairly, such as a fair scheduling of the customers’ jobs. Our main aim in this research is to provide a unified framework to enable schedulers to make fair decisions in repetitive scheduling environments. For doing so, we consider a set of repetitive scheduling problems involving a set of n clients. In each out of q consecutive operational periods (e.g., days), each one of the customers submits a job for processing by an operational system. The scheduler’s aim is to provide a schedule for each of the q periods such that the quality of service (QoS) received by each of the clients will meet a certain predefined threshold. The QoS of a client may take several different forms, e.g., the number of days that the customer receives its job later than a given due date, the number of times the customer receives his preferred time slot for service, or the sum of waiting times for service. We analyze the single machine variant of the problem for several different definitions of QoS and classify the complexity of the corresponding problems using the theories of classical and parameterized complexity. We also study the price of fairness, i.e., the loss in the system’s efficiency that results from the need to provide fair solutions. (A joint work with Danny Hermelin, Hendrik Molter, Rolf Niedermeier and Michael Pinedo).

Proof methods of time-dependent scheduling

Seminarium

Prelegent: Prof. dr hab. Stanisław Gawiejnowicz (Pracownia Algorytmiki)
Data i godzina:  03 grudnia 2024 r., g. 11:00

Streszczenie: We discuss the methods applied in proofs of time-dependent scheduling results. We begin with recalling the basic notions of the first-order logic and proposition calculus. Next, we review the main proof methods such as, among others,  direct proof, proof by contradiction, proof by pairwise job interchange, NP-hardness proof and proof with the use of priority-generating functions. For each method, we describe its idea and give examples of its usage. We complete the talk by delineating the possible future research in that domain.

Optimizing large sensor data filtering, networking and computing

Seminarium

Prelegent: Prof. UAM dr hab. Joanna Berlińska (Pracownia Algorytmiki)
Data i godzina:  12 listopada 2024 r., g. 11:00

Streszczenie: We consider filtering and processing large data streams in intelligent data acquisition systems. It is assumed that raw data arrives in discrete events from a single expensive sensor. Not all raw data, however, comprises records of interesting events and hence some part of the input can be filtered out. The intensity of filtering is an important design choice because it determines the complexity of filtering hardware and software, and the amount of data that must be transferred to the following processing stages. We analyze the optimum intensity of filtering and its relationship with the capacity of the following processing stages. A set of generic filtering intensity, data transfer, and processing archetypes are modeled and evaluated.

Two new approximation schemes for maximizing the weighted number of just-in-time jobs in a proportionate flow shop

Seminarium

Prelegent: Prof. dr hab. Stanisław Gawiejnowicz (Pracownia Algorytmiki)
Data i godzina:  05 listopada 2024 r., g. 11:00

Streszczenie: We propose two new fully polynomial-time approximation schemes for maximizing the weighted number of just-in-time jobs in a multi-machine proportionate flow shop system, applying  recently proposed frameworks for the construction of approximation schemes for monotone dynamic programming formulations. The proposed schemes are faster by a linear factor with respect to the number of jobs than the state-of-the-art scheme for the problem.

 

Theory and practice of deploying linear solvers on large heterogenous computational systems

Seminarium

Prelegent: Dr Katarzyna Świrydowicz (Pacific Northwest National Laboratory, USA)
Data i godzina:  8 stycznia 2024 r., g. 10:30

Abstract: A need to solve an extremely large, sparse linear system commonly occurs in applications that are otherwise HPC-ready. While often overlooked, the repeated estimations of the solutions to linear systems can constitute ninety or more percent of the total application time. In the talk, I will share my experience gained while work on linear solvers developed during multiple subprojects of the Exascale Computing Project, which was a large scientific effort, spanning multiple US universities and national laboratories, and sponsored by the US Department of Energy. I will explain the limitations and challenges in the usage of linear solvers in applications. I will also present a variety of theoretical- and implementation-based techniques that have lead to reliable, GPU-ready linear solvers.

 

Szeregowanie zadań typu malleable

Seminarium

Prelegent: Prof. dr hab. inż. Maciej Drozdowski (Politechnika Poznańska)
Data i godzina:  31 stycznia 2023 r., g. 12:00

Streszczenie: Przedmiotem wystąpienia będą problemy szeregowania zadań typu malleable, tzn. takich które można wykonywać na wielu procesorach jednocześnie, a ponadto liczba używanych procesorów może się zmieniać w czasie. Przedstawione zostaną sformułowanie ogólne, wybrane przypadki wielomianowe, problemy otwarte i NP-trudne, stosowane podejścia.

 

Szeregowanie zadań dla k-dzielnego grafu ograniczeń

Seminarium

Prelegent: Dr Krzysztof Turowski (Uniwersytet Jagielloński w Krakowie)
Data i godzina:  13 grudnia 2022 r., g. 10:30

Streszczenie: Problem szeregowania zadań z grafem ograniczeń, wprowadzony przez Hansa Bodlaendera, Klausa Jansena i Gerharda Woegingera w 1994 roku, polega na przydziale zadań do maszyn z dodatkowym warunkiem, aby zadania sąsiadujące w grafie ograniczeń nie zostały przydzielone do wykonania na tej samej maszynie. W referacie zostaną przedstawione problemy oraz rezultaty otrzymane dla szczególnego przypadku, gdy graf ograniczeń jest grafem pełnym k-dzielnym dla różnego rodzaju maszyn (identycznych, jednorodnych, dowolnych), typów zadań (jednostkowe, dowolnej długości), kryteriów (maksymalny i średni czas zakończenia zadania), a także w różnym ujęciu liczby partycji w grafie (jako część instancji vs. parametr problemu). Zaprezentowane zostaną dowody i różnorodne techniki użyte do ich wyprowadzenia (m.in. programowanie dynamiczne, programowanie liniowe),  a także szereg problemów otwartych, które nadal oczekują na rozwiązanie.

Inhibitory w świecie RNA

Seminarium

Prelegent: Mgr Jarosław Synak (Instytut Chemii Bioorganicznej PAN)
Data i godzina:  6 grudnia 2022 r., g. 10:30

Streszczenie: Współczesne komórki posiadają ogromną liczbę mechanizmów regulujących, które pozwalają dostosować się do zmiennych warunków zewnętrznych, kontrolują podział, a także stabilizują poziomy poszczególnych substancji. Jak wszystko, musiało to kiedyś mieć swój początek, dlatego proponujemy koncepcję takiego mechanizmu w Świecie RNA. Jest on na tyle prosty, że mógł wykształcić się spontanicznie, jednak na tyle złożony, żeby pełnić swoją funkcję – regulować poziom reagentów. Współautorami prezentowanych wyników są Agnieszka Rybarczyk i Jacek Błażewicz.