Plánování větrníku - Pinwheel scheduling

V matematice a informatice je plánování větrníku problém je problém v plánování v reálném čase s opakujícími se úkoly o délce jednotky a tvrdými omezeními v době mezi opakováními.

Definice

Vstup do plánování větrníku se skládá ze seznamu úkolů, u nichž se předpokládá, že každý z nich zabere jednotkový čas na instanci. Každý úkol má přidruženou kladnou celočíselnou hodnotu, minimální čas opakování (minimální čas od začátku jedné instance úlohy do další). V daném okamžiku lze provést pouze jeden úkol.^[1]

Požadovaným výstupem je nekonečná sekvence určující, který úkol má být proveden v každé jednotce času. Každá vstupní úloha by se měla objevit nekonečně často v pořadí, přičemž největší mezera mezi dvěma po sobě následujícími instancemi úkolu se maximálně rovná době opakování úkolu.^[1]

Například nekonečně se opakující sekvence abacabacabac ... by byl platný plán větrníku pro tři úkoly A, b, a C s časy opakování, které jsou alespoň 2, 4, respektive 4.

Hustota

Pokud je úkol, který má být naplánován, očíslován od ${ displaystyle 1}$ na ${ displaystyle n}$, nechť ${ displaystyle t_ {i}}$ označte čas opakování úkolu ${ displaystyle i}$. Pak hustota problému plánování větrníku je ${ displaystyle textstyle součet 1 / t_ {i}}$. Aby mohlo existovat řešení, je nutné, aby hustota byla maximálně ${ displaystyle 1}$.^[2]

Tato podmínka hustoty také postačuje k tomu, aby existoval plán ve zvláštním případě, že všechny časy opakování jsou navzájem násobky (například pokud jsou všechny pravomoci dvou ), protože v tomto případě lze problém vyřešit pomocí disjunktu krycí systém.^[1] Mít hustotu nanejvýš ${ displaystyle 1}$ je také dostatečné, když existují přesně dva odlišné časy opakování.^[2] V ostatních případech to však nestačí. Zejména neexistuje žádný plán pro tři položky s opakovanými časy ${ displaystyle t_ {1} = 2}$, ${ displaystyle t_ {2} = 3}$, a ${ displaystyle t_ {3}}$, bez ohledu na to, jak velký ${ displaystyle t_ {3}}$ může být, i když hustota tohoto systému je pouze ${ displaystyle 5/6 + 1 / t_ {3}}$.^[3]

Každá instance plánování větrníku s hustotou maximálně ${ displaystyle 3/4}$ má řešení,^[4] a předpokládalo se, že každá instance má nanejvýš hustotu ${ displaystyle 5/6}$ má řešení.^[3][5] Každá instance s maximálně třemi odlišnými časy opakování a hustotou ${ displaystyle 5/6}$ má řešení.^[5]

Periodicita a složitost

Pokud existuje řešení, lze předpokládat, že je periodické, s periodou maximálně rovnou součinu časů opakování. Není však vždy možné najít opakující se plán subexponenciální délky.^[2]

S kompaktní vstupní reprezentací, která určuje, pro každý odlišný čas opakování, počet objektů, které mají tento čas opakování, je plánování větrníku NP-tvrdé.^[2]

Aplikace

Mezi aplikace plánování větrníku patří plánování komunikace mezi satelity a pozemní stanicí, plánování údržby sbírky objektů (například výměna oleje v automobilech), počítačové zpracování multimediálních dat,^[5] a řešení sporů v bezdrátových počítačových sítích v reálném čase.^[6]

Reference

externí odkazy

• Plánování větrníku (1989) Douglas B.West, University of Illinois