Planowanie zadań z problemem wąskiego gardła

Biorąc pod uwagę zadań każde zadanie wymaga czasu czasu.J 1 , J 2 , . . . , J n T i > 0 , T i ∈ $n$$J_1,J_2,...,J_n$$T_i > 0, T_i \in N$

Każde zadanie musi być wstępnie przetworzone i przetworzone przez pojedynczą maszynę M, która może obsłużyć tylko 1 zadanie na raz, a obie fazy wymagają 1 jednostki czasu. Po wstępnym przetworzeniu zadanie jest wysyłane do maszyny o nieograniczonej mocy (która może obsługiwać równolegle nieograniczoną liczbę zadań) i będzie gotowe w czasie , a następnie musi zostać przesłane ( natychmiast ) do maszyny M ponownie w celu przetwarzanie końcowe.T $J_i$$T_i$

Związany z tym problem decyzyjny to:

Wejście: Czasy przetwarzania z pracy, liczba całkowita Pytanie: można przetwarzać wszystkie zadania w czasie za pomocą powyższego modelu "wąskiego gardła"? N K ≥ 2 $T_i >0, T_i \in \mathbb{N}$$N$$K\geq 2N$
$\leq K$

Czy ten problem ma nazwę?
Jaka jest jego złożoność? (czy jest w czy jest -kompletny?) N $\sf{P}$$\sf{NP}$

UPDATE 29 marca:
Jak słusznie zauważył przez M.Cafaro w swojej odpowiedzi, problem jest podobny do Unconstrained Minimalna zakończeniem czasu problem (UMFT) (patrz rozdział 17 z Handbook of Scheduling algorytmów ), który jest -hard (potwierdzone w W. Kern i W. Nawijn, „Planowanie zadań wielozadaniowych z opóźnieniami czasowymi na jednej maszynie”, University of Twente, 1993). Jak widzę, istnieją pewne różnice, ponieważ w moim modelu:$\sf{NP}$

• czas przetwarzania wstępnego / końcowego jest stały (1 jednostka czasu)
• jak tylko zadanie zostanie ukończone, musi być natychmiast przetworzone (model UMFT dopuszcza opóźnienia)

Nie znalazłem dowodu Kern & Nawijn w Internecie, więc nadal nie wiem, czy powyższe ograniczenia zmieniają trudność problemu.

Wreszcie możesz pomyśleć cały proces jak pojedynczy robot kuchenny z dużym piekarnikiem; robot może przygotowywać różne rodzaje żywności pojedynczo (wszystkie wymagają tego samego czasu przygotowania), wkładać je do piekarnika, a gdy tylko zostaną ugotowane, musi je wyjąć z piekarnika i dodać trochę zimnych składników ... „ problem robota kucharza ” :-)

Pytanie zostało udowodnione jako trudne dla NP w „Minimalizowaniu makespanu w sklepie z dwiema maszynami z opóźnieniami i operacjami jednostkowymi - NP-Hard” W. Yu, H. Hoogeveen i JK Lenstra (2004). Jest to udowodnione w części 9 artykułu:

Twierdzenie 24. Problem minimalizacji makespan na pojedynczej maszynie z dwiema jednostkowymi operacjami czasu na zadanie z dowolnymi opóźnieniami pośrednimi jest silnie NP-trudny.

Dokładny wzór studiował tutaj jest to, że praca składa się z dwóch operacji, że czas podjąć jednostka rozdzielone przez jakiś czas opóźnienia T i . Problem jest silnie NP-zupełny zarówno wtedy, gdy dokładna wartość opóźnienia T i jest określona dla każdego zadania, oraz gdy określony jest minimalny czas opóźnienia dla każdego zadania.$i$$T_i$$T_i$

Wygląda to na tak zwany model planowania master-slave wprowadzony przez Sahni . W szczególności twój problem dotyczy systemów Master-Slave typu Single-Master. Możesz wyróżnić kilka przypadków:

1) Jeśli nie dodasz żadnych dodatkowych ograniczeń w kolejności wykonywania zadania (jak w twoim przypadku), problem nazywa się nieograniczonym problemem minimalnego czasu zakończenia (UMFT) i okazało się, że jest trudny do wykonania;

2) Te same zamówienia przed przetwarzaniem i po przetworzeniu: możliwe jest zaprojektowanie algorytmu celu skonstruowania zamówienia z zachowaniem harmonogramu minimalnego czasu zakończenia (OPMFT);$O(n \log n)$

Dlatego też, w przypadku 1 problem jest -hard, gdy jest w P w przypadku 2.$NP$$P$

Dodatkowe powiązane problemy to:

3) Postprocessing w odwrotnym porządku: Dla dowolnej permutacji przetwarzania wstępnego,$σ$$σ$

4) ograniczenie związane z brakiem oczekiwania na proces:

a) [MFTNW] Minimalizuj czas zakończenia z zastrzeżeniem ograniczenia braku oczekiwania na proces; b) [OP-MFTNW] To jest wersja MFTNW zachowująca porządek. Oznacza to, że należy zminimalizować czas zakończenia z zastrzeżeniem ograniczeń związanych z brakiem oczekiwania na proces i zachowaniem kolejności; c) [RO-MFTNW] Minimalizuj czas zakończenia z zastrzeżeniem ograniczeń związanych z brakiem oczekiwania na proces i odwrotnym zamówieniem.

Problemy i są trudne dla NP, podczas gdy akceptuje wielomianowe rozwiązanie czasowe.b $a$$b$$c$

Dodatkowe informacje w Podręczniku planowania , rozdział 17.