Paralel görev zamanlama problemi - Parallel task scheduling problem

Teorik bilgisayar biliminde, paralel görev zamanlama problemi bir NP-zor optimizasyon problemi. Belirli bir dizi ${ displaystyle n}$ İşler olarak da adlandırılan paralel görevlerin planlanması gerekir ${ displaystyle m}$ bazen işlemci olarak adlandırılan aynı makineler, en son tamamlanma süresini en aza indirir. Veltman ve ark.^[1] ve Drozdowski^[2], bu problem şu şekilde gösterilir: ${ displaystyle P | size_ {j} | C _ { max}}$ içinde üç alanlı gösterim Graham ve diğerleri tarafından tanıtıldı ^[3]. Bu problem formülasyonunun kökenleri 1960'lara kadar izlenebilir.^[4]. Bu problem için, oranı şundan daha küçük olan polinom zaman yaklaştırma algoritması yoktur. ${ displaystyle 3/2}$ sürece ${ displaystyle P = NP}$.

Tanım

Bu problemde bize bir set veriliyor ${ displaystyle { mathcal {J}}}$ nın-nin ${ displaystyle n}$ işler yanı sıra ${ displaystyle m}$ özdeş makineler. her iş ${ mathcal {J}}} içinde { displaystyle j$ işlem süresi var ${ displaystyle p_ {j} in mathbb {N}}$ ve eşzamanlı kullanımını gerektirir ${ displaystyle q_ {j} in mathbb {N}}$ Bir program, her bir işi atar. ${ mathcal {J}}} içinde { displaystyle j$ başlangıç ​​zamanına ${ displaystyle s_ {j} in mathbb {N} _ {0}}$ ve bir set ${ displaystyle m_ {j} subseteq {1, dots, m }}$ nın-nin ${ displaystyle | m_ {j} | = q_ {j}}$ Her işlemci herhangi bir zamanda en fazla bir iş yürütürse, bir program uygulanabilir. Sorunun amacı ${ displaystyle P | size_ {j} | C _ { max}}$ minimum uzunlukta bir program bulmaktır ${ displaystyle C _ { max} = max _ {j in { mathcal {J}}} (s_ {j} + p_ {j})}$, aynı zamanda programın yapım süresi olarak da adlandırılır. Bir programın fizibilitesi için yeterli bir koşul aşağıdaki gibidir

${ displaystyle sum _ {j in { mathcal {J}}, s_ {j} leq t$.

Bu özellik tüm başlangıç ​​zamanları için karşılanırsa, zamandan başlayarak her dizi zamanında işlere ücretsiz makineler atanarak uygulanabilir bir program oluşturulabilir. ${ displaystyle t = 0}$.^[5][6]. Ayrıca, işler tarafından kullanılan makine aralıklarının sayısı ve her bir adımdaki boşta kalma aralıkları, aşağıdakilerle sınırlandırılabilir: ${ displaystyle | { mathcal {J}} | +1}$^[5]. Burada bir makine aralığı, bu setteki tüm makinelerin aynı işi işlediği şekilde maksimum kardinaliteye sahip bir dizi ardışık makinedir. Bir makine aralığı, ilk ve son makinesinin indeksi tarafından tamamen belirlenir. Bu nedenle, çıktıyı polinom boyutuyla kodlamanın kompakt bir yolunu elde etmek mümkündür.

Sertlik

Bu problem, sabit sayıda makine için bile NP-zordur çünkü ${ displaystyle P2 || C _ { max}}$ karşılık gelir bölüm sorunu. Dahası, Du ve Leung^[7] bu sorunun olduğunu gösterdi kesinlikle NP-zor makine sayısı en az olduğunda ${ displaystyle m = 5}$ve bir sözde polinom zaman Algoritma, makine sayısı en fazla ise sorunu tam olarak çözer ${ displaystyle m = 3}$. Daha sonra Henning ve ark.^[8] makinelerin sayısı arttığında sorunun da NP-zor olduğunu gösterdi ${ displaystyle m = 4}$. Makinelerin sayısı bir sabit ile sınırlandırılmamışsa, yaklaşık oranı şundan daha küçük olan bir yaklaşım algoritması olamaz. ${ displaystyle 3/2}$ sürece ${ displaystyle P = NP}$ çünkü bu sorun, çöp kutusu paketleme sorunu alt harf olarak, yani tüm işlerin işlem süresi olduğunda ${ displaystyle p_ {j} = 1}$.

Varyantlar

Bu problemin üzerinde çalışılan birkaç çeşidi vardır^[2]. Aşağıdaki varyantlar da birbirleriyle kombinasyon halinde düşünülmüştür.

Bitişik işler: Bu varyantta, makinelerin sabit bir düzeni vardır ${ displaystyle (M_ {1}, noktalar, M_ {m})}$. İşleri herhangi bir alt kümeye atamak yerine ${ displaystyle m_ {j} subseteq {M_ {1}, dots, M_ {m} }}$, işler bir makine aralığına atanmalıdır. Bu sorun, sorunun formülasyonuna karşılık gelir. şerit paketleme sorunu.

Kalıplanabilir işler: Bu varyantta her iş ${ mathcal {J}}} içinde { displaystyle j$ bir dizi uygun makine numarasına sahiptir ${ displaystyle D subseteq {1, dots m }}$ ve bu numaraların her biri için $D'de { displaystyle d }$ işlem süresi var ${ displaystyle p_ {j, d}}$. Bir iş planlamak için ${ mathcal {J}}} içinde { displaystyle j$, bir algoritma bir makine numarası seçmelidir $D'de { displaystyle d }$ ve bunu bir başlangıç ​​zamanına atayın ${ displaystyle s_ {j}}$ ve ${ displaystyle d}$ zaman aralığı boyunca makineler ${ displaystyle [s_ {j}, s_ {j} + p_ {j, d}).}$ Bu tür bir problem için olağan bir varsayım, bir işin çalışmasının, ${ displaystyle d cdot p_ {j, d}}$ artan sayıda makine için artmıyor.

Birden çok platform: Bu varyantta, makine seti bağımsız platformlara bölünmüştür. Planlanmış bir iş yalnızca bir platformun makinelerini kullanabilir ve işlendiğinde birden fazla platforma yayılmasına izin verilmez.

Algoritmalar

Garey ve Graham'ın hazırladığı liste çizelgeleme algoritması^[9] mutlak bir orana sahiptir ${ displaystyle 2}$, Turek ve ark.^[10] ve Ludwig ve Tiwari^[11]. Feldmann, Sgall ve Teng^[12] Liste çizelgeleme algoritması tarafından üretilen, öncelikli olmayan bir çizelgenin uzunluğunun aslında en fazla ${ displaystyle (2-1 / m)}$ Optimum önleyici yapım süresinin katı. sayı olduğunda durum için bir polinom-zaman yaklaşım şeması (PTAS) ${ displaystyle m}$ işlemci sayısı sabittir ${ displaystyle Pm | size_ {j} | C _ { max}}$, Amoura ve ark.^[13] ve Jansen vd.^[14]Daha sonra Jansen ve Thöle ^[6] İşlemci sayısının iş sayısı ile polinomik olarak sınırlandırıldığı durum için bir PTAS buldu. Bu algoritmada, makinelerin sayısı, algoritmanın zaman karmaşıklığı içinde polinomik olarak görünür. Genel olarak, makinelerin sayısı yalnızca örneğin boyutunda logaritmik olarak göründüğünden, bu algoritma aynı zamanda bir sözde polinom zaman yaklaşımı şemasıdır. Bir ${ displaystyle (3/2 + varepsilon)}$-yaklaşıklık Jansen tarafından verildi^[15]alt sınırına olan boşluğu kapatan ${ displaystyle 3/2}$ keyfi olarak küçük haricinde ${ displaystyle varepsilon}$.

Bitişik ve bitişik olmayan işler arasındaki farklar

Paralel görev zamanlama probleminin bir örneği verildiğinde, optimum üretim süresi, makinelerin bitişiğindeki kısıtlamaya bağlı olarak değişebilir. İşler bitişik olmayan makinelerde planlanabiliyorsa, en uygun üretim süresi bitişik olanlara programlanmaları gerektiği durumdan daha küçük olabilir. Bitişik ve bitişik olmayan çizelgeler arasındaki fark ilk olarak 1992'de gösterilmiştir.^[16] bir örnekte ${ displaystyle n = 8}$ görevler, ${ displaystyle m = 23}$ işlemciler, ${ displaystyle C _ { max} ^ {nc} = 17}$, ve ${ displaystyle C _ { max} ^ {c} = 18}$.Błądek vd. ^[17] bu sözde c / nc farklarını inceledi ve aşağıdaki noktaları kanıtladı:

• Bir c / nc-farkının ortaya çıkması için, en az üç görev olmalıdır. ${ displaystyle q_ {j}> 1.}$
• Bir c / nc-farkının ortaya çıkması için, en az üç görev olmalıdır. ${ displaystyle p_ {j}> 1.}$
• Bir c / nc farkının ortaya çıkması için, en azından ${ displaystyle m = 4}$ işlemciler gereklidir (ve bir c / nc farkı olan bir örnek vardır) ${ displaystyle m = 4}$).
• Bir c / nc farkının ortaya çıkması için bitişik olmayan program uzunluğu en az ${ displaystyle C _ { max} ^ {nc} = 4.}$
• Maksimum c / nc farkı ${ displaystyle sup _ {I} C _ { max} ^ {c} (I) / C _ { max} ^ {nc} (I)}$ en azından ${ displaystyle 5/4}$ ve en fazla ${ displaystyle 2.}$
• Belirli bir örnekte bir c / nc farkı olup olmadığına karar vermek NP-tamamlanmıştır.

Ayrıca, kanıtlanmamış olan aşağıdaki iki varsayımı da önerdiler:

• Bir c / nc farkının ortaya çıkması için, en azından ${ displaystyle n = 7}$ görevler gereklidir.
• ${ displaystyle sup _ {I} C _ { max} ^ {c} (I) / C _ { max} ^ {nc} (I) = 5/4}$

Ayrıca bakınız

• İş atölyesi planlaması
• Açık mağaza planlaması

Referanslar