Multiobjective genetic algorithm approaches to project scheduling under risk

Abstract

ÖZET RİSK ALTINDA PROJE ÇİZELGELEME PROBLEMİNE GENETİK ALGORİTMA ÇÖZÜM YAKLAŞIMLARI Bu tezde risk altında proje çizelgeleme problemi ele alınmıştır. Risk altında proje çizelgeleme problemi iki amaçlı karar problemi olarak tanımlanmış ve 0-1 tamsayılı matematiksel programlama modeli olarak formüle edilmiştir. İki amaçlı bu modelde, bir amaç beklenen proje süresinin en küçüklenmesi diğer amaç ise beklenen proje maliyetinin en küçüklenmesidir. Bu probleme çözüm yaklaşımı olarak genetik algoritma (GA) seçilmiştir. Çok amaçlı GA literatürü detaylı olarak incelendikten sonra vektör değerlendirmeli GA üzerine iki strateji ve ayrıca yeni bir GA önerilmiştir. Bu GAlar için parametreler üzerinde yapılan istatistik! deneyler sonucunda uygun parametre değerleri seçilmiştir. Seçilen parametreler yapılan çalışmalarda kullanılmıştır. Bu tezde ayrıca GA sonuçlarım geliştirmek üzere üç tane sezgisel yöntem önerilmiştir. Bu sezgisel yöntemlerin amacı, beklenen proje süresini sabit tutarken beklenen proje maliyetini azaltmaktır. Sezgisel yöntemler önerilen GA'nın sonuna eklenmiş ve bu algoritmanın sonuçlarını geliştirmek amacıyla kullamlmıştır. Son olarak, GAlar ve sezgisel yöntemler üç farklı problem sınıfı üzerinde sulanmıştır. Sonuçlar üzerinden algoritmaların ve sezgisel yöntemlerin ikili (fi karşılaştırmaları yapılmıştır. Ayrıca GAMS ticari matematiksel programlama yazılımı kullanılarak Pareto yüzeyinin bir yaklaşımı yapılmıştır. Önerilen GA'nın sonuçlarının bu yaklaşımla da yalan olduğu görülmüştür. Sezgisel yöntemlerin ise ikili karşılaştırması yapılmış ve bu karşılaştırmaların sonuçlan rapor edilmiştir. vı

ABSTRACT MULTIOBJECTIVE GENETIC ALGORITHM APPROACHES TO PROJECT SCHEDULING UNDER RISK In this thesis, project scheduling under risk is chosen as the topic of research. Project scheduling under risk is defined as a biobjective decision problem and is formulated as a 0-1 integer mathematical programming model. In this biobjective formulation, one of the objectives is taken as the expected makespan minimization and the other is taken as the expected cost minimization. As the solution approach to this biobjective formulation genetic algorithm (GA) is chosen. After carefully investigating the multiobjective GA literature, two strategies based on the vector evaluated GA are developed and a new GA is proposed. For these three GAs first the parameters are investigated through statistical experimentation and then the values are decided upon. The chosen parameters are used for the computational study part of this thesis. In this thesis three improvement heuristics are developed also to further improve the GA solutions. The aim of these improvement heuristics is to decrease the expected cost of the project while keeping the expected duration of the project fixed. These improvement heuristics are implemented at the end of the proposed GA and used to improve the results of the proposed GA. Finally the GAs and improvement heuristics are tested on three different sets of problems. The results are evaluated by pairwise comparisons of algorithms and of heuristics. Also an approximation of the true Pareto front is generated using the commercial mathematical modelling program, GAMS®. The results are compared to that approximation and they seem comparable to that solution. The results of the improvement heuristics are also compared against each other and the performance of the heuristics is reported in detail.