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

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

PDF: Algorytmy aproksymacji czasu wielomianowego do planowania maszyn: Dziesięć otwartych problemów

— Daniel Apon

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

Minimalizacja makespan na identycznych maszynach z ograniczeniami pierwszeństwa

Otwarte Problem 1. Zapewnić wynik inapproximability dla . $4/3+\delta$ $P|prec|C_{max}$

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 , gdzie tendencję do 0 ponieważ zmierza do 0. ” $2-\epsilon$ $2-\zeta$ $\zeta$ $\epsilon$

W 2008 roku został opublikowany papier „Pierwszeństwo ograniczone harmonogram w · optymalne "opisujące algorytm dlaze stosunkiem wydajności, o którym mowa w tytule. Poprawia to algorytm Coffmana-Grahama z ograniczonymi $(2−\frac{7}{3p+1})$ $P|prec,p_j=1|C_{max}$ , gdziejest liczbą komputerów. $2-\frac{2}{p}$ $p$

Artykuł „Algorytmy aproksymacyjne dla planowania zadań z ograniczeniami pierwszeństwa łańcucha” autorstwa Jansena i Solis-Oba zawiera PTAS dla , aw konsekwencji dla jako szczególny przypadek poprzedniego problemu. $Qm|chains|C_{max}$ $Pm|chains|C_{max}$

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 ze stałą liczbą zadań w podłączonym komponencie każdego zamówienia. $P|chains|C_{max}$ $P|prec|C_{max}$

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|C_{max}$

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. $2\sqrt{2}$

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 maszyn i / lub niezależne od maksymalnej liczby operacji. Dostarczenie wynik inapproximability do . Podaj wynik niedoceniania dla którego wartość rośnie wraz z liczbą $J||C_{max}$ $m$ $\mu$ $5/4+\delta$ $J||C_{max}$ $J||C_{max}$ $m$ maszyn do nieskończoności.

$J2||C_{max}$ $\mu$ $\ne$

$J||C_{max}$ $O((\log lb)^{1-\epsilon})$ $NP\subseteq ZTIME(2^{\log n^{O(1/\epsilon)}})$ $J2||C_{max}$ $NP\subseteq DTIME(n^{O(\log n)})$

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

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

$1|prec|\sum C_j$ $1|prec|\sum w_jC_j$ $2−\epsilon$

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;r_j|\sum w_jF_j$ $P|pmtn;r_j|\sum F_j$

$O(1)$ $1|pmtn;r_j|\sum w_jF_j$ $O(1)$

$\Omega(\sqrt{\frac{\log P}{\log\log P}})$ $P|pmtn;r_j|\sum F_j$ $\Omega(\frac{\log P}{\log\log P})$

— Oleksandr Bondarenko
źródło