Using ant colony optimization to find an optimum solution for resource constrained project scheduling problem


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Faculty of Engineering, Industrial Engineering, Turkey

Approval Date: 2009

Thesis Language: English

Student: SEYHAN ALVER

Supervisor: SEROL BULKAN

Abstract:

KARINCA KOLONİSİ OPTİMİZASYONU ALGORİTMASI’NIN KAYNAK KISITLI PROJE ÇİZELGELEME PROBLEMİNE OPTİMUM ÇÖZÜM BULMAK İÇİN UYGULANMASI Proje çizelgeleme problemi kaynak kısıtlaması veya çoklu proje çizelgelemesi ile ele alındığında optimal bir çözüm bulunması açısından oldukça zor bir problemdir. Kaynak kısıtlı proje çizelgeleme problemi önemli bir araştırma problemidir. Bu problem NP-zordur. Bu nedenle problemin çözümü için yalnızca kesin olan sonuçlara ulaşılmaya çalışılmamış, aynı zamanda çeşitli sezgisel çözümler de sunulmuştur. Genel olarak proje çizelgeleme problemi için kesin bir sonuca ulaşılabilecek problemlerin küçük boyutlu, aktivite sayısının 60’dan az olduğu ve yüksek bir kaynak kısıtlamasına sahip olmayan problemler olduğu, büyük boyutlu problemlerin çözümü için ise sezgisel yöntemlerin kullanılması gerektiği söylenmektedir. Bu nedenle problemin çözümü için sezgisel yöntemler de geliştirilmiştir. Karınca Kolonisi Optimizasyonu zor optimizasyon problemlerine yaklaşık çözümler bulabilmek için kullanılabilen popülasyona dayalı bir sezgisel yaklaşımdır. Karınca Kolonisi Optimizayonu’nda yapay karıncalar adı verilen yazılım ajanları verilen optimizasyon problemi için iyi çözümler bulmaya çalışırlar. Bu tez çalışması ile proje çizelgeleme problemi kaynak kısıtlaması durumu ile incelenmiş ve Karınca Kolonisi Optimizasyonu Algoritması kullanılarak çözülmeye çalışılmıştır. İlk olarak proje çizelgeleme problemleri için bir analiz gerçekleştirilmiştir. Bu genel analizi takiben kaynak kısıtlı proje çizelgeleme probleminin tanımı yapılmış, problemle ilgili kavramlar detaylı bir şekilde açıklanmış, problemin notasyonu ve amaçları anlatılmıştır. Daha sonra problemin çözümü ile ilgili seri ve paralel çizelge geliştirme planları ve nasıl uygulanacakları açıklanmıştır. Bunu takiben Karınca Kolonisi Optimizasyonu Algoritması’nın uygulanmasında başlangıç çizelgesi olarak kullanılacak çizelgeyi elde etmek amacıyla kullanılabilecek öncelik kurallarından bahsedilmiştir. Kuralların anlatımından sonra da Karınca Kolonisi Optimizasyonu Algoritması detaylı bir şekilde anlatılmıştır. Çalışmada Karınca Kolonisi Optimizasyonu Algoritması’na başlangıç çizelgesi oluşturmak için 6 farklı öncelik kuralı kullanılmıştır. Geliştirilen uygulama algoritmanın karakteristik değişkenlerinin farklı değerleri ile 480 değişik kaynak kısıtlı proje çizelgeleme problemi için çalıştırılmış ve elde edilen çözümler problemlerin optimum çözümleri ile karşılaştırılarak bulunan sonuçlar analiz edilmiştir. ABSTRACT USING ANT COLONY OPTIMIZATION ALGORITHM TO FIND AN OPTIMUM SOLUTION FOR RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM Project scheduling problem is a very hard problem to find an optimum solution if it is considered under resource constraints or multi project scheduling. Resource constrained project scheduling problem is a very important research problem. This problem is NP (Non-Polynomial)-hard. So not only exact solution procedures but also many different kinds of heuristics have been proposed to solve it. Generally, it is mentioned that the optimal solution for the problem can only be achieved by exact solution procedure in small projects, usually with less than 60 activities, which are not highly resource constrained. Therefore, heuristic methods are designed to solve large and highly resource constrained projects. Ant Colony Optimization is a population-based metaheuristic that can be used to find approximate solutions to difficult optimization problems. In Ant Colony Optimization, a set of software agents called artificial ants search for good solutions to a given optimization problem. In this study the project scheduling problem is considered under resource constraints and it is aimed to find an optimum solution for the problem by using Ant Colony Optimization. Firstly, a comprehensive analysis of project scheduling problems is performed. Following this analysis, the definition of resource constrained project scheduling problem is given, the concepts related to problem are explained in detail, the notation and the objectives of the problem are defined. Then the serial and the parallel schedule generation schemes related to problem solution and how they are implemented are explained. Following that, the priority rules which will be used to get the initial schedule to apply Ant Colony Optimization are mentioned and Ant Colony Optimization Algorithm is explained briefly. In the study 6 priority rules are used to form an initial schedule for Ant Colony Optimization Algorithm. The developed application is run with different values of characteristic variables of the algorithm for 480 different problem instances. The solutions obtained are analysed by comparing them with the optimum solutions.