AKIŞ TİPİ ÇİZELGELEME PROBLEMLERİNİN GENETİK ALGORİTMA

ile

ÇÖZÜM PERFORMANSININ ARTIRILMASINDA DENEY TASARIMI UYGULAMASI

Alpaslan FIĞLALI1

Orhan ENGİN2

İ.T.Ü. İşletme Fakültesi Endüstri Mühendisliği Bölümü1

Selçuk Üniversitesi Müh. Mim. Fak. Endüstri Mühendisliği Bölümü2

 

 

 

ÖZET

Bu makalede, optimum çözümü zor olan (NP-zor), çok makinalı akış tipi çizelgeleme problemlerinin  genetik algoritma ile çözüm performansının artırılmasına yönelik bir çalışma yapılmıştır. Genetik algoritmanın optimum veya optimuma yakın çözüme ulaşma  performansını etkileyen; başlangıç popülasyonu; üreme, çaprazlama ve mutasyon operatörleri ile  çaprazlama ve mutasyon oranları gibi  parametrelerin uygun değerlerinin belirlenmesine çalışılmıştır. Parametrelerin ayrı ayrı değerlendirilmesi ile bulunan en iyi iki parametre değeri, ve yukarıdaki parametreler kullanılarak Taguchi yöntemi ile iki seviyeli, altı faktörlü  deney tasarımı yapılmıştır. Turbo paskal programlama dilinde hazırlanan genetik algoritma programı ile   akış tipi çizelgeleme problemleri için bilinen (Carlier,1978) beş ayrı problem üzerinde toplam 1000 adet deney yapılmıştır. Bu  deneyler sonucunda akış tipi çizelgeleme problemlerinin GA ile çözümünde etkili olan parametreler ile GA’nın çözüm performansını artıracak parametre setlerinin belirlenmesi amaçlanmıştır.

Anahtar Kelimeler: Akış tipi çizelgeleme, Genetik algoritma, Parametre optimizasyonu, Deney tasarımı

ABSTRACT

In this study, the solution performance of genetic algorithms in flowshop scheduling problem area which is known as NP-hard class is tried to be improved. Because that the performance of the algorithm depends on the control parameters, such as number of initial population, reproduction operators, crossover operators, mutation operators, rate of crossover and mutation rate, the optimal set of control parameters is tried to be optimized  to achieve the optimal or suboptimal solution.  Firstly, the best two parameter values found by evaluating the parameters individually and they are used in design of experiments as bi-level and six factors for multi-machine problems. Five benchmark flow-shop scheduling problems  from literature were solved with 1000 runs on the genetic algorithms program made by using Turbo Pascal programming language. As the result of experiments, the parameters affecting the solution performance of GA for flow-shop scheduling problems and optimal parameter sets of GA are determined.

Keywords: Flow-shop scheduling, Genetic algorithms, Parameters optimisation,  Experimental design

 

GİRİŞ

Bu çalışmada akış tipi  çizelgeleme problemlerinin Genetik Algoritma (GA) yardımı ile çözüm performansının artırılmasına çalışılmıştır. Akış tipi çizelgeleme problemlerinde, birbirinden farklı, m-makina ve n-iş mevcut olup her bir iş aynı sıra ile  m farklı  operasyondan  oluşur. Akış tipi çizelgeleme problemleri ile ilgili yapılan bu çalışmada amaç  toplam akış zamanını veya en son işin tamamlanma zamanını (makespan) minimize etmektir.

Akış tipi çizelgeleme problemleri ile ilgili ilk çalışmayı, Johnson [1954] yapmıştır. İki makina n-iş problemleri için optimum çözüm veren basit bir algoritma geliştirmiştir.

Daha sonra yapılan çalışmalarda m‑makina sayısı (m>2) için araştırmalar yapılmıştır. Makina sayısı (m>2)  problemleri, NP-zor (Optimum çözümleri olmayan) kapsamına girdiğinden bu problemler için çeşitli sezgisel yöntemler geliştirilmiştir [Chen ve diğerleri ,1995]. Bunlar; Palmer’in Eğim Dizisi Yöntemi [1965]; Compbell, Dudek ve Smith (CDS) Algoritması [1970]; Gupta Yöntemi [1971]; Dannenbring Yöntemi [1972]; Nawaz, Enscore ve Ham (NEH) Yöntemi [1983]; Hundal ve Rajgopal Yöntemi [1998]; Widmer ve Hertz Yöntemi [1989]; Ho ve Chang (HC) Yöntemi [1991].

