Planowanie stochastyczne

Planowanie stochastyczne dotyczy problemów planowania obejmujących losowe atrybuty, takie jak losowe czasy przetwarzania, losowe terminy, losowe wagi i stochastyczne awarie maszyn. Główne zastosowania pojawiają się między innymi w systemach produkcyjnych, systemach komputerowych, systemach komunikacyjnych, logistyce i transporcie oraz uczeniu maszynowym. ^{[ potrzebne źródło ]}

Wstęp

Celem stochastycznych problemów z planowaniem mogą być regularne cele, takie jak minimalizacja całkowitego czasu przepływu, czasu wykonania lub całkowitego kosztu spóźnienia w przypadku niedotrzymania terminów; lub mogą to być nieregularne cele, takie jak minimalizacja zarówno kosztów wczesności, jak i opóźnień w wykonaniu zadań lub całkowity koszt planowania zadań w przypadku prawdopodobnego nadejścia katastrofalnego zdarzenia, takiego jak silny tajfun.

Na wydajność takich systemów, ocenianą za pomocą regularnej miary wydajności lub miary nieregularnej wydajności, może znacząco wpływać polityka planowania przyjęta w celu nadania priorytetu dostępowi zadań do zasobów w czasie. Celem planowania stochastycznego jest zidentyfikowanie zasad planowania, które mogą zoptymalizować cel.

Problemy planowania stochastycznego można podzielić na trzy szerokie typy: problemy dotyczące planowania partii zadań stochastycznych, problemy wielorękiego bandyty oraz problemy dotyczące planowania systemów kolejkowych. Te trzy typy zwykle zakładają, że dostępne są kompletne informacje w tym sensie, że rozkłady prawdopodobieństwa zaangażowanych zmiennych losowych są znane z góry. Kiedy takie rozkłady nie są w pełni określone i istnieje wiele konkurujących rozkładów do modelowania zmiennych losowych będących przedmiotem zainteresowania, problem jest określany jako niepełna informacja. Metoda Bayesowska została zastosowana do rozwiązywania stochastycznych problemów szeregowania z niepełnymi informacjami.

Planowanie partii zadań stochastycznych

$maszyn,$ $aby$ partia zadań z losowymi czasami przetwarzania, których rozkłady są znane, musi zostać wykonana przez zestaw zoptymalizować dany cel wydajności.

Najprostszym modelem w tej klasie jest problem sekwencjonowania zestawu $na$ jednej maszynie, aby zminimalizować oczekiwany ważony czas przepływu. Czasy przetwarzania ${i} ($ niezależnymi zmiennymi losowymi o ogólnym rozkładzie ze średnią dla zadania $)}$ ${\ Displaystyle G_$ . Dopuszczalne zasady muszą być nieprzewidujące (decyzje dotyczące harmonogramu są oparte na historii systemu do chwili obecnej włącznie) i nieprzewidujące (przetwarzanie zadania musi przebiegać nieprzerwanie aż do zakończenia po rozpoczęciu).

Niech ${\ Displaystyle w_ {i} \ geq 0}$ oznacza stawkę kosztów ponoszonych w jednostce czasu w systemie dla zadania $Displaystyle$ do ${\ tylda {C}$ oznacza losowy czas zakończenia. Niech oznacza klasę wszystkich dopuszczalnych zasad i niech mi $_ {\ pi} [\ cdot ]}$ oznacza oczekiwanie w ramach polityki $\ Displaystyle \ Pi}$ ${\ Displaystyle \ pi \ w \ Pi}$ . Problem można określić jako

{\ Displaystyle \ min _ {\ pi \ w \ Pi} w_ {1} E_ {\ pi} [{\ tylda {C}} _ ​​{1}] + \ cdots + w_ {n} E_ {\ pi} [ {\tylda {C}}_ {n}].}

Optymalne rozwiązanie w szczególnym deterministycznym przypadku jest podane przez regułę Smitha o najkrótszym ważonym czasie przetwarzania: układaj zadania w porządku nierosnącym według wskaźnika priorytetu w ja p ja {\ $} p_ {i}}$ . Naturalne rozszerzenie reguły Smitha jest również optymalne dla powyższego modelu stochastycznego.

Ogólnie rzecz biorąc, reguła, która nadaje wyższy priorytet zadaniom o krótszym oczekiwanym czasie przetwarzania, jest optymalna dla celu flowtime przy następujących założeniach: kiedy wszystkie rozkłady czasu przetwarzania zadania są wykładnicze; gdy wszystkie zadania mają wspólny ogólny rozkład czasu przetwarzania z niemalejącą funkcją stopy hazardu; oraz gdy rozkłady czasu przetwarzania zadań są uporządkowane stochastycznie.

Problemy z wielorękimi bandytami

wielorękich bandytów tworzą szczególny typ optymalnej alokacji zasobów (zwykle pracujący z przydziałem czasu), w którym pewna liczba maszyn lub procesorów ma być przydzielona do obsługi zestawu konkurencyjnych projektów (nazywanych ramionami). W typowych ramach system składa się z pojedynczej maszyny i zestawu stochastycznie niezależnych projektów, które będą zapewniać losowe nagrody w sposób ciągły lub w określonych dyskretnych punktach czasowych, kiedy są obsługiwane. Celem jest maksymalizacja oczekiwanych łącznych obniżonych nagród w stosunku do wszystkich dynamicznie zmienianych polis.

