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.

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+\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 2 - ç , 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 dlaP|prec,pj=1|Cmaxze stosunkiem wydajności, o którym mowa w tytule. Poprawia to algorytm Coffmana-Grahama z ograniczonymi2-$(2−\frac{7}{3p+1})$$P|prec,p_j=1|C_{max}$ , gdziepjest 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 P m | C H i n a | C m a x 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 P | p r e c | C m a x 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 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ą $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})$

Ta strona internetowa może zawierać pewne informacje o użytkowaniu:

http://www.mathematik.uni-osnabrueck.de/research/OR/class/