A genetic algorithm for the resource constrained project scheduling problem
Kısıtlı kaynaklı iş programlaması probleminin genetik algoritmalar ile çözülmesi
- Tez No: 305654
- Danışmanlar: DOÇ. DR. RIFAT SÖNMEZ
- Tez Türü: Yüksek Lisans
- Konular: İnşaat Mühendisliği, Civil Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: İnşaat Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 108
Özet
Kısıtlı kaynaklı iş programlaması problemi faaliyetlerin öncelik sırasını vekaynak kısıtlarını dikkate alarak mümkün olan minimum proje süresinibulmayı amaçlar. Bu problem polinomsal zamanda çözülebilen bir problemolduğu için kesin sonucu bulmaya yönelik algoritmalar küçük boyutluprojelerin çözümü ile sınırlıdır. Bu tezde sunulan genetik algoritma kesineyakın sonuçları küçük projelerin yanında kesin çözüm algoritmalarının zayıfolduğu büyük projeler için de bulmayı amaçlamaktadır. Geleneksel genetikalgoritmalara karşın, önerilen algoritma ileriye doğru planlama ile üretilen vegeriye doğru planlama ile üretilen iki farklı popülasyon içerir. Genetikalgoritma sürecinde ileriye (geriye) doğru planlama ile yapılan iş takvimlerigeriye (ileriye) doğru planlama ile yapılan iş takvimlerine dönüştürülür.Böylece, her iki tür takvimin karakteristikleri kullanılmış olur. Ayrıca, sunulanalgoritma eşleştirilecek bireyleri kaynakları kullandığı döneme göre seçerekyeni bir çaprazlama operatörü sunmaktadır. Kullanılan mutasyon operatörü isesadece iyileşen iş takvimlerini popülasyona dahil edecek şekilde yapılmıştır. Testsonuçları, önerilen algoritmanın sektörde iyi bilinen ve kısıtlı kaynaklarlaiş programlaması yapabilen Primavera Proje Planlayıcısı (P6 versiyon 7.0) veMicrosoft Project 2010 paket programlarına göre daha iyi olduğunugöstermektedir. Ayrıca, sunulan algoritma literatürdeki benzer çalışmalarda yeralan problemlerin çözümünde ve proje programlama problemkütüphanesindeki örnek problemlerin çözümünde başarılı sonuçlar eldeetmiştir. Sunulan algoritma özellikle problem kütüphanesindeki 120 ve 300aktiviteli projeler için tatmin edici sonuçlar vermiştir. Geliştirilen algoritmanınsınırları ve ileride yapılabilecek iyileştirmeler ile ilgili öneriler yapılmıştır.
Özet (Çeviri)
The resource-constrained project scheduling problem (RCPSP) aims to find aschedule of minimum makespan by starting each activity such that resourceconstraints and precedence constraints are respected. However, as the problemis NP-hard (Non-Deterministic Polynomial-Time Hard) in the strong sense, theperformance of exact procedures is limited and can only solve small-sizedproject networks. In this study a genetic algorithm is proposed for the RCPSP.The proposed genetic algorithm (GA) aims to find near-optimal solutions andalso overcomes the poor performance of the exact procedures for large-sizedproject networks. Contrarily to a traditional GA, the proposed algorithmemploys two independent populations: left population that consist of leftjustified(forward) schedules and right population that consist of right-justified(backward) schedules. The repeated cycle updates the left (right) population bymaintaining it with transformed right (left) individuals. By doing so, thealgorithm uses two different scheduling characteristics. Moreover, thealgorithm provides a new two-point crossover operator that selects the parentsaccording to their resource requirement mechanism. The algorithm alsoincludes a modified mutation operator which just accepts the improvedsolutions. Experiment results show that the suggested algorithm outperforms the wellknown commercial software packages; Primavera Project Planner (P6 version7.0) and Microsoft Project 2010 for the RCPSP. In addition, the algorithm istested with problems obtained from literature as well as the benchmarkPSPLIB (Project Scheduling Problem Library) problems. The proposedalgorithm obtained satisfactory results especially for the problems with 120 and300 activities. Limitations of the proposed genetic algorithm are addressed andpossible further studies are advised.
Benzer Tezler
- A genetic algorithm for the resource constrained project scheduling problem having a single machine with sequence dependent setup times
Sıra bağımlı kurulum zamanlı tek bir makineye sahip kaynak kısıtlı proje çizelgeleme problemi için bir genetik algoritma
SÜLEYMAN KAYA
Yüksek Lisans
İngilizce
2013
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. SEDEF MERAL
- Kaynak kısıtlı proje çizelgeleme probleminde tekrarsız kromozom destekli paralel genetik algoritma uygulaması
A parallel genetic algorithm application with nonrepetitive chromosome improvement for resource constrained project scheduling problem
ŞAFAK EBESEK
- A Genetic algorithm for multi-mode resource constrained project scheduling
Çok modlu, kaynak kısıtlamalı proje planlaması için bir genetik algoritma yaklaşımı
BURAK GÜVENÇ
Yüksek Lisans
İngilizce
2000
İnşaat MühendisliğiOrta Doğu Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA TALAT BİRGÖNÜL
- A hybrid genetic algorithm for multi mode resource constrained scheduling problem for large size projects
Büyük ölçekli projelerde çok modlu kaynak kısıtlı iş programlama problemi için geliştirilmiş bir hibrit genetik algoritma
MUSTAFA GÜREL
Yüksek Lisans
İngilizce
2015
İnşaat MühendisliğiOrta Doğu Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. RİFAT SÖNMEZ