Pierwsza wersja problemów wielobandyckich została sformułowana w obszarze projektów sekwencyjnych przez Robbinsa (1952). Od tego czasu nie było żadnego istotnego postępu w ciągu dwóch dekad, aż Gittins i jego współpracownicy dokonali słynnych osiągnięć badawczych w Gittins (1979), Gittins i Jones (1974), Gittins i Glazebrook (1977) oraz Whittle (1980) pod Ustawienia Markowa i semi-Markowa. W tym wczesnym modelu każde ramię jest modelowane przez proces Markowa lub semi-Markowa, w którym punkty czasowe dokonywania przejść między stanami są epokami decyzyjnymi. Maszyna może w każdej epoce wybrać ramię do obsłużenia z nagrodą reprezentowaną jako funkcja bieżącego stanu przetwarzanego ramienia, a rozwiązanie charakteryzuje się wskaźnikami alokacji przypisanymi do każdego stanu, które zależą tylko od stanów ramion. Indeksy te są zatem znane jako indeksy Gittinsa, a optymalne polityki są zwykle nazywane indeksowania Gittinsa , ze względu na jego renomowany wkład.

Wkrótce po przełomowym artykule Gittinsa Whittle (1981) zbadał rozszerzenie problemu rozgałęzionych bandytów w celu modelowania stochastycznych przybyszów (znane również jako problem otwartego bandyty lub bandyty zdobywającego broń). Inne rozszerzenia obejmują modele niespokojnego bandyty, sformułowane przez Whittle'a (1988), w których każde ramię ewoluuje niespokojnie zgodnie z dwoma różnymi mechanizmami (moda bezczynności i moda zajętości), oraz modele z kosztami/opóźnieniami przełączania autorstwa Van Oyena i in. (1992), którzy wykazali, że żadna polityka indeksowa nie jest optymalna, gdy przechodzenie między ramionami wiąże się z kosztami/opóźnieniami.

Harmonogramowanie systemów kolejkowych

Modele tej klasy zajmują się problemami projektowania optymalnych dyscyplin usług w systemach kolejkowych, w których zadania do wykonania pojawiają się w losowych epokach w czasie, zamiast być dostępne na początku. Główną klasą modeli w tym ustawieniu są wieloklasowe sieci kolejkowe (MQN), szeroko stosowane jako wszechstronne modele komunikacji komputerowej i systemów produkcyjnych.

Najprostsze typy MQN obejmują planowanie wielu klas zadań na jednym serwerze. Podobnie jak w przypadku dwóch omówionych wcześniej kategorii modeli, wykazano, że proste zasady indeksu priorytetów są optymalne dla różnych takich modeli.

Bardziej ogólne modele MQN obejmują takie cechy, jak czasy przezbrojenia w przypadku zmiany usługi z jednej klasy zadań na inną (Levy i Sidi, 1990) lub wiele stacji przetwarzania, które zapewniają obsługę odpowiednich, nienakładających się podzbiorów klas zadań. Ze względu na trudność takich modeli badacze postawili sobie za cel zaprojektowanie stosunkowo prostych zasad heurystycznych, które osiągnęłyby wydajność bliską optymalnej.

Szeregowanie stochastyczne z niepełnymi informacjami

Większość badań nad stochastycznymi modelami szeregowania została w dużej mierze oparta na założeniu pełnej informacji, w tym sensie, że rozkłady prawdopodobieństwa zaangażowanych zmiennych losowych, takich jak czasy przetwarzania i czasy włączenia/wyłączenia maszyny, są całkowicie określone a priori .

Istnieją jednak okoliczności, w których informacje są dostępne tylko częściowo. Przykłady planowania z niepełnymi informacjami można znaleźć między innymi w oczyszczaniu środowiska, zarządzaniu projektami, eksploracji ropy naftowej, harmonogramowaniu czujników w robotach mobilnych i modelowaniu czasu cyklu.

W wyniku niekompletnych informacji może istnieć wiele konkurencyjnych rozkładów do modelowania zmiennych losowych będących przedmiotem zainteresowania. Skuteczne podejście opracowali Cai i in. (2009), aby rozwiązać ten problem, w oparciu o aktualizację informacji Bayesa. Identyfikuje każdą konkurującą dystrybucję poprzez realizację zmiennej losowej, powiedzmy ${\ displaystyle \ Theta}$ . Początkowo ${\ displaystyle \ Theta}$ ma wcześniejszą dystrybucję opartą na historycznych informacjach lub założeniach (które mogą nie mieć charakteru informacyjnego, jeśli żadne informacje historyczne nie są dostępne). Informacje o ${\ Displaystyle \ Theta}$ mogą być aktualizowane po zaobserwowaniu realizacji zmiennych losowych. Kluczową kwestią przy podejmowaniu decyzji jest to, jak wykorzystać zaktualizowane informacje do udoskonalenia i ulepszenia decyzji. Kiedy polityka planowania jest statyczna w tym sensie, że nie zmienia się w czasie, identyfikowane są optymalne sekwencje, aby zminimalizować oczekiwaną zdyskontowaną nagrodę i stochastycznie zminimalizować liczbę opóźnionych zadań w ramach wspólnego wykładniczego terminu wykonania. Kiedy polityka planowania jest dynamiczna w tym sensie, że może wprowadzać korekty w trakcie procesu na podstawie aktualnych informacji, opracowywany jest późniejszy indeks Gittinsa, aby znaleźć optymalną politykę, która minimalizuje oczekiwaną zdyskontowaną nagrodę w klasie zasad dynamicznych.