Algorytmy aproksymacji czasu wielomianowego do planowania maszyny: ile pozostało otwartych problemów?

22

W 1999 r. Petra Schuurman i Gerhard J. Woeginger opublikowali artykuł „Wielomianowe algorytmy aproksymacji czasu dla szeregowania maszynowego: dziesięć otwartych problemów” . Od tego czasu, o ile mi wiadomo, nie pojawiły się recenzje, które dotyczyłyby tej samej listy problemów. Byłoby więc świetnie i przydatne, gdyby każdy z nas mógł sporządzić takie podsumowanie niektórych z dziesięciu otwartych problemów i wnieść je tutaj.

Dai Le
źródło
Nie sądzę, że trzeba to zrobić CW ...
Suresh Venkat
@Suresh Venkat: Jak usunąć CW?
Oleksandr Bondarenko
Niestety nie ma sposobu, aby zamienić pytanie wiki społeczności na pytanie inne niż CW. Dodanie tej funkcji do silnika stosu wymiany jest wymagane na stronie: meta.stackexchange.com/questions/6821/…
Tsuyoshi Ito
Zobacz także najczęściej zadawane pytania dotyczące użycia znacznika CW: meta.cstheory.stackexchange.com/questions/225/…
Suresh Venkat

Odpowiedzi:

16

Minimalizacja makespan na identycznych maszynach z ograniczeniami pierwszeństwa

Otwarte Problem 1. Zapewnić wynik inapproximability dla P | p r e c | C m a x .4/3+δP|prec|Cmax

Najpierw przychodzi mi na myśl tegoroczna praca Oli Svensson „Warunkowa twardość pierwszeństwa Ograniczone planowanie na identycznych maszynach”. W swojej pracy Ola to potwierdza

„, jeżeli problem pojedyncze urządzenie jest trudne do w przybliżeniu w czynnik następnie rozważana problemu urządzenie równoległe, nawet w przypadku, jednostka przetwarzania razy, trudno jest w przybliżeniu w czynnik 2 - ç , gdzie ζ tendencję do 0 ponieważ ϵ zmierza do 0. ”2ϵ2ζζϵ

W 2008 roku został opublikowany papier „Pierwszeństwo ograniczone harmonogram w · optymalne "opisujące algorytm dlaP|prec,pj=1|Cmaxze stosunkiem wydajności, o którym mowa w tytule. Poprawia to algorytm Coffmana-Grahama z ograniczonymi2-2(273p+1)P|prec,pj=1|Cmax , gdziepjest liczbą komputerów.22pp

Artykuł „Algorytmy aproksymacyjne dla planowania zadań z ograniczeniami pierwszeństwa łańcucha” autorstwa Jansena i Solis-Oba zawiera PTAS dla , aw konsekwencji dla P m | C H i n a | C m a x jako szczególny przypadek poprzedniego problemu.Qm|chains|CmaxPm|chains|Cmax

W tym roku ukazał się artykuł „Schematy aproksymacyjne dla planowania zadań z ograniczeniami pierwszeństwa łańcucha” autorstwa Jansena i Solis-Oba (wersja dziennikowa poprzedniego), który dotyczy PTAS dla ze stałą liczbą zadań w każdym łańcuchu i P | p r e c | C m a x ze stałą liczbą zadań w podłączonym komponencie każdego zamówienia.P|chains|CmaxP|prec|Cmax

Minimalizacja makespan na jednolitych maszynach z ograniczeniami pierwszeństwa

Artykuł z 2003 roku „Algorytmy aproksymacyjne do planowania zadań z ograniczeniami pierwszeństwa łańcucha” autorstwa Jansena i Solis-Oba zawiera PTAS dla .Qm|chains|Cmax

Minimalizacja makespan pod pierwszeństwem ograniczeń komunikacyjnych

Minimalizacja makespan na niepowiązanych maszynach

Minimalizacja makespan w otwartych sklepach

Minimalizacja makespan w sklepach przepływowych

W artykule Nagarajana i Sviridenko z 2008 r. „Tight Bounds for Permutation Flow Shop Scheduling” możemy znaleźć górną granicę stosunku między optymalnym okresem rozproszenia a rozpiętością najlepszego harmonogramu permutacji. Ta granica jest współczynnikiem przybliżenia proponowanego algorytmu i jest najlepsza z możliwych w przypadku algorytmów opartych na trywialnych dolnych granicach, do czynnik. Nawiasem mówiąc, proponowane algorytmy to obecnie te o najlepszych stosunkach aproksymacyjnych.22

Minimalizacja makespan w sklepach pracy

Otwarty problem 7. Zdecyduj, czy istnieje algorytm aproksymacji czasu wielomianowego dla którego najgorsze działanie jest niezależne od liczby m maszyn i / lub niezależne od maksymalnej liczby μ operacji. Dostarczenie 5 / 4 + δ wynik inapproximability do J | | C m a x . Podaj wynik niedoceniania dla J | | C m a x, którego wartość rośnie wraz z liczbą mJ||Cmaxmμ5/4+δJ||CmaxJ||Cmaxm maszyn do nieskończoności.

J2||Cmaxμ

J||CmaxO((loglb)1ϵ)NPZTIME(2lognO(1/ϵ))J2||CmaxNPDTIME(nO(logn))

Całkowity czas realizacji zadania bez ograniczeń pierwszeństwa

Całkowity czas realizacji zadania z uwzględnieniem ograniczeń pierwszeństwa

1|prec|Cj1|prec|wjCj2ϵ

W „Optymalnym teście długiego kodu z jednym wolnym bitem” Bansal i Khot udowodnili, że tak jest, ale zakładając nowy wariant unikalnej gry.

Kryteria czasu przepływu

1|pmtn;rj|wjFjP|pmtn;rj|Fj

O(1)1|pmtn;rj|wjFjO(1)

Ω(logPloglogP)P|pmtn;rj|FjΩ(logPloglogP)

Oleksandr Bondarenko
źródło