Akış tipi iş çizelgeleme problemlerinin yapay bağışıklık sistemi ile çok amaçlı optimizasyonuna yönelik bir model önerisi
A multi-objective artificial immune algorithm for permutation flow shop scheduling problem to minimize makespan and total flow time: A proposal of model
Yazar: ERKAN AKÇAY
Danışman: PROF. DR. NİLGÜN FIĞLALI
Kocaeli Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2009
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Akış tipi üretim = Flow shop production ; Sezgisel algoritmalar = Heuristic algorithms ; Çok amaçlı karar verme = Multiobjective decision making

Özet:
Bu çalışmada, permütasyon akış tipi iş çizelgeleme problemlerinde en son işin tamamlanma süresi ve işlerin akış zamanlarının toplamının en küçüklenmesi amaçlanmış olup, bu amaç doğrultusunda Çok Amaçlı Yapay Bağışıklık Algoritması önerilmiştir. Söz konusu algoritma, yapay bağışıklık algoritmasının önemli adımlarından olan klonlama aşamasında çözüm uzayını açısal bölümlere ayırmış, çözümlerin ait oldukları açısal bölümlemedeki yoğunluğa göre klon sayısını belirleyerek çözümler arasındaki çeşitliliği sağlamaya çalışmıştır. Bir sonraki neslin seçim aşamasında ise Pareto baskınlık derecesini kullanması ile pareto tabanlı çok amaçlı algoritmalar arasında değerlendirilebilmektedir. Önerilen Yapay Bağışıklık Algoritmasında, klonlanan çözümlere rastsal iki işin yer değiştirmesi operatörü (swap) uygulanmış, bir sonraki nesil için seçilen çözümlere ise lokal arama uygulanmış, lokal arama operatörü olarak ise seçilen bir işin araya sokulması operatörü (insertion) kullanılmıştır. Önerilen algoritma ile elde edilen sonuçlar, PASA (R.K. Suresh ve K.M. Mohanasundaram, 2004), MOSA-I ve MOSA-II (T.K. Varadharajan, Chandrasekharan Rajendran, 2004), ve ?PGA-ALS (T. Pasupathy, Chandrasekharan Rajendran, R.K. Suresh, 2005) algoritmalarından elde edilen pareto optimum sonuçlar ile birleştirilerek net pareto cephe elde edilmiş ve çalışmaların net pareto cephede yer alan çözüm sayıları karşılaştırılmıştır. Önerilen algoritmanın net pareto cephenin oluşturulmasına diğer algoritmalardan daha fazla katkı sağladığı görülmüştür.

Abstract:
In this paper, we present a multi-objective algorithm for permutation flow shop scheduling problem to minimize makespan and total flow time. An effective artificial immune algorithm is proposed for searching pareto optimal frontier. Proposed algorithm based on the clonal selection principle. Algorithm divides the solution space to angular sections and determines intensification of the solutions in these angular sections. To obtain non-dominated and well-dispersed solutions, algorithm uses intensification of the angular sections when determining number of the clones of the good solutions. We have made use of 95 benchmark problems provided by Taillard [Eur. J. Operation. Res. 64 (1993) 278]. The non-dominated sets obtained from each of the existing bench-mark algorithms and the proposed PASA (R.K. Suresh ve K.M. Mohanasundaram, 2004, ?Pareto Archived Simulated Annealing for Permutation Flow Shop Scheduling with Multiple Objectives?), MOSA-I and MOSA-II (T.K. Varadharajan, Chandrasekharan Rajendran, 2004, ?A multi-objective simulated-annealing algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs?), and PGA-ALS (T. Pasupathy, Chandrasekharan Rajendran, R.K. Suresh,2005, ?A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs?) are compared, and subsequently combined to obtain a net non-dominated front. It is found that most of the solutions in the net non-dominated front are belong to proposed AIA algorithm.