Rendszeroptimalizálás, 18. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

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

Ü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
  • P_m: m párhuzamosan futó gép
  • P: nem rögzített számú párhuzomosan futó gép. P|β||γ az {1||β||γ, P₂||β||γ, P₃||βγ, ...} 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
  • r_j: adottak a release time-ok, azaz hogy melyik job mikortól áll rendelkezésre
  • p_j: 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
  • C_max = max(C_j): az utolsó munka befejezési ideje
  • ∑C_j ~ ∑C_j/n: a munkák átlagos befejezési ideje

1|precC_max

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

1|∑C_j

Munkaigény szerint növekvő sorrendben adogatjuk a feladatokat a gépnek. p₁≤p₂≤...≤p_n. 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 J₁, ..., J_n sorrendben veszi a feladatokat, ahol valamelyik i-re p_i>p_i+1, akkor a két feladatot megcserélve ∑C_j csökken.

P|C_max

A 2|||C_max feladat NP nehéz, mert visszavezethető rá a partíciós probléma. P||||C_max is NP nehéz, mert speciális esetként tartalmazza 2||C_max-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 P_m|C_max feladatot.
  
• Biz.*:
• OPT ≥ max(p_i)
• OPT ≥ ∑p_i/m
• Az utolsóként befejeződő k munka t-kor kezdődött, és t-ig egy gép sem állhatott ⇒ ∑_i≠kp_i ≥ mt
• C_max = t+p_k ≤ ∑_i≠kp_i/m+p_k = ∑p_i/m+p_k(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.

-- Peti - 2007.01.03.