Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel18}} ==!! Ütemezési feladatok típusai. Az 1|prec||C_max és az 1||||∑C_j feladat. 2-közelítő algoritm…”

2012-10-22T09:43:48Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel18}} ==!! Ütemezési feladatok típusai. Az 1|prec||Cmax és az 1||||∑Cj feladat. 2-közelítő algoritm…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel18}}

==!! Ütemezési feladatok típusai. Az 1|prec||Cmax és az 1||||∑Cj feladat. 2-közelítő algoritmus a P||Cmax feladatra.==

__TOC__

===Ütemezési feladatok osztályozása===

Az ütemezési feladatok egy α|βγ hármassal írhatók le, ahol
* α a gépek száma
** 1: 1 gép
** Pm: m párhuzamosan futó gép
** P: nem rögzített számú párhuzomosan futó gép. P|β||γ az {1||β||γ, P2||β||γ, P3||βγ, ...} feladatokat tartalmazó osztály neve.
* β az infók halmaza az ütemezésről. Pl.:
** prec: adott egy irányított gráf, ami megkötéseket tartalmaz arra nézve, hogy egy adott munka elkezdéséhez mely munkákat kell előbb befejezni
** rj: adottak a release time-ok, azaz hogy melyik job mikortól áll rendelkezésre
** pj: adottak a megmunkálási idők, mennyit vesz igénybe az adott munka elvégzése
* γ a függvény, ami szerint optimalizálunk
** Cmax = max(Cj): az utolsó munka befejezési ideje
** ∑Cj ~ ∑Cj/n: a munkák átlagos befejezési ideje

===1|precCmax===

A feladatokat topologikus sorrendben adogatjuk a gépnek. Ez optimális, mert folyamatosan foglalt a gép.

===1|∑Cj===

Munkaigény szerint növekvő sorrendben adogatjuk a feladatokat a gépnek. p1≤p2≤...≤pn. Az algoritmust SPT-nek (Shortest Processing Time) hívjuk.

Az SPT ütemezés optimális, mert véges sok sorrend létezik és egy nem SPT ütemezés javítható. Ha az ütemezés J1, ..., Jn sorrendben veszi a feladatokat, ahol valamelyik i-re pi>pi+1, akkor a két feladatot megcserélve ∑Cj csökken.

<div id="P_Cmax"></div>
===P|Cmax===

A 2|||Cmax feladat NP nehéz, mert visszavezethető rá a partíciós probléma. P||||Cmax is NP nehéz, mert speciális esetként tartalmazza 2||Cmax-ot.

*Def.*: listás ütemezés (Graham):
A joboknak vesszük egy előre rögzített sorrendjét. Ha egy gép nem dolgozik, a listában következő munkát azonnal odaadjuk neki.

*Tétel*: a listás ütemezés (2-1/m)-approximálja a Pm|Cmax feladatot. 
*Biz.*:
* OPT ≥ max(pi)
* OPT ≥ ∑pi/m
* Az utolsóként befejeződő k munka t-kor kezdődött, és t-ig egy gép sem állhatott <big>⇒</big> ∑i≠kpi ≥ mt
* Cmax = t+pk ≤ ∑i≠kpi/m+pk = ∑pi/m+pk(1-1/m) ≤ OPT*(2-1/m)

*Tétel*: Az LPT (Longest Processing Time) szerinti listás ütemezés 4/3-approximációs minden m-re.

-- [[PallosPeter|Peti]] - 2007.01.03.

[[Category:Infoszak]]

Rendszeroptimalizálás, 18. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel18}} ==!! Ütemezési feladatok típusai. Az 1|prec||Cmax és az 1||||∑Cj feladat. 2-közelítő algoritm…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel18}} ==!! Ütemezési feladatok típusai. Az 1|prec||C_max és az 1||||∑C_j feladat. 2-közelítő algoritm…”