PARALEL

PARALEL MAKİNELER İLE BEKLEMESİZ AKIŞ İSTASYONLARI İÇİN ÇİZELGELEME ALGORİTMALARININ PERFORMANSI Leave a comment

PARALEL MAKİNELER İLE BEKLEMESİZ AKIŞ İSTASYONLARI İÇİN ÇİZELGELEME ALGORİTMALARININ PERFORMANSI

 

  1. GİRİŞ

 Paralel makineli beklemesiz akış istasyonu olarak bilinen bir üretim sisteminde işleri çizelgeleyen algoritmaların performansı üzerine çalışılmıştır. Beklemesiz akış istasyonu k³2 makine merkezi [Z1, Z2,…, Zk] kümesinden oluşur, Zj merkezi m³1 paralel makineye sahiptir. Çizelgelenen n adet iş vardır {Ji ½1 £ i £ n}. p(Ji)=[pi1,pi2,…,pik] fonksiyonu çeşitli görevleri veya Ji işi için sırasıyla [Z1,Z2,…,Zk] merkezlerindeki ihtiyaç duyulan işlem zamanlarını gösterir. Bunun anlamı Ji işi ilk Z1‘de pi1  birim zamanda işlenecektir ve sonra Z2‘de pi2  birim zamanda işlenecektir ve böylece sonunda Zk‘da pik  birim zamanda işlenerek işlemini tamamlar. pij görevi, Zj ‘deki özdeş paralel makinelerden {Mj1,Mj2,…, Mjmj} herhangi bir mj ‘de işlem görebilir. Beklemesiz akış istasyonundaki her bir iş, ilk makine merkezinde başlanmasından son makine merkezinde tamamlanmasına kadar makinelerde herhangi bir kesinti ve makine merkezleri arasında herhangi bir bekleme olmaksızın sürekli olarak işlenir. Paralel makineli beklemesiz akış istasyonunda çizelgeleme problemi, birkaç basit akış hatları olan kimyasal işlemde ve petro-kimya üretim çevresinde çoğalmaktadır. Akış hatlarındaki her bir seviyede işlemcilerin doğası etkili bir şekilde özdeştir ve bundan dolayı karşılıklı değişebilirdir (Salvador,1973). Beklemesiz duruma bir diğer örnek, metallerin sürekli olarak yüksek derecede işlenmesi gereken sıcak metal haddeleme endüstrilerindedir. Son yıllarda, beklemesiz çizelgeleme problemlerinde ilgi dikkate değer miktarda artmaktadır.

 

Paralel makineli beklemesiz akış istasyonu, geleneksel beklemesiz akış istasyonunun ve özdeş paralel makine atölyesinin genellemesini gösterir. Eskisi k=1 ve m1³2 yani birden daha fazla paralel makineli bir makine merkezi örneğine uygunken, önceki mj =1, 2£j£k örneğine uygundur. Bu özel örnekler üzerine literatürde çok büyük miktarda çalışılmıştır (Lawler ve diğerlerinin araştırma yazısı 1982,1989 ve Lenstra ve Rinnooy Kan,1985).

 

Bir akış istasyonunda, toplam bitiş zamanını veya çizelgenin kriteri olarak bilinenin minimize etmek için n işi çizelgeleme problemini göz önünde tutarız. Beklemesiz akış istasyonunda kriteri minimize etmek için etkili algoritmaları, yukarıda bahsedilen NP- tamamlama problemlerine ait olan özel örnekler için (dikkate değer k=2, m1= m2=1’in ayrılığı; Gilmore ve Gomory,1964) benzerleri mevcut değildir (Garey ve Johnson,1979;Rock,1982;Sriskandarajah ve Ladet,1986). Salvador (1973)‘da olduğu gibi dal-sınır teknikleri kullanan bir algoritmanın dizaynı mümkünken bu algoritmalar hatta orta sayıda işler için zaman tüketir. Bu yüzden, kesin optimizasyon algritmalarını aramak yerine makul işlem zamanında iyi sonuç elde etmesi umulan heuristik algoritmalar araştırırız.

 

Bu yazıda, paralel makineler ile beklemesiz akış istasyonları için belirli heuristik algoritmaların performansını değerlendiririz. Bu noktada, özel bir algoritma ile elde edilen çözümün optimal çözüme ne kadar yakın olduğunu öğrenmekle ilgileniriz. Genelde, algoritmanın ortalama durum performansı değerlendirmesi deneysel çalışmalar ile ortaya çıkarılır.  Bu, bilinen veya tahmin edilen optimal çözümleri ile geniş problem kümelerinde heuristik çalıştırmakla ve elde edilen çözümleri heuristik olarak karşılaştırmakla ilgilidir. Bu gibi değerlendirme metotlarının kullanışlılığı problem örneklerinin ne kadar gerçekçi olduğuna bağlıdır. Bununla beraber algoritmanın daha zayıf olarak işlem gören örneği göz önünde bulundurmama riski her zaman olduğu için gerçekçi örnek problem kümesinin seçimi zordur.

 

Bu yazıda izlediğimiz yaklaşım “en kötü durum performans değerlendirmesi” olarak bilinir. Heuristik çözümün en kötü durumda optimal çözüme ne kadar yakın olduğunu belirleyen sert matematiksel analizden oluşur. Bu çizgi boyunca, akış istasyonunda yapılan işlerin bazıları ve paralel makineler çevresi Coffman ve diğerleri (1978), Friesen (1984), Friesen ve Langston (1986), Gonzalez ve Sahni (1978), Graham (1966,1969), Hochbaum ve Sahni (1978), Rock (1982), ve Rock ve Schmidt (1983)’de ortaya çıkar; ayrıca Lawler ve diğerlerinin (1982,1989) ve Lenstra ve Rinnooy Kan (1985)’in inceleme yazılarına bakın.

 

Paralel makineler ile beklemesiz akış istasyonları için çizelgeleme algoritmalarının geliştirilmesi üzerine az sayıda çalışma mevcuttur. Salvador (1973), sentetik fiber endüstrisinde fiili uygulamalarda doğan paralel makineli beklemesiz akış istasyonları için minimum bitiş zamanını bulmak için çizelgeleyen dal ve sınır algoritmasını geliştirmiştir. Paralel makineler ile beklemesiz akış istasyonlarının içeriğinde bazı heuristik algoritmaların en kötü durum analizi, Sriskandarajah (1986) ve Sriskandarajah ve Sethi (1989)’da ortaya çıkar. Bu yazı, beklemesiz akış istasyonu imalat çevresinde bazı heuristiklerin performansı analiz edilerek yazarın önceki çalışmasını genişletilir. Bir kaç çalışma beklemesiz kısıtı yerine makine merkezleri arasında bir tamponu göz önüne alır. Wittrock (1988), asıl olarak bitiş zamanını minimize etmek için ve ikinci olarak işlemdeki envanteri minimize etmek için bit heuristik algoritma önermiştir. En kötü durum performans içeriğinde paralel makineli iki makine merkezi akış istasyonu için bazı algoritmalar, Buten ve Shen (1973), Langston (1987) ve Sriskandarajah ve Sethi (1989)’da çalışılmıştır. Arthanari (1974), m1³2 ve m2=1 ile Zve Ziki makine merkezinden oluşan akış istasyonları üzerine çalışmıştır. Çıkışı minimize etmek için dal ve sınır algoritmasına dayanan heuristik prosedür geliştirmiştir.

 

Bundan sonraki bölümde problemin notasyonunu belirmekteyiz. Bölüm 3’te beklemesiz akış istasyonu için özellikle k=2 için bazı algoritmaların performansını analiz ederiz. Daha özel olarak Bölüm 3.2.’de m1=m³2,m2=1 ile k=2 durumunu göz önünde tutarken Bölüm 3.1. ‘de m1=1,m2= m³2 ile k=2’nin beklemesiz akış istasyonlarının durumunu göz önünde tutarız. Bu durumlar için önerilen algoritmalar, en kötü durum performans içeriğinde analiz edilir. Bölüm 3.3, m1=m2=m³2 ile k=2 durumunu göz önünde tutar. Bölüm 3.4 ‘de F2½beklemesiz, m1³ 2, m2³ 2½Cmax genel durumu için algoritma sağlanır ve daha üst sınır performansı türetilir. Bölüm 4 yazıyı sonuçlandırır.

 

  1. PROBLEMİN NOTASYONU

 

Çizelgeleme problemlerinin sınıflandırılması ve notasyonu için, Lawler ‘ı izleriz (1982). Problemi a ½b½g  formunda sunarız, bizim örneğimizde bu Fk½beklemesiz, m1, m 2, …., mk ½ C max  şeklindedir ve a = Fk k makina merkezi ile akış istasyonu çevresini gösterir, b = {beklemesiz,m1,m 2, …., mk } beklemesizlik kısıtını ve herbir merkezdeki makinaların sayısını gösterir. Eğer mi belirtilmemişse 1 olarak tayin edilir. Benzer şekilde, eğer bekleme olamama kısıtı belirtilmemişse ara stokların sınırsızdır. g = C max   optimallik kriteridir, örneğin bitiş zamanının en küçüklenmesi (makespan). S çizelgesinin bitiş zamanı C max  aşağıdaki gibi tanımlanır. C i , S çizelgesinde Ji işinin bitiş zamanı ise, C max  = max i{Ci} olur. Özel durum F1½beklemesiz, m½Cmax, ayrıca Pm½½Cmax olarak gösterilebilir ve Pm m makina ile paralel makina çevresi ni gösterir.

 

 

  1. BEKLEMESİZ AKIŞ İSTASYONU İÇİN ÇİZELGELEME ALGORİTMALARININ PERFORMANSI

 

Bu bölümde, beklemesiz akış istasyonunun iki özel örneği için belirli heuristik algoritmalarının en kötü durum davranışını inceleriz. Bu bölümün birinci ve ikinci alt bölümler sırasıyla F2½beklemesiz, m1=1, m2=m ³ 2½Cmax ile F2½beklemesiz, m1= m ³ 2, m2= 1½Cmax ilgilenir. Son alt bölüm herbir merkezde her hangi bir sayıda makina ile akış istasyonlarını  değerlendirirken  (F2½beklemesiz, m1³2, m2³1½Cmax),  üçüncü alt alt bölüm ise F2½beklemesiz, m1 = m2=m³2½Cmax ile ilgilenir. Bu yazıda, sıfır işlem zamanlı görevlerinin makinalarada e miktar zaman harcadığını farz ederiz ve e pozitif küçük bir sayıdır (örneğin e=0).

 

3.1. F2½beklemesiz, m1=1, m2=m ³ 2½Cmax Örneği İçin Algoritmalar : En Kötü  

       Durum Performansı

 

İlk olarak liste çizelgeleme algoritmasının en kötü durum performansını açıklarsak, liste çizelgeleme algoritması ilk uygun makineye listedeki bir sonraki işi atar.

 

3.1.1. Liste Çizelgeleme Algoritması H1

 

Bu algoritmada, 1,2,…,n iş indekslerinin listesi (permütasyonu) gerçekleştirilir. İşler listede göründükleri sırayla çizelgelenirler.

 

Bu heuristik Graham tarafından, m ³ 2 makinalı paralel makina istasyonları için 1966 yılında çalışılmıştır örneğin Pm½½Cmax . Eğer sırasıyla f ve f*, verilen herhangi bir iş seti için  liste çizelgelemenin ve optimal çizelgelemenin tamamlanma zamanını gösterir ve r = 2-(1/m) ile f / f* £ r ‘dir. r değerine liste çizelgeleme algoritması için en kötü durum performans sınırı denir. F2½beklemesiz, m1=1, m2=m ³ 2½Cmax durumu için  liste çizelgeleme algoritmasının  en kötü –durum sınırını Teorem1’de kurarız.

 

Bu bölümde sonuçları sağlamak için, liste çizelgeleme algoritması ile elde edilen iş indeksleri sırasında  olan Sj çizelgesi tanımlanır. Sj = [1,2,…,n] indekslerinin sırasıyla tayini ile genellik kaybı olmaz . Sj için Şekil 1 ‘de görüldüğü gibi …………………………

 

 

Teorem 1 : F2½beklemesiz, m1=1, m2=m ³ 2½Cmax  örneği için liste çizelgeleme algoritması için en kötü durum sınırını saptarız. Bu bölümde sonuç sağlamak için işlerin sırasını gösteren  ve liste çizelgeleme algoritması ile elde edilen Sj çizelgesini tanımlarız. . Sj = [1,2,…,n] iş sırası olsun.

 

Şekil 1’de . Sj , Sj olarak gösteriliyor ve x,y,w bölümlerine ayrılabilir.

 

Bölüm x  : Bu bölüm Sj  ‘nin, Z1 makine merkezindeki makina tamamıyla dolu olduğu zamanki bölümüdür. x bölümünün uzunluğu ile gösterilir. [ i=1,2,…,l(x)]. l(x) tane bölüm vardır.

 

l(x)

x = S xj

i=1

 

l(y)

y = S yj

i=1

f/f* £ x/f+ y/w +w/f*                                (10)

 

(10),(7),(8) ve (9) kullanılarak aşağıdakine sahip oluruz

f / f* £ (3-1/m)                                   (11)

 

Liste çizelgeleme algoritması için elde edilen F2½beklemesiz, m1=1, m2=m³2½Cmax benzer en kötü durum örneği kurulabilir. Bu ispatı tamamlar.

 

Liste çizelgeleme algoritmasının, daha geniş ilk görevli işler çizelgenin başına çizelgelendiği ve daha geniş ikinci görevli işler ise çizelgenin sonuna çizelgelendiğinden dolayı daha zayıf performansına en kötü örnekten fark edilebilir. Yukarıda sınırı geliştirmek için  pi2 ‘nin artan sırada olmayan işleri çizelgeleyen aşağıdaki algoritmayı öneririz.

 

 

 

 

3.1.2. H2 Algoritması

 

Bu algoritmada pi2 ‘nin artan sırada olmayan işler çizelgelenir.

 

Aşağıdaki teorem H2 için en kötü durum sınırını sağlar.

 

İspat : Şekil 1’de S, H‘nin çizelgesi

f = x+y+w                              (12)

 

Sj = [1,2,…,n] olduğu zaman aşağıdaki açıktır;

f³ y                             (13)

Şimdi şunu sağlarız

f³ x+w                                 (14)

Bölüm 3.11’de olduğu gibi Sj ; Sj1  , Sj2 , Sj3  isimli üç forma bölünebilir. Sj3 ‘de

w= 0                                       (15)

Bu yüzden (14) ilişkisi Sj3 için doğrudur. Sj3 ‘de m işlerinin f zamanında bittiğine dikkat edelim.

 

Sj1 (veya Sj2 )’de w>0 dan beri en fazla m-1 iş f zamanında bitebilir. f zamanında biten işlerin en küçük indeksi q olsun. Eğer w≤ min (pi2 ) ise (14) ilişkisi doğrudur. w>min (pi2 ) olsun; 1≤q≤n doğru olur. Şimdi Sj1 (veya Sj2 ) çizelgesinde Jq+1 , Jq+2 ,… ve Jn işleri çıkaralım. Kalan işler {J1 , J2 ,…., Jq } , bunlar Sj2  ‘nin çizelgesi formundadır, aynı bitiş zamanı f ‘e sahiptirler. Şimdi şu açıktır,

 

q

f*1 ≥ pq2 + S pj1               (16)

i=1

 

{J1 , J2 ,…., Jq }işlerinin optimal bitiş zamanı f*1 olduğu zaman.

 

Kolayca şu gözlenir

f* ≥ f*1                            (17) ve

 

q

pq2 ≥  S pj1 +w                (18)

i=1

Bu ispatı tamamlar.

 

F2½beklemesiz, m1 = m2=1½Cmax  problemi, Gilmore ve Gomary (1964) nedeniyle polinomial zaman algoritması ile çözülebileceği ile ilgilidir. Bu algoritması en kötü durum performansı, F2½beklemesiz, m1=1,m2=m=2½Cmax örneği için Teorem 3’de verilmiştir. Algoritmanın en kötü durum performansı Johnson (1954) nedeniyle F2½beklemesiz, m1=1,m2=m=2½Cmax örneği için Sriskandarajah ve Sethi (1989)’de bulunur ve analiz edilir.

Teorem 3 : F2½beklemesiz, m1=1,m2=m=2½Cmax örneği için, f Gilmore ve Gomory ile elde edilen J={Ji ½1 £ i £ n }iş setinin bitiş zamanı olsun ve f* iş setinin optimal çizelgesinin bitiş zamanı olsun. Sonra f/f*  ≤ 2, ve sınır mümkün olan en iyidir.

 

İspat : İspat, Sriskandarajah ve Sethi (1989) ‘da kullanılan teknikten çıkar.

 

 

 

3.2. F2½beklemesiz, m1= m ³ 2, m2=1½Cmax Örneğinin Algoritması : En Kötü  

       Durum Performansı

 

F2½beklemesiz, m1= 1, m2= m ³ 2½Cmax  için herhangi bir çizelge, Z1 ve Z2 makine merkezlerinin rolünü karşılıklı değiştirerek ve rezerve yönlerde çizelgeyi gözönüne alarak F2½beklemesiz, m1= m ³ 2, m2=1½Cmax  probleminin çizelgesi olarak düşünülebilir. Aşağıdaki liste çizelgeleme algoritması benzer en kötü durum sınırı {3-(1/m)}’e sahip olduğu kolayca görülür.

 

3.2.1. Liste Çizelgeleme Algoritması H1

 

Bu algoritmada her bir i=1,2,…,n için pi1 ve pi2 ‘nin değerlerini karşılıklı değiştiririz. Sonra işler listedeki sıraya göre F2½beklemesiz, m1= 1, m2= m ³ 2½Cmax  için çizelgelenirler. Eğer Z1 ve Z2 ‘nin yerini karşılıklı değiştirirsek ve reserve tarafta çizelgeyi gözönünde tutarsak, F2½beklemesiz, m1= m ³ 2,m2=1½Cmax için doğru bir çizelge şeklinde olacaktır.

 

Sonuç 4 : H1‘ algoritmasının en kötü durum sınırı 3-1/m ‘dir.

 

İspat : Teorem1’den sonra gelir.

3.2.2. H2Algoritması

 

Bu algoritmada her bir i=1,2,…,n için pi1 ve pi2 ‘nin değerlerini karşılıklı değiştiririz. Sonra pi2 ‘nin sırası artmayacak şekilde F2½beklemesiz, m1= 1, m2= m ³ 2½Cmax için işler çizelgelenir. Eğer Z1 ve Z2 ‘nin rolünü değiştirirsek, F2½beklemesiz, m1= m ³ 2,m2=1½Cmax için doğru bir çizelge şeklinde olacaktır.

 

Sonuç 5 : H2‘ algoritmasının en kötü durum sınırı 2 ‘dir.

 

İspat : Teorem 2’yi takip eder.

 

Benzer şekillerde, Gilmore ve Gomory’nin algoritması temelinde heuristik, F2½beklemesiz, m1= 2, m2=1½Cmax özel örneği için en kötü durum sınırı 2 ile kurulabilir. Algoritmanın detaylı tanımı aşağıdaki gibidir:

  • Her bir i=1,2,…,n için pi1 ve pi2 ‘nin değerleri değiştirilir.
  • Gilmore ve Gomory’nin algoritmasını kullanarak F2½beklemesiz,m1=2,m2=1½Cmax için iş sırası (çizelgesi) bulunur.
  • F2½beklemesiz, m1= 2, m2=1½Cmax için aynı sırada işler çizelgelenir.
  • Yukarıdaki çizelgede, Z1 ve Z2 ‘nin rlünü değiştirirsek ve reserve yönde çizelge gözönüne alınarak F2½beklemesiz, m1= 2, m2=1½Cmax için doğru bir çizelge elde edilir.

 

 

3.3. F2½beklemesiz, m1=m2 =m ³ 2½Cmax Örneği İçin Algoritmalar : En Kötü  

       Durum Performansı

 

Bu örnekte liste çizelgeleme algoritması ve F2½beklemesiz, m1=m2 =m ³ 2½Cmax örneği için (1964) ile alınan algoritması kombine edilerek algoritma elde edilir. Sonra en kötü durum performansı sınırı çıkarılır. Şimdi algoritmalarımızın taslağını yapalım: Ji ,1 £ i £ n, p(Ji)=[pi1,pi2 ] işlem zamanlarına gereksinim duyan n iş olsun ve Ti = pi1+pi2 , 1 £ i £ n, olsun. Bu alt bölümde analiz edilen heuristik algoritmaları Sriskandarajah ve Sethi (1989)’da ilk önerilmiştir.

 

 

3.3.1. Ha  Algoritması

 

Adım 1 : Problemi m akış istasyonu problemine böl. Her problem iki makine merkezine sahiptir ve her merkez bir makineye sahiptir: {M11,M21},{M12,M22},…,{M1m ,M2m }, Mij  j. Akış istasyonunda i. makine merkezidir. Bak Şekil 3.

 

Adım 2 : m makine ile fiili paralel makine istasyonu her bir akış istasyonu {M1j,M2j} göz önüne alınarak tek bir Mmakinesi olarak oluşturulur. Liste çizelgeleme algoritması kullanılarak paralel makine istasyonunda n iş (işlem zamanı ihtiyacı T1 , T2 ,…, Tn ) çizelgelenir. Bu yolla işler m akış istasyonuna tahsis edilir.

 

Adım 3 : Her bir akış istasyonu iki makineden oluştuğu için her bir m akış istasyonunu Gilmore ve Gomory (1964) tarafından önerilen algoritma kullanılarak optimal olarak çözebiliriz. (Bu adım liste çizelgeleme kuralı ile yeniden yerleştirilebilir.)

 

Adım 2’de,paralel makine istasyonunda (Pm ½½ Cmax ) minimizasyon problem kriterini çözmeye çalıştığımıza dikkat edin. Bu problem NP-tamamlama problemlerinin sınıfına ait olduğu için (Gorey ve Johson,1979), liste çizelgeleme heuristiği işleri çizelgeleme için seçilir.

 

Aşağıdaki sonuç Sriskandarajah ve Sethi (1989)’de elde edildi.

 

Teorem 6 : Ha  algoritması ile elde edilen iş seti {Ji ½1 £ i £ n} ‘nin bitiş zamanı f olsun ve f* iş setinin optimal çizelgesinin bitiş zamanı olsun. Sonra

f/ f* £ 3-1/m ,

ve sınır mümkün olan en iyidir.

 

Teorem 6’da elde edilen sınırın eğer Adım 3 liste çizelgeleme kuralı ile yerleştirilirse sağlam olacağına dikkat.

 

Sonuç : Fk½beklemesiz, m,m,…,m ³ 2½Cmax  örneği için Ha algoritması ile elde edilen J={Ji ½1 £ i £ n} iş setinin bitiş zamanı f olsun ve f* , J’nin optimal çizelgesinin bitiş zamanı olsun. Sonra,

f/ f* £ k+1-1/m ,

 

İspat : İspat kolaydır ve Teorem 6’ya benzerdir.

 

Ha algoritmasının Adım 3’te k>2 için liste çizelgesi kullandığına dikkat.

 

 

3.3.2. Algoritma Hb       

 

Adım 1 : Ha ‘nın aynıdır.

 

Adım 2 : Ha ‘daki gibi, fakat liste çizelgeleme algoritması yerine LPT ( en uzun işlem zamanı ilk) kuralı n işi m paralel istasyona tahsis etmek için kullanılır.

 

Adım 3 : Ha ‘nın aynıdır.

 

LPT, Pm ½½ Cmax (Graham 1966,1969) için liste çizelgeleme algoritmadan daha iyi olduğudan en kötü durum performans içeriğinde algoritma Hb ‘nin Ha ‘dan daha iyi performans göstermesini bekleriz. Hb için performans sınırı Teorem 9’da tahmin edilir. Teorem 9’u sağlamak için aşağıdaki Lemma’ya ihtiyaç duyarız.

 

Lemma 8 : f* , beklemesiz akış istasyonunda p[Ji ]=[ pi1,pi2 ] ile J= {Ji ½1 £ i £ n} iş setinin optimal bitiş zamanı olsun ve f o* , m paralel makine istasyonunda p[Ji]=[Ti] ile J’nin optimal bitiş zamanıdır, Ti = pi1+pi2 ‘dir. Sonra fo*£2f* .

 

İspat : Beklemesiz bir akış istasyonunda J için S çizelgesi (f bitiş zamanı) verilsin, aşağıdaki prosedürü kullanarak bir paralel makine istasyonunda J için So çizelgesi (fo bitiş zamanı) kurulabilir. Sonra 2f ile sınırlı bitiş zamanına,yani fo£2f , ihtiyaç duyan sonuçlanan çizelge So gösterilecektir.

 

Prosedür ilk makine gruplarını şekillendirir. İki makineden oluşan her bir grup, her bir merkezden keyfi olarak bir makine olarak şekillendirilir. Sonra ne zaman farklı gruplardan makineler aynı işi işlerse çizelge aynı grupta işlerin hepsini çizelgelemek için yeniden düzenlemesine (belki önceden ayırmalar ile) dikkat ederek çizelge kurulur. Bu yeniden düzenlenen çizelge verilir, 2f uzunluğu ile paralel makine çizelgesini kolayca kurabiliriz. Daha fazla detay için okuyucu aşağıdaki prosedüre ve örnek problem üzerinde prosedürün gösterimine başvurabilir.

 

Prosedür :

 

Adım 1 : Her bir grup iki makineden oluşacak şekilde makineleri grupla. Her bir grubun, her bir makine merkezinden bir makine alarak oluşturulmasına dikkat. Grup Gi ={M1i,M2i}, 1£ i £ m. (Bak Şekil 4a’da m=3 için verilen örneğe.)

 

Adım 2 : İşlerin tiplerini tanımla: üç tip iş vardır.

 

Tip-1 iş : Eğer Ji işini işleyen makineler aynı gruba dahil ise Ji işine tip-1 iş denir. (Şekil 4a’da verilen örnekte, J1 , J3 , J5 , J6 , J8 , J11 , J12 , J13 , J14 ve J15  işleri tip-1 işlerdir. Ji işinin birinci ve ikinci görevleri sırasıyla Ji (1), Ji (2) olarak ifade edilir.)

Tip-2 iş : Ji işini işleyen makineler eğer farklı gruplara dahil ise Ji işi tip-2 iş olarak adlandırılır. (Şekil 4a’da verilen örnekte J2 , J4 , J7  ve J10 işleri tip-2 işleridir.)

Tip-3 iş : S çizelgesinde sol dışarıda yerleşen aylak zaman, tip-3 işleri olarak tanımlanan kukla işler ile yeniden sunulur. (Şekil 4a’da verilen örnekte Jdve Jd2 işleri tip-3 işleridir.)

 

Adım 3 : Tip-2 işleri tip-1 işlere değiştirerek belirli bir yolla görevleri oynat. Hareket prosedürü aşağıda olduğu gibidir:

Adım 3.1 : Tip-2 iş Ji ‘yi bul. Ji (1) ilk görevinin işlendiği (veya çizelgelendiği) grubu (Gj olsun) bul. İkinci görev Ji (2)’nin işlendiği (veya çizelgelendiği) grubu (Gk olsun) bul.f(Ji (1)), Gj ‘de Ji (1) bitiş zamanı olsun.

 

Adım 3.2 : Gj ‘de Gk ‘ya hareket ettirilen görevler setini (tGj ) oluştur.

Adım 3.2(a) : Küme G= Gj , L= f(Ji (1)) ve tG =0.

Adım 3.2(b) : Eğer G’de L’de ilk görevi başlayan tip-1 iş Ju varsa, sonra

L¬L+p[Ju (1)]+p[Ju (2)] ,

tG¬ tG È [Ju (1)],[Ju (2)]  ,

p[Ju (q)], Ju işinin q.görevinin işlem zamanıdır (q=1 veya 2). Yoksa G’de L’de başlayan tip-2 veya tip-3 iş (Ju) mevcuttur (q, 1 veya 2’ye eşit olabilir), sonra

L¬L+p[Jv (q)]   ,

tG¬ tG È [Jv(q)]  ,

Eğer Jv tip-3 ise (bu iş Jdw olarak ifade edilir), sonra

L¬L+p[Jdw ]          ,

tG¬ tG È [Jdw]        ,

Adım 3.2(c) : Adım 3.2(b)’yi L=f oluncaya kadar tekrar et.

Adım 3.2(d) : L=f olduğu zaman, tGj = tG ‘yi kur.

 

Adım 3.3 : Gk ‘da Gj ‘ye hareket ettirilecek görev kümesi (tGk) oluştur.

Adım 3.3(a) : G= Gk ‘yı kur, L=f(Ji(1))+p[Ji(2)] ve tG ={ Ji(2)}.

Adım 3.3(b) :Yukarıdaki Adım 3.2(b)’nin aynısı.

Adım 3.3(c) : L=f ‘e kadar Adım 3.3(b) ‘yi tekrarla.

Adım 3.3(d) : L=f olduğu zaman tGk = tG ‘yi kur.

 

Adım 3.4 : Gj ‘den (tGj ) görevlerini yeniden çıkar. Bu Gj ‘de bir seri boş yer bırakır. Gj ‘deki çizelgelenen sıranın aynı sırasında tGj  görevleri ile bu yerleri çizelgele.

 

Adım 3.5 : Gj ‘den (tGj ) görevlerini yeniden çıkar. Bu Gj ‘de bir seri boş yer bırakır. Gj ‘deki çizelgelenen sıranın aynı sırasında tGj  görevleri ile bu yerleri çizelgele. Adım 3.4 ve 3.5’de yerler çizelgelendiği zaman aşağıdaki işlemlerine dikkat:

  • Eğer gerekli ise görevler önceden ayrılır
  • İşin ilk görevi ikinci makine merkezlerine çizelgelenebilir. İşin ikinci görevi ilk makine merkezlerine çizelgelenebilir.

 

Adım 3.6 : Adım 3.1–3.5’i bütün tip-2 işler tip-1 işlerle yer değiştirene kadar tekrarla.

 

Bu prosedür örnekte (Bak Şekil 4a-4f) gösterilmiştir. Adım 3.2(b) de (ayrıca Adım 3.3(b) ‘de ) dikkat, G grubunda olan ve ilk görevleri L’de başlayan tip-1 işi ararız. Eğer bunun gibi işler yoksa, G’de olup L’de başlayan tip-2 veya tip-3 işi her zaman vardır. Bu özelliğin beklemesiz kısıtı ile bir akış istasyonu için doğru olduğu kolayca görülebilir. Adım 3.4 ve 3.5’de iki görev setini iki grup arasında hareket ettiririz.

????

O yüzden, iki kümeyi iki grup arasında hareket ettirerek ne f bitiş zamanını ne de diğer işlerin çizelgesinin etkilerini değiştiririz. Bu tür her harekette en az bir tip-1 işi tip-2 işi ile değiştirilir ve şimdi yeni tip-2 işi yaratılır. O yüzden prosedür tip-2 işlerinin toplam sayısı ile sınırlı sonlu iterasyonda sona erer. Böylece bütün tip-2 işlerinin tip-1 işlerine değişimini garanti eder. Prosedürün sonunda işlerin gruplara  ki bu gruplarda bütün işler ya tip-1 ya da tip-3 işleridir, yeni tayine sahip oluruz. Her bir gruptaki işler (preemptively) f’den daha uzun olmayan çizelge uzunluğu ile iki makinede işlem görür. Paralel makine çizelgesi, paralel makine istasyonunda tek bir makine için her bir gruba işler transfer edilerek kurulur. Sonra her bir gruptaki işler çizelgelenir böylece her bir işin görevler 1 ve 2 aynı makinede (nonpreemptively) işlem görür. Oluşan paralel makine çizelgesi So , açıkça 2f’e eşit veya daha küçük olan fo tamamlanma zamanına sahiptir. Yukarıdaki prosedürü kullanarak tamamlanma zamanı f‘ın Sparalel makine çizelgesi f£2 file kurulabilir. Optimal bitiş zamanı fo*£ fo  olduğuna göre fo*£2f* ‘e sahip oluruz. Bu ispatı tamamlar.

 

Prosedürün gösterimi: J={Ji½1 £ i £ 15}iş seti, tip-2 işlerin tip-1 işlere değiştirildiği prosedürü göstermek için dikkate alınır. İşlerin işlem zamanı aşağıdaki gibi verilmiştir: p[J1]=[0,3], p[J2]=[2,3], p[J3]=[3,9], p[J4]=[4,1], p[J5]=[5,0], p[J6]=[0,2], p[J7]=[3,2], p[J8]=[2,7], p[J9]=[1,3], p[J10]=[4,3], p[J11]=[2,2], p[J12]=[1,0], p[J13]=[0,4], p[J14]=[4,2] ve p[J15]=[9,1].

 

Şekil 4a’da, m=3 ile beklemesiz akış istasyonunda J için S çizelgesi verilmiştir. S çizelgesinin tamamlanma zamanı f=14’dür. G1 ve G2 gruplarına ait olan Jişi tip-2 işidir. Jişini tip-1 işiyle değiştirelim. G2 ‘den G1 ‘e hareket ettirilmekte olan görev kümesi tG2 dir ve,

tG2 ={ J8 (1), J8 (2), Jd1 , J12(1), J12(2)} ,

Benzer şekilde G1 ‘den G2 ‘ye hareket ettirilen görevler kümesi tG1 dir ve,

tG1 ={ J7 (2), J4(1),J5(1),J5(2)} ,

Her bir kümedeki { tG1,tG2}görevlerin toplam işlem zamanı 11’e eşit olur. Gruplar arasında görev kümelerinin taşınmasından sonra Şekil 4b, S çizelgesinin Gantt şeması gösterimini sağlar. J5(1) görevi herkesden önce ele geçirilir ve J5´(1), J5“(1) olarak isimlendirilen iki yeni görev ile yeniden gösterilir.

 

 

“Şekil 4a. m=3 ile beklemesiz akış istasyonunda J için S çizelgesi, J={ Ji |1£i£15}, tG1 ={ J7(2), J4(1),J5(1),J5(2)}, tG2 ={ J8(1), J8 (2), Jd1 , J12(1), J12(2)}.

 

Ayrıca, ilk görev J8(1) ‘in ikinci merkez makine M21 ‘de çizelgelendiğine ve ikinci görev J8(2)’nin ilk merkez makine M11 ‘de çizelgelendiğine dikkat (Bak Şekil 4b). Fakat tG1 görevleri, G1 ‘de çizelgelenir. Şimdi J2 işini tip-1 işe değiştiririz. J2 işi, Gve G2 gruplarına aittir. G2 ‘den G1 ‘e taşınmakta olan görevler kümesi tG2 dir.

tG2 ={ J2(2), J9(1),J10(1),J11(1), J11(2)}

Benzer şekilde, G1 ‘den G2 ‘ye taşınmakta olan görevler kümesi tG1 dir.

tG1 ={ J3(1), J3(2)}

Her bir kümedeki { tG1,tG2} görevlerin toplam işlem zamanı 12’ye eşittir. Görevler kümesini gruplar arasında taşınmasından sonra Şekil 4c S çizelgesinin Gantt Şeması gösterimini sağlar.

 

“Şekil 4b. J7 işi tip-1’e değiştirildikten sonra S çizelgesidir. tG1 ={ J3(1), J3(2)} , tG2={J2(2), J9(1),J10(1),J11(1), J11(2)}

 

“Şekil 4c. J2 işi tip-1’e değiştirildikten sonra S çizelgesidir.tG2={J5´(1), J5“(1),J5(2)},  tG3={J4(2),J10(2),Jd2}

 

J3(2) görevini J3´(2), J3“(2) isimli iki göreve (preempt) etmeye gerek duyarız. Aşağıdaki işleri değiştiririz (birinden sonra diğeri): J4, J9 ve J10 (Bak Şekil 4d-4f). Bütün tip-2 işlerini tip-1 işlerine değiştirdi. Son çizelge S için Şekil 4f’e bak. Teorem 9’u sağlamaya hazırız.

 

Teorem 9 : Hb algoritması ile elde edilen iş setinin J={Ji½1 £ i £ n} bitiş zamanı f olsun ve fiş setinin /optimal çizelgesinin bitiş zamanı olsun. Sonra

f/ f* £ 8/3-2/3m

İspat : Adım 2’de m paralel makineye işlerin tahsisini göz önüne al. fparalel makine istasyonunda işlerin bitiş zamanı olsun ve f* işlerin optimal bitiş zamanı olsun.

 

“Şekil 4d.J4 işi tip-1’e değiştirildikten sonra S çizelgesidir. tG2=={J10(1), J11(1), J11(2)}, tG2={ J9(2),J5*(1),J5**(1),J5(2)}

 

“Şekil 4e.J9 işi tip-1’e değiştirildikten sonra S çizelgesidir. tG2=={J10‘(2),J10“(2),Jd2}, tG3={ J11(1), J11‘(2),J11“(2)}

 

Adım 2, LPT kuralı kullandığında Graham (1969)’dan,

fo /fo*£ 4/3-1/3m                 (24)

Şu açıktır

f £ fo                                  (25)

Lemma 8’den,

fo*£ 2 f*                               (26)

(25) ve (26) sonuçlarını kullanarak şunu elde ederiz

f /f*£ 8/3-2/3m          (27)

Bu ispatı tamamlar.

 

Hb algoritmasının kesin en kötü durum sınırı rb bilinmez, hiçbir iş seti ile bulunmamış olduğu için,

f /f*=8/3-2/3m

 

 

 

“Şekil 4f.J10 işi tip-1’e değiştirildikten sonra S çizelgesidir.

 

Bununla birlikte iş seti örneği ile

f /f*=7/3-2/3m

Sriskandarajah ve Sethi (1989) bulunur. Böylece, rb aşağıdaki aralıkta olmalıdır:

7/3-2/3m£ rb £ 8/3-2/3m

Hb performans sınırı, Adım 2’de daha iyi algoritma ile LPT yerleştirerek geliştirilebilir (yeni algoritma Hc olarak adlandırılır). Bu yolla, Hc ‘nin en kötü durum sınırı rc ‘nin olması gerektiği aralığı belirleyeceğiz. Daha iyi algoritmalar olan sırasıyla Multifit (Friesen ve Langston,1984)’nin geliştirdiği Multifit (Coffman örneğin,1978;Friesen,1984) ve 6/5,72/61 ve (1+e)’nin performans garantisi (ro) ile Adım 2 için e-yaklaşım algoritması (Hachbaum ve Shmays,1987) uygundur. Hc ‘nin Adım 2’sinde optimal algoritma kullanılmış bile olsa Sriskandarajah ve Sethi (1989) rc ³2  gösterir.

 

Teorem 9’dan rc £2 ro sonucu çıkarılabilir. Böylece, rc aşağıdaki aralıkta olmalıdır:2£rc£2 ro , ro Adım 2’de kullanılan algritmanın performans garantisidir.

 

Adım 2 ve 3’de algoritmaların kullanımına aldırmyarak, Hc algoritmasının tümünün en kötü durum sınırı 2’ye eşit veya daha fazla olacağına dikkat. O yüzden eğer sınırı 2’den daha aza azaltmak istenirse sağlam olarak burada sunulandan farklı bir dizayna gerek duyulur.

 

 

 

 

 

3.4. F2½beklemesiz, m1 ³2,m2 ³ 2½Cmax Örneği İçin Algoritmalar : Daha Üst     Sınır Performansı

 

Bu bölümde, F2½beklemesiz, m1 ³2,m2 ³ 2½Cmax genel durumu için bir algoritma sağlanır. Sonra daha üst sınır performansı elde edilir. Genelliğinden hiçbir kayıp olmaksızın m1£m2 kabul ederiz, F2½beklemesiz, m1£m2½Cmax için herhangi bir çizelge eğer önceki problemde Z1 ve Z2 ‘nin rolünü karşılıklı değiştirirsek F2½beklemesiz, m1£m2½Cmax için doğru bir çizelge şeklini alabilir. Şimdi bizim algoritmamızın taslağını çizelim: Ji ,1£i£n, p[J1]=[ pi1,pi2 ], Ti = pi1+pi2  işlem zamanına ihtiyaç duyan n iştir ve k=[m2/m1], k m2/m1 ‘e eşit veya daha büyük olan en küçük tamsayıdır.

 

 

3.4.1. Hg Algoritması

 

Adım 1: Problemi, paralel makine problemleri ile m1 akış istasyonuna bölünür ve ilk merkezin tam olarak bir makineye sahip olduğu ve ikinci makinede en fazla k paralel makineye sahiptir:{ M1,j , M2,(j-1) k+2 ,…, M2,(j-1) k+k’ }; j=1,2,…, m1 ; M2,(j-1) k+r ,j. akış istasyonunda r. Paralel makinedir. Bak Şekil 5.

 

Adım 2 : m1 makine ile doğru bir paralel makine istasyonu, her bir akış istasyonu yukarıda tanımlanan tek bir Mj makinesi olarak değerlendirilerek şekillendirilir. Hochbaum ve Shymoys için (den dolayı) algoritmaları kullanılarak, paralel makine istasyonunda n iş (ihtiyaç duydukları işlem zamanı T1 , T2 ,…, Tn ) çizelgelenir.

 

Bu yolda işler m1 iş istasyonlarına tahsis edilir.

 

Adım 3 : Eğer akış istasyonu paralel makinelere sahipse bölüm 3.1.2’de sağlanan H2 algoritması kullanılarak m1 akış istasyonunun her biri çözülür; başka türlü çözüm Gilmore ve Gomary (1964) tarafından sağlanan algoritma kullanılarak akış istasyonu çözülür. (Bu adım liste çizelgeleme kuralı ile yeniden yerleştirilebilir).

Halgoritması için aşağıdaki sonuç elde edilebilir.

 

Teorem 10 : Halgoritması ile elde edilen iş setinin J={ Ji |1£i£n}bitiş zamanı f olsun ve f* ise iş setinin optimal çizelgesinin bitiş zamanı olsun.

f/ f* £ [1+( m2/m1)] (1+e)

 

İspat : Adım 2’de, işlerin m1 paralel makinelerine tayinini değerlendir. fo ,paralel makine istasyonunda işlerin tamamlanma zamanı olsun ve fo* işlerin optimal bitiş zamanı olsun. Hochbaum ve Shmoys (1987) algoritması kullanıldığı için şuna sahip oluruz,

fo/fo*£(1+e)                         (28)

Şu açık ki,

f£fo                                     (29)

 

“Şekil 5. m1 =3 ve m2 =5 olan paralel makineli m1 akış istasyonuna ayrışma.

 

Lemma 8’in tekniklerini ve prosedürünü kullanarak, aynı Lemma’dan elde edilene benzer olan aşağıdaki ilişkiyi elde edebiliriz:

fo*£[1+( m2/m1)] f   (30)

 

(29),(30) ve (28) ‘deki sonuçları kullanarak şunları elde ederiz

f/ f* £ [1+( m2/m1)] (1+e)             (31)

Bu ispatı tamamlar.

 

Halgoritmasının tam bir en kötü durum sınırı bilinmemektedir, hiçbir iş seti ile bulunamamıştır.

f/ f* = [1+( m2/m1)] (1+e)

Adım 3 liste çizelgeleme kuralı ile yerleştirilirmiş olsa bile Teorem 10’da elde edilen sınırın doğru olduğuna dikkat.

 

  1. Sözlerin Sonucu

 

Heuristik algoritmaları dizayn ettik ve iki makine merkezli beklemesiz akış istasyonunda minimum bitiş zamanlı çizelgelemenin bulunması problemi için performans sınırlarını tahmin ettik. Bu sınırlar son derece kullanışlı, çünkü kısmi olarak önerilen algoritmanın hiçbir zaman bilinen yüzdeden daha fazla optimal çözümü geçmeyeceğini bize garanti etmeyi mümkün kılar. En kötü durum performans konteksinde , H2 algoritması, F2½beklemesiz, m1=1,m2 =m ³ 2½Cmax için H1 liste çizelgeleme algoritmasından daha iyi performans gösterir ki bu sırada Hb algoritmasından daha iyi performans gösterir. Bu yazının mümkün ilavesi; Hb , Hc ve Hg algoritmaları için yakın sınırlar kadar iyi olan ve her bir merkezde herhangi bir sayıda makine ile akış istasyonu için H1 , Halgoritmalarının en kötü durum performansı çalışılabilir. Heuristik algoritmalar genelde uygulamada kendi en kötü durum garantilerinden daha iyi davranırlar. O yüzden sistemde işlenmesi gereken tipte işler üzerine yaklaşık varsayımlar altında ortalama durum performansı üzerine çalışmak bakımından ilginçtir.

 

 

Bir cevap yazın

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Translate »