Intervalové plánování - Interval scheduling

Intervalové plánování je třída problémů v počítačová věda, zejména v oblasti algoritmus design. Problémy berou v úvahu soubor úkolů. Každý úkol je reprezentován znakem interval popisující čas, ve kterém je třeba provést. Například úkol A může běžet od 2:00 do 5:00, úkol B může běžet od 4:00 do 10:00 a úkol C může běžet od 9:00 do 11:00. Podmnožina intervalů je kompatibilní pokud se žádné dva intervaly nepřekrývají. Například podmnožina {A, C} je kompatibilní, stejně jako podmnožina {B}; ale ani {A, B} ani {B, C} nejsou kompatibilní podmnožiny, protože se odpovídající intervaly v každé podmnožině překrývají.

The problém s maximalizací intervalového plánování (ISMP) je najít největší kompatibilní sadu - sadu nepřekrývajících se intervalů maximální velikosti. Cílem je provést co nejvíce úkolů.

V upgradované verzi problému jsou intervaly rozděleny do skupin. Podmnožina intervalů je kompatibilní pokud se žádné dva intervaly nepřekrývají a navíc žádné dva intervaly nepatří do stejné skupiny (tj. podmnožina obsahuje nanejvýš jeden reprezentativní interval každé skupiny).

The problém s rozhodnutím o skupinovém intervalu (GISDP) je rozhodnout, zda existuje kompatibilní sada, ve které jsou zastoupeny všechny skupiny. Cílem je provést jeden reprezentativní úkol z každé skupiny. GISDPk je omezená verze GISDP, ve které je maximálně počet intervalů v každé skupině k.

The problém s maximalizací plánování skupinových intervalů (GISMP) je najít největší kompatibilní sadu - sadu nepřekrývajících se zástupců maximální velikosti. Cílem je provést reprezentativní úkol z co největšího počtu skupin. GISMPk je omezená verze GISMP, ve které je maximálně počet intervalů v každé skupině k. Tento problém se často nazývá JISPk, kde J znamená Práce.

GISMP je nejobecnějším problémem; další dva problémy lze považovat za zvláštní případy:

• ISMP je zvláštní případ, kdy každý úkol patří do své vlastní skupiny (tj. Rovná se GISMP1).
• GISDP je problém rozhodování, zda se maximum přesně rovná počtu skupin.

Maximalizace intervalu plánování

^[1]

Několik algoritmů, které na první pohled vypadají slibně, ve skutečnosti nenajdou optimální řešení:

• Výběr intervalů, které začínají nejdříve, není optimálním řešením, protože pokud je nejdříve interval velmi dlouhý, jeho přijetí by nás přimělo odmítnout mnoho dalších kratších požadavků.
• Výběr nejkratších intervalů nebo výběr intervalů s nejmenším počtem konfliktů také není optimální.

Chamtivé polynomiální řešení

Následující chamtivý algoritmus najde optimální řešení:

1. Vyberte interval, X, nejdříve dokončovací čas.
2. Odstranit Xa všechny intervaly se protínají X, ze sady intervalů kandidátů.
3. Opakujte, dokud není sada intervalů kandidátů prázdná.

Kdykoli vybereme interval v kroku 1, možná budeme muset odstranit mnoho intervalů v kroku 2. Všechny tyto intervaly však nutně protínají dobu dokončení X, a tím se navzájem protínají (viz obrázek). Proto maximálně 1 z těchto intervalů může být v optimálním řešení. Proto pro každý interval v optimálním řešení existuje interval v chamtivém řešení. To dokazuje, že chamtivý algoritmus skutečně najde optimální řešení.

Formálnější vysvětlení poskytuje a Argument nabíjení.

Chamtivý algoritmus může být proveden v čase O (n log n), kde n je počet úkolů pomocí kroku předzpracování, ve kterém jsou úkoly seřazeny podle doby dokončení.

Rozhodnutí o skupinovém intervalu

NP-úplné, když některé skupiny obsahují 3 nebo více intervalů

