Planowanie wiatraczka

W matematyce i informatyce problem planowania wiatraczka jest problemem w planowaniu w czasie rzeczywistym z powtarzającymi się zadaniami o jednostkowej długości i twardymi ograniczeniami czasu między powtórzeniami.

Definicja

Dane wejściowe do planowania wiatraczka składają się z listy zadań, z których każde ma zająć jednostkę czasu na instancję. Każdemu zadaniu przypisana jest dodatnia liczba całkowita, czyli minimalny czas powtarzania (minimalny czas od początku jednej instancji zadania do następnej). W danym momencie można wykonać tylko jedno zadanie.

Pożądany wynik to nieskończona sekwencja określająca, które zadanie należy wykonać w każdej jednostce czasu. Każde zadanie wejściowe powinno pojawiać się nieskończenie często w sekwencji, z największą przerwą między dwiema kolejnymi instancjami zadania co najwyżej równą czasowi powtórzenia zadania.

Na przykład nieskończenie powtarzająca się sekwencja abacabacabac... byłaby prawidłowym harmonogramem wiatraczka dla trzech zadań a , b i c z czasami powtórzeń wynoszącymi odpowiednio co najmniej 2, 4 i 4.

Gęstość

Jeśli zadania, które mają zostać zaplanowane, są ponumerowane od $niech$$.$ oznaczają $i$ powtarzania ja $\ displaystyle$ } Wtedy gęstość problemu planowania wiatraczka wynosi ${\ displaystyle \ textstyle \ suma 1/t_ {i}}$ . Aby rozwiązanie istniało, konieczne jest, aby gęstość wynosiła co najwyżej ${\ displaystyle 1}$ .

Ten warunek dotyczący gęstości jest również wystarczający, aby istniał harmonogram w szczególnym przypadku, gdy wszystkie czasy powtórzeń są wzajemnie wielokrotnościami (na przykład, jeśli wszystkie są potęgami dwójki ), ponieważ w tym przypadku można rozwiązać problem za pomocą rozłącznego pokrycia system . Posiadanie co najwyżej gęstości $jest$ wystarczające, gdy istnieją dokładnie dwa różne czasy powtórzeń. Jednak w innych przypadkach nie jest to wystarczające. W szczególności nie ma harmonogramu dla trzech elementów z powtórzeniami ${\ displaystyle t_ {1} = 2}$ , ${\ Displaystyle t_ {2} = 3}$ i ${\ Displaystyle$$t_ {3}}$ , bez względu na to, jak duży , nawet jeśli gęstość tego systemu jest tylko ${\ Displaystyle 5/6 + 1/t_ {3}}$ .

Każdy przypadek planowania wiatraczka z co najwyżej gęstością $ma$$,$ każdy przypadek z co najwyżej gęstością . $ma$ instancja z trzema różnymi czasami powtarzania i co najwyżej rozwiązanie

Okresowość i złożoność

Gdy istnieje rozwiązanie, można założyć, że rozwiązanie jest okresowe, z okresem co najwyżej równym iloczynowi czasów powtórzeń. Jednak nie zawsze jest możliwe znalezienie powtarzającego się harmonogramu o długości poniżej wykładniczej.

Ze zwartą reprezentacją wejściową, która określa, dla każdego odrębnego czasu powtórzenia, liczbę obiektów, które mają ten czas powtórzenia, planowanie wiatraczka jest NP-trudne .

Aplikacje

Zastosowania planowania wiatraczka obejmują planowanie komunikacji między satelitami a stacją naziemną, planowanie konserwacji zbioru obiektów (takich jak wymiana oleju w samochodach), komputerowe przetwarzanie danych multimedialnych i rozwiązywanie rywalizacji w bezprzewodowych sieciach komputerowych w czasie rzeczywistym.

Linki zewnętrzne

• Planowanie wiatraczka (1989) , Douglas B. West, University of Illinois