Akış tipi çizelgeleme problemleri için, bilgisayarların hızlarının artması ile daha etkin çizelgeleme yöntemleri geliştirilmeye çalışılmıştır. Bu yöntemlerden biri de genetik algoritmalardır. Genetik algoritmaların çizelgeleme yöntemlerinde kullanımı iki farklı şekilde gerçekleştirilmiştir [Gen ve Cheng, 2000] bunlar,

1.  Genetik algoritma yardımı ile permütasyon tipi iş sırası bulma,

2.  GA ile bulunan permütasyon sırasının,  bilinen Klasik sezgisel yöntemler (Johnson, Palmer, CDS, Gupta v.d.)  ile karşılaştırılması.

Akış tipi çizelgeleme problemleri ile ilgili olarak son yıllarda yapılan GA çalışmaları aşağıda özetlenmiştir [Engin,2001].

Chen, Vempati ve Aljaber [1995] tamamlanma zamanı (makespan-Cmax) kriterli akış tipi çizelgeleme problemleri için sezgisel tabanlı GA kullanmıştır, bulunan sonuçlar mevcut sezgisel yöntemler (NEH, CDS) ile karşılaştırılarak GA’nın iyi performans verdiği belirlenmiştir.

Reeves [1995b]  Akış tipi çizelgeleme (n-iş;m-makina) problemlerini, GA (uygun parametreler kullanılarak) ile çözüp, elde edilen sonuçları, komşuluk arama (neighbourhood search) ve tavlama benzetimi ile karşılaştırmıştır. GA’nın daha iyi performans verdiği belirlenmiştir.

Murata, Ishıbuchı ve Tanaka [1996a], akış tipi çizelgeleme problemlerinin GA çözüm değerlerini, diğer arama yöntemlerinden olan, yerel arama, tabu araştırma ve tavlama benzetimi yöntemleri ile karşılaştırmışlardır, bulunan sonuçlara göre GA biraz daha iyi sonuç vermiştir. GA’nın performansının artırılması için  iki melez GA önerilmiştir. Bunlar, genetik lokal arama ve genetik tavlama benzetimidir.

Murata, Ishıbuchı ve Tanaka [1996b], Akış tipi çizelgeleme problemleri için, çok amaçlı bir genetik  algoritma kullanmıştır. Bu algoritmanın performansı iki amaca göre belirlenmiştir; bunlar, tamamlanma zamanı(Cmax) ve toplam gecikmenin minimize edilmesidir.

Chen,Neppallı ve Aljaber [1996], Akış tipi çizelgeleme problemlerinin çözümünde GA kullanarak toplam akış zamanını minimize etmeye çalışmışlardır. GA’nın akış tipi çizelgeleme problemlerinin çözümünde başarılı sonuçlar verdiğini belirlemişlerdir.

Jain ve Bagchi [2000], Akış tipi çizelgeleme  problemlerinin GA ile çözüm etkinliğinin  araştırılmasına yönelik olarak Darwin ve Lamark tabanlı Genetik algoritmaların karşılaştırılmasını yapmışlardır. GA’nın performansının artırılmasında, öğrenen temelli GA modellerini önermişler ve bu modeli klasik yöntemler (NEH, CDS) ile karşılaştırarak etkinliğini belirlemişlerdir.

NP-zor olarak bilinen Akış tipi çizelgeleme problemlerinin GA ile çözüm kalitesi, GA’da kullanılan parametrelere bağlıdır. Genetik Algoritmada, optimum veya optimuma yakın çözüm veren parametreler, problemlerin yapısına göre değişmektedir. Akış tipi çizelgeleme problemlerinde, optimum veya optimuma yakın çözüme ulaşılması için Gen ve Cheng [2000]  bu çalışmada uygun genetik operatörler, deney tasarımı yardımı ile, belirlenmiştir. Çalışmada, Carlier [1978] tarafından geliştirilen beş farklı akış tipi çizelgeleme problemi kullanılmıştır. Deneylerden elde edilen sonuçlara göre parametre setlerinin çözüm kalitesini etkilediği görülmüştür.