GISDPk je NP úplný, když ${displaystyle kgeq 3}$,^[2] i když mají všechny intervaly stejnou délku.^[3] To lze prokázat snížením z následující verze Booleovský problém uspokojivosti:

Nechat ${displaystyle X = {x_ {1}, x_ {2}, ..., x_ {p}}}$ být množinou booleovských proměnných. Nechat ${displaystyle C = {c_ {1}, c_ {2}, ..., c_ {q}}}$ být soubor

klauzule nad X takové, že (1) každá klauzule v C hasat většina tří literálů a (2) každá proměnná je omezena na to, aby se objevila jednou nebo dvakrát pozitivně a jednou negativně celkově C. Rozhodněte, zda existuje přiřazení k proměnným proměnné X tak, že každá klauzule v C má alespoň jeden skutečný literál.

Tato verze byla zobrazena ^[4] být NP-kompletní stejně jako neomezená verze.

Vzhledem k instanci tohoto problému uspokojivosti vytvořte následující instanci GISDP. Všechny intervaly mají délku 3, takže stačí představit každý interval podle jeho počátečního času:

• Pro každou proměnnou ${displaystyle x_ {i}}$ (pro i=1,...,p), vytvořte skupinu se dvěma intervaly: jeden od ${displaystyle 50i-10}$ (představující úkol ${displaystyle x_ {i} = false}$) a další začínající na ${displaystyle 50i + 10}$ (představující úkol ${displaystyle x_ {i} = true}$).
• Za každou klauzuli ${displaystyle c_ {j}}$ (pro j=1,...,q), vytvořte skupinu s následujícími intervaly:
  • Pro každou proměnnou ${displaystyle x_ {i}}$ , který se zdá pozitivní pro za prvé čas v C - interval začínající na ${displaystyle 50i-12}$.
  • Pro každou proměnnou ${displaystyle x_ {i}}$ , který se zdá pozitivní pro druhý čas v C - interval začínající na ${displaystyle 50i-8}$. Všimněte si, že oba tyto intervaly protínají interval ${displaystyle 50i-10}$, spojený s ${displaystyle x_ {i} = false}$.
  • Pro každou proměnnou ${displaystyle x_ {i}}$ to se objeví negativně - interval začínající na ${displaystyle 50i + 8}$. Tento interval protíná interval ${displaystyle 50i + 10}$ spojený s ${displaystyle x_ {i} = true}$.

Všimněte si, že nedochází k překrývání intervalů ve skupinách spojených s různými klauzulemi. To je zajištěno, protože proměnná se objeví nejvýše dvakrát pozitivně a jednou negativně.

Vytvořený GISDP má proveditelné řešení (tj. Plánování, ve kterém je zastoupena každá skupina), právě když má daná sada booleovských klauzulí uspokojivé přiřazení. Proto je GISDP3 NP-kompletní, a tak je GISDPk pro každého ${displaystyle kgeq 3}$.

Polynom, když všechny skupiny obsahují maximálně 2 intervaly

GISDP2 lze vyřešit v polynomiálním čase následující redukcí na 2 - uspokojivost problém:^[3]

• Pro každou skupinu i vytvořte dvě proměnné představující dva intervaly: ${displaystyle x_ {i}}$ a ${displaystyle y_ {i}}$.
• Pro každou skupinu i, vytvořte klauzule: ${displaystyle x_ {i} šálek y_ {i}}$ a ${displaystyle eg {x_ {i}} cup eg eg {y_ {i}}}$, které představují tvrzení, že by měl být vybrán právě jeden z těchto dvou intervalů.
• Za každé dva protínající se intervaly (tj. ${displaystyle x_ {i}}$ a ${displaystyle y_ {j}}$) vytvořte klauzuli: ${displaystyle eg {x_ {i}} cup eg {y_ {j}}}$, které představují tvrzení, že by měl být vybrán maximálně jeden z těchto dvou intervalů.

Tato konstrukce obsahuje maximálně O (n²) věty (jedna pro každou křižovatku mezi intervaly, plus dvě pro každou skupinu). Každá klauzule obsahuje 2 literály. O uspokojivosti těchto vzorců lze rozhodnout časově lineárně v počtu doložek (viz 2-SAT ). Proto lze GISDP2 řešit v polynomiálním čase.

Maximalizace skupinového intervalu

MaxSNP-complete, když některé skupiny obsahují 2 nebo více intervalů

GISMPk je NP-úplný, i když ${displaystyle kgeq 2}$.^[5]

Navíc GISMPk je MaxSNP -kompletní, tj. nemá PTAS, pokud P = NP. To lze dokázat ukázkou redukce zachování aproximace z MAX 3-SAT-3 na GISMP2.^[5]

Polynomiální 2-aproximace

Následující chamtivý algoritmus najde řešení, které obsahuje alespoň 1/2 optimálního počtu intervalů:^[5]

1. Vyberte interval, X, nejdříve dokončovací čas.
2. Odstranit Xa všechny intervaly se protínají Xa všechny intervaly ve stejné skupině X, ze sady intervalů kandidátů.
3. Pokračujte, dokud není sada intervalů kandidátů prázdná.

Formální vysvětlení podává a Argument nabíjení.

Faktor přiblížení 2 je těsný. Například v následující instanci GISMP2:

• Skupina č. 1: {[0..2], [4..6]}
• Skupina č. 2: {[1..3]}

Chamtivý algoritmus vybere pouze 1 interval [0..2] ze skupiny # 1, zatímco optimální plánování je vybrat [1..3] ze skupiny # 2 a poté [4..6] ze skupiny # 1.

Aproximační algoritmy založené na LP

Pomocí techniky Relaxace lineárního programování, je možné aproximovat optimální plánování s mírně lepšími aproximačními faktory. Aproximační poměr prvního takového algoritmu je asymptoticky 2, když k je velký, ale když k = 2 algoritmus dosahuje přibližného poměru 5/3.^[5] Faktor přiblížení pro libovolné k byl později vylepšen na 1,582.^[6]

Grafická znázornění

Problém s intervalovým plánováním lze popsat pomocí průsečíkový graf, kde každý vrchol je interval, a mezi dvěma vrcholy je hrana právě tehdy, když se jejich intervaly překrývají. V této reprezentaci je problém s intervalovým plánováním ekvivalentní nalezení maxima nezávislá sada v tomto průsečíkovém grafu. V obecných grafech je nalezení maximální nezávislé množiny NP-těžké. Proto je zajímavé, že v intervalových křižovatkových grafech to lze provést přesně v polynomiálním čase.^{[Citace je zapotřebí ]}

Problém plánování skupinových intervalů, tj. GISMPk, lze popsat podobným grafem intervalového průniku s dalšími hranami mezi každým dvěma intervaly stejné skupiny, tj. Jedná se o okrajové spojení intervalového grafu a grafu sestávajícího disjunktní kliky velikosti k.

Variace

Důležitou třídou plánovacích algoritmů je třída algoritmů s dynamickou prioritou. Když se žádný z intervalů nepřekrývá, je optimální řešení triviální. Optimum pro neváženou verzi najdete u nejbližší termín první plánování. Vážené intervalové plánování je zobecnění, kdy je každému provedenému úkolu přiřazena hodnota a cílem je maximalizovat celkovou hodnotu. Řešení nemusí být jedinečné.

Problém s intervalovým plánováním je jednorozměrný - relevantní je pouze časová dimenze. The Maximální disjunktní sada problém je zobecnění na 2 nebo více dimenzí. I tato generalizace je NP-úplná.

Další variantou je alokace prostředků, ve které je pomocí prostředků naplánována sada intervalů k takhle k je minimalizován. To znamená, že všechny intervaly musí být naplánovány, ale cílem je co nejvíce snížit počet zdrojů.

Další variace je, když existují m procesory místo jednoho procesoru. Tj., m různé úkoly mohou běžet paralelně.^[2]

Viz také

• Plánování (výpočet)
• Nejčasnější termín prvního plánování

Zdroje