An efficient branch and bound algorithm for the resource leveling problem
Kaynak dengeleme problemi için etkin bir dal ve sınır algoritması
- Tez No: 341014
- Danışmanlar: DOÇ. DR. RIFAT SÖNMEZ, YRD. DOÇ. DR. SABRİ TANKUT ATAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, İnşaat Mühendisliği, Industrial and Industrial Engineering, Civil Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- 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ı: İnşaat Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: 104
Özet
Kaynak dengeleme problemi (KDP) projelerin kaynak kullanım eğrilerini en iyilemeyi amaçlamaktadır. Bu kapsamda, dal ve sınır tabanlı bir algoritma geliştirilmiştir. Geliştirilen dal ve sınır algoritması doğrusal karma-tamsayılı modelleme yöntemi ile literatürde yer alan diğer dal ve sınır tabanlı yöntemlerle karşılaştırılmıştır. İyi bir üst sınır değeri hesabı için uyarlamalı bir dal ve sınır sezgiseli geliştirilmiştir. İkinci bir alt sınır değeri hesabı sunularak ikili alt sınır değeri hesabı KDP?nin çözümünde ilk defa kullanılmıştır. Alt sınır değerlerini geliştirmek için dal açma işleminde kullanılmak üzere çeşitli aktivite seçim metodları sunulmuştur. Algoritmayı hızlandırmak ve yüksek performanslı bir yöntem elde etmek amacıyla çeşitli teknikler uygulanmıştır. İçerisinde PSPLIB, Kolisch vd. (1999), Franck vd. (2001) ve Rieck vd. (2012)?den problem örneklerinin de olduğu literatürden alınan test setleri kullanılarak kapsamlı deneyler yapılmıştır. Geliştirilen dal ve sınır algoritması 20 aktiviteye kadar olan problemlerin tüm amaç fonksyonlarına göre çözümünde işlem süresi bakımından literatürdeki en iyi performansı sergilemiştir. Ayrıca, atıl kaynak günü en iyilemesinde literatürde ilk defa, dal ve sınır algoritması 30 aktiviteye kadar olan problemleri çözmüştür. Doğrusal karma-tamsayılı model aynı amaç fonksyonu için 10 aktiviteye kadar olan problemleri çözebilmiş ve bu yöntemin performansının kullanılan amaç fonksiyonuna yüksek oranda bağımlı olduğu gözlenmiştir. Geliştirilen dal ve sınır algoritması KDP?nin çözümünde işlem süresini hızlandırma tekniklerinin uygulanabilmesindeki ve birbirinden farklı amaç fonksiyonlarını çözebilmesindeki esnekliğiyle en iyileme algoritmaları için güçlü bir yöntem sunmaktadır.
Özet (Çeviri)
Resource leveling problem (RLP) focuses on optimizing resource utilization curves obtained by using Critical Path Method (CPM). This thesis presents a new and efficient branch and bound algorithm for the RLP. The proposed algorithm has been compared with mixed-integer linear modeling methods and previous branch and bound algorithms. An adaptive branch and bound heuristic has been developed for a good upper bound calculation. A new lower bound calculation strategy has been introduced and dual calculation has been used to obtain better lower bound values. Activity selection methods for branching process have been proposed to improve lower bounds and accelerating techniques have been implemented to achieve an efficient branch and bound algorithm for the RLP. Extensive computational experiments have been conducted using test problems from the literature including instances from Project Scheduling Problem Library (PSPLIB), Kolisch et al. (1999), Franck et al. (2001) and Rieck et al. (2012). The branch and bound algorithm has proven the best performance in terms of computational times for problems up to 20 activities for all objective functions. Moreover, for resource idle days optimization, problems up to 30 activities were solved for the first time in literature. Mixed-integer linear model could only solve problems with 10 activities for resource idle days and its performance highly depends on the type of the objective function. The proposed branch and bound algorithm provides a powerful method for the RLP due to its flexibility in applying several accelerating techniques and it can solve optimization functions in all forms.
Benzer Tezler
- Kaynak kısıtlı proje programlama problemlerinin çözümü için yeni yöntem ve algoritmalar
New methods and algorithms for solving the resource-constrained project scheduling problem
İHSAN UĞUR
- Bulanık çok modlu kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için matematiksel bir model
A mathematical model for the solution of the fuzzy multi mode resource-constrained project scheduling problems
ÖMER ATLI
Doktora
Türkçe
2012
Endüstri ve Endüstri MühendisliğiHava Harp Okulu KomutanlığıEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CENGİZ KAHRAMAN
- Multiobjective relational data warehouse design for the cloud
Bulut için çok amaçlı ilişkisel veri ambarı tasarımı
TANSEL DÖKEROĞLU
Doktora
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET COŞAR
- İzlenceleme problemleri için alt sınır tahmin yöntemleri
Lower bound estimation methods for scheduling problems
RIZA DİNDİR
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. MEHMET EMİN DALKILIÇ
- Öbek analizi algoritmaları
Başlık çevirisi yok
MUHAMMET ALTUN
Yüksek Lisans
Türkçe
1998
Mühendislik Bilimleriİstanbul Teknik ÜniversitesiMühendislik Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. ALİ ERCENGİZ