Prelegent: Dr Joanna Berlińska (Pracownia Algorytmiki)
Data i godzina: 15 grudnia 2020 r., g. 12:30
Streszczenie: W referacie przedstawione zostaną wyniki dotyczące szeregowania zadań w dwumaszynowym flowshopie ze zmieniającą się w czasie ilością dostępnej pamięci. Skupimy się na przypadku zadań z jednostkowymi czasami trwania operacji i różnymi wymaganiami pamięciowymi. Pokażemy, że problem minimalizacji długości uszeregowania jest silnie NP-trudny i przedstawimy dla niego wielomianowy schemat aproksymacji (PTAS). Zaprezentowany zostanie również algorytm dokładny oparty na całkowitoliczbowym programowaniu liniowym oraz algorytmy heurystyczne.