Genetik Algoritmalar (GA)

Genetik algoritma, rastsal arama tekniklerini kullanarak çözüm bulmaya çalışan, parametre kodlama esasına dayanan bir arama tekniğidir [Goldberg, 1989]. Akış tipi çizelgeleme probleminin GA ile çözümünde takip edilecek işlem adımları [Croce ve diğerleri,1995] şunlardır:

1. Çizelgelenecek bütün işler dizi olarak kodlanır. Bu diziyi (kromozomu) oluşturan her bir elemana gen denir. Her bir dizi, arama uzayında belirli bir çözüme  tekabül eder.

2. Rassal olarak iş sırası (kromozom)  seçilir ve başlangıç popülasyonu olarak kabul edilir.

3. Her bir dizi için bir uygunluk değeri, tüm işler için Cmax–tamamlanma zamanı, hesaplanır, bulunan uygunluk (fitness) değerleri, dizilerin çözüm kalitesini gösterir.

4. Bir grup dizi belirli bir olasılık değerine göre rassal olarak seçilip üreme işlemi gerçekleştirilir.

5. Üreme işleminde, çeşitli genetik operatörler kullanılabilir.

6. Yeni bireylerin uygunluk değerleri hesaplanarak, çaprazlama ve mutasyon işlemlerine tabi tutulur.

7. Önceden belirlenen nesil sayısı boyunca 4 ve 6 numaralı  işlemler devam ettirilir.

8. İterasyon  nesil sayısına ulaşınca işlem bitirilir. Uygunluk değeri en yüksek olan dizi (Cmax değeri en küçük olan)  en iyi çözüm olarak seçilir.

 

Genetik Algoritmada Kullanılan Operatörler

Uygulamada, iş çizelgeleme problemleri için temel kodlama (Her bir genin bir işi temsil ettiği) kullanılmıştır. Kromozom dizisi üzerinde herbir rakam bir işi temsil etmektedir [Cleveland ve Smith,1989].

Başlangıç popülasyonu literatürdeki  çalışmalara benzer  şekilde 10,20,30,40 ve 50 kromozom şeklinde ve rassal olarak  belirlenmiş [Ghedjati, 1999] ve bu değerler  ayrı ayrı  test edilerek en iyi başlangıç popülasyonu değeri 40 ve 50 kromozom olarak belirlenmiştir [Engin, 2001].

Üreme yöntemi olarak, Goldberg tarafından geliştirilen Rulet çemberi [Goldberg,1989]  yönteminin makina verimlerine göre düzenlenmiş Makina Verimli Rulet Çemberi [Engin, 2001]  ile Akış Zamanlı  Rulet Çemberi yöntemi kullanılmıştır  [Chen ve diğerleri, 1996]. Makina Verimli Rulet Çemberi yönteminde, Mevcut popülasyon içinde bulunan  her bir iş sırası için ortalama makina verimleri hesaplanır. Verimi en yüksek olan iş sırasının bir sonraki nesilde kullanılması sağlanacak şekilde Rulet Çemberi yöntemi ile üreme işlemi gerçekleştirilir. Akış Zamanlı Rulet Çemberi yönteminde, makina verimleri yerine akış zamanları (Cmax) kullanılır. Minimum akış zamanına sahip olan iş dizilerinin bir sonraki nesilde kullanılması için rulet çemberi yöntemi kullanılır.

Çaprazlama yöntemi olarak, Altı ayrı çaprazlama operatörü [Cheng ve diğerleri, 1999] üzerinde   daha önceden yapılan deneyler sonucundan [Engin, 2001]  en uygun bulunan Doğrusal Sıralı Çaprazlama (LOX)  ile  Sıra Tabanlı Çaprazlama (OBX) kullanılmıştır. Doğrusal Sıralı Çaprazlamada, rastsal olarak seçilen iki ebeveyn üzerinde rastsal iki alt dizi seçilerek sıralı olarak yer değiştirilir. Sıra Tabanlı çaprazlama yönteminde de kromozom üzerinde bir grup nokta rastsal olarak seçilir. Birinci kromozomun seçilen noktalara karşılık gelen karakterleri aynen yerlerini korur; ikinci kromozomun seçilen noktalara ait karakterleri birinci kromozomun aynı noktalardaki karakterlerinin önüne getirilir. Geride kalan boş pozisyonlara, ikinci kromozomdan aktarılan yeni karakterlerde göz önüne alınarak, ilk kromozomun kullanılmayan karakterleri tarafından sıra ile yerleştirilerek yeni kromozom elde edilir.

Çaprazlama oranı, %10-%100 aralığında %10’luk artışlarla incelenmiş ve en iyi sonuçları veren, %70 ve % 90 seçilmiştir [Engin, 2001].

Mutasyon operatörü olarak beş ayrı mutasyon operatörü [Murata ve diğerleri,1996a]  arasında yapılan deneyler sonucunda en uygun bulunan Ters Mutasyon  ile Keyfi üç iş değiştirme mutasyon yöntemi kullanılmıştır. Ters mutasyon yönteminde,  mutasyon için seçilen kromozomdan iki pozisyon rastsal olarak seçilir ve bu iki pozisyondaki alt diziler ters çevrilir. Keyfi üç iş değiştirme yönteminde ise, kromozom üzerinde rastsal olarak seçilen üç iş keyfi (rastsal) olarak  yer değiştirilir.

Mutasyon oranı  da literatüre uygun olarak  %1 ile % 5 seçilmiştir [Engin,2001].

Deney Tasarımı

Deney tasarımı için  GA’da kullanılan altı faktör yukarıda belirtilen seviyelerde kullanılmıştır.  Faktörlerin birbirinden bağımsız oldukları kabul edilerek, Taguchi-deney tasarımı, L8 ortogonal düzeni kullanılmıştır [Ross,1989].

L8 Ortogonal düzene göre 8 farklı deney noktasında  25 er yenileme  için Carlier [1978] tarafından akış tipi çizelgeleme için geliştirilen ve  işlem süreleri [1-1000] aralığında değişen   beş ayrı problem üzerinde  toplam 1000 adet deney, Turbo Paskal programlama dilinde hazırlanan  Genetik algoritma programı yardımı ile bilgisayarlarda  test edilmiştir.

DENEYLER

İki seviyeli  altı faktörlü L8 ortogonal düzene göre gerçekleştirilen deneylerde kullanılan parametre değerleri Tablo 1’de sunulmuştur.

 

Tablo 1.  L8 Ortogonal Düzen İçin Kullanılan  Faktörler ve Seviyeleri

Faktör No

Faktör

SEVİYE

 

 

1

2

A

Başlangıç popülasyonu

40

50

B

Üreme Yöntemi

Makina Verimli (1) R.Ç

Akış zamanlı  (2)

R.Ç.

C

Çaprazlama Yöntemi

Doğrusal Sıralı Çaprazlama

(LOX)

Sıra Tabanlı Çaprazlama

(OBX)

D

Mutasyon Yöntemi

Ters Mutasyon

(1)

Keyfi üç iş değiş.

(4)

E

Çaprazlama Oranı

% 70

% 90

F

Mutasyon Oranı

% 1

% 5

 

 

Bu düzene göre test edilen beş ayrı problem için sekiz ayrı deney sonucunda elde edilen tamamlanma zamanlarının (Cmax) aritmetik ortalama ve standart sapma değerleri  Tablo 2’de sunulmuştur.

Tablo 2’deki değerler incelendiğinde aritmetik ortalaması en küçük olan tamamlanma zamanı değeri, sekizinci deneyde bulunmuştur. Tablo 2’deki deneylerden 3,4,7 ve 8. deneylerde standart sapma değeri sıfır çıkmıştır. Bu deneylerdeki 25 denemenin tamamında aynı Cmax değerlerine ulaşılmıştır.

 

Tablo 2. Problemlerin Tamamlanma Zamanları Ortalama ve Sapma Değerleri

Deney No

 

Problem 1

5x10

Problem 2

4x13

Problem 3

4x14

Problem 4

5x12

Problem 5

6x10

1

`x

7075

7440

8196

7700

7795

s

66,13

115,02

72,95

65,04

31,07

2

`x

7048

7401

8151

7624

7784

s

29,31

102,05

71,89

70,97

25,30

3

`x

7038

7364

8099

7525

7750

s

0

44,30

56,20

54,44

17,10

4

`x

7038

7333

8110

7566

7743

s

0

77,11

52,23

53,50

17,10

5

`x

7047

7457

8293

7698

7764

s

27,18

87,17

91,13

75,37

26,57

6

`x

7038

7430

8179

7598

7770

s

1,95

77,85

77,30

70,21

25,87

7

`x

7038

7259

8059

7503

7782

s

0

91,81

52,62

46,03

38,21

8

`x

7038

7177

8026

7465

7748

s

0

38,96

35,33

48,16

24,07

 

Cmax değerleri bulunan beş ayrı problem  için ANOVA testi ile  hesaplanan hata kareleri toplamı [Ross, 1989] Tablo 3’de sunulmuştur.

Tablo 3’de hesaplanan kareler toplamı incelendiğinde, %10 anlamlılık düzeyi için bütün parametrelerin etkili olduğu söylenir. GA’da kullanılan en etkili parametrenin üreme yöntemi olduğu tablo da görülmektedir. GA parametrelerinin etkililik oranlarının belirlenmesi için Tablo 3’deki değerlerin toplam içerisindeki yüzde oranı Tablo 4’de sunulmuştur.

 

Tablo 3. Hata Kareleri Toplamı

Problem No

Başlangıç Popülasyonu

Üreme Yöntemi

Çaprazlama Yöntemi

Mutasyon Yöntemi

Çaprazlama Oranı

Mutasyon Oranı

Problem 1

5x10

599.841

657.001

599.841

595.686

545.490

595.686

Problem 2

              4x13

294.374

1.109.901

144.668

99.413

5.212

6.379

Problem 3

4x14

191.704

860.672

11

102.604

39.592

57.596

Problem 4

5x12

28.512

985.608

71.896

92.450

34.322

101.430

Problem 5

              6x10

21.074

25.787

178

6.373

340

4.186

 

Tablo 4. Parametre % Etkililik Oranları

Problem No

Başlangıç Popülasyonu

Üreme Yöntemi

Çaprazlama Yöntemi

Mutasyon Yöntemi

Çaprazlama Oranı

Mutasyon Oranı

Problem 1

5x10

16,69

18,28

16,69

16,57

15,17

16,57

Problem 2

4x13

17,73

66,84

8,71

5,98

0,31

0,40

Problem 3

4x14

15,30

68,73

0,00

8,19

3,16

4,49

Problem 4

5x12

2,16

74,99

5,47

7,03

2,61

7,71

Problem 5

6x10

36,37

44,50

0,30

10,99

0,58

7,22

Ortalama

17,65

54,67

6,23

9,75

4,37

7,30

 

SONUÇ

Optimum çözümleri bulunamayan, n-iş, m-makina (m>2) akış tipi çizelgeleme problemlerinin rastsal bir arama tekniği olan GA ile çözümünde etkin parametrelerin belirlenmesine ilişkin yapılan deneylerden elde edilen sonuçlara göre, GA’nın performansını etkileyen temel faktör üreme yöntemidir. Deneylerden elde edilen sonuçlar ve deney tasarımındaki parametrelerin etkilik oranları dikkate alındığında; Çok sayıda optimum veya optimuma yakın çözümü bulunan (aynı Cmax değerine sahip fakat iş sırası farklı olan küme) çizelgeleme problemlerinde üreme operatörünün etkisi, optimum veya optimuma yakın çözüm kümesi küçük olan problemlerden daha azdır. GA’nın performansını etkileyen ikinci faktörün başlangıç popülasyonu sayısı olduğu belirlenmiştir. Sonuç olarak İşlem sürelerinin yüksek seçildiği [1-1000] durumlarda akış tipi çizelgeleme problemlerinin GA ile çözümünde Tablo 5’deki parametrelerin kullanılmasının iyi sonuç vereceği belirlenmiştir.

 

 

Tablo 5. Uygun Parametre Seti

Parametreler

Başlangıç Popülasyonu

Üreme Yöntemi

Çaprazlama Yöntemi

Mutasyon Yöntemi

Çaprazlama Oranı

Mutasyon Oranı

Uygun olanlar

50

Akış Zamanlı R.Ç.

Doğrusal Sıralı Çaprazlama

(LOX)

Keyfi Üç iş değiştirme

%70

%1

 

KAYNAKÇA

1.     CAMPBELL H.G.,DUDEK,R.A., SMITH, B.L.,1970, A Heuristic Algorithm For The n-Job, m-Machine Sequencing Problem, Management Science,16, pp:16

2.     CARLIER,J.,1978, Akış Tipi Çizelgeleme Problemleri, ftp://mscmga.ms.ic.ac.uk / pub / flowshop 1.txt 

3.     CHEN,C.L.,VEMPATI,V.S.,ALJABER,N., 1995, An Application of Genetic Algorithms for flow shop problems, European  Journal of Operation Research, 80, 389-396

4.     CHEN,C.L.,NEPPALLI,R.V.,ALJABER,N.,1996, Genetic Algorithms Applied to the Continuous Flow Shop Problem, Computers and  Industrial Engineering, vol 30, no:4,919-929

5.     CHENG,R.,GEN.M.,TSUJIMURA,Y.,1999, A Tutorial Survey of Job Shop Scheduling Problems Using Genetic Algorithms: Part II. Hybrid Genetic Search Strategies, Computers and Industrial Engineering 37, 51-55

6.     CLEVELAND,G.A.,SMITH,F.S.,1989, Using Genetic Algorithm to  Schedule Flow Shop  Release, Proc. 3rd  Int. Conf. On  Genetic Algorithms Applications, 160-169

7.     CROCE,F.D.,TADEI,R.,VOLTA,G.,1995. A Genetic Algorithm for the Job Shop Problem, Computers and Operations.Research. Vol.22,No.1

8.     DANNENBRING,D.G.,1977, An Evaluation of Flow-Shop Sequencing Heuristic, Management Science,23, pp:11

9.     ENGİN.O.,2001,Akış Tipi Çizelgeleme Problemlerinin Genetik Algoritma ile Çözümün Performansının Artırılmasında Parametre Optimizasyonu, Doktora Tezi, İ.T.Ü. Fen Bilimleri Enstitüsü, İstanbul

10.   GEN,M.,CHENG,R.,2000,Genetic Algorithms and Engineering Optimization , JOHN WILEY SONS, INC,USA

11.   GHEDJATI,F.,1999,Genetic Algorithms for the Job-Shop Scheduling Problem with Unrelated Parallel Constraints: Heuristic Mixing Method Machines and Precedence, Computers and Industrial Engineering 37, 39-42

12.   GOLDBERG,D.E.,1989.Genetic Algorithms in Search Optimization and Machine Learning, Addion Wesley Publishing Company,USA

13.   GUPTA,J.N.D.,1971,  A Functional Heuristic Algorithm For Flow-Shop Scheduling  Problem, Operations Research,22, pp:39-47

14.   HO,J.,C.,CHANG,Y.,1991, A New Heuristic For  The n-Job, m-Machine Flow-Shop Problem, European J.of  Operations  Research,52, PP:194-202

15.   JAIN,N.,BAGCHI,T.P.,2000,Hybridized Gas: Some New Results  in Flowshop Scheduling , Modelling and Simulation (MS2000) International Conferance at Pittsburg  in May 2000, http:// citeseer.nj.nec.com

16.   JOHNSON,S.M.,1954, Optimal two three-stage production schedule with setup times included,Nav. Research Logistics Quarterly, No:1, p:61-68

17.   MURATA,T.,ISHIBUCHI,H., TANAKA, H.,1996b, Multi-Objective Genetic Algorithms and Its Applications to Flow shop Scheduling Computers and Industrial Engineering, vol 30, No 4, pp 957-968

18.   MURATA,T.,ISHIBUCHI,H., TANAKA, H.,1996a, Genetic Algorithms for Flow Shop Scheduling Problems,Computers and Industrial Enginering vol.30, No.4, pp 1061-1071

19.   NAWAZ,M.,ENSCORE,J.E.,HAM,I.,1983, A Heuristic Algorithm For The m-Machine, n-Job Flow-Shop Sequencing Problem, OMEGA, The International Journal of Management Science, 11/1, pp:91-95

20.   PALMER,D.S,1965, Sequencing Jobs Through a Multi-stage Process in Minimum Total Time a Quick Method  of  Obtaining a Near Optimum, Operations Research 16, pp:10