Geri Dön

An efficient branch and bound algorithm for the resource leveling problem

Kaynak dengeleme problemi için etkin bir dal ve sınır algoritması

  1. Tez No: 341014
  2. Yazar: HÜSEYİN YENİOCAK
  3. Danışmanlar: DOÇ. DR. RIFAT SÖNMEZ, YRD. DOÇ. DR. SABRİ TANKUT ATAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, İnşaat Mühendisliği, Industrial and Industrial Engineering, Civil Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2013
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: İnşaat Mühendisliği Bölümü
  12. Bilim Dalı: İnşaat Mühendisliği Ana Bilim Dalı
  13. 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

  1. 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

    Doktora

    Türkçe

    Türkçe

    1987

    İşletmeİstanbul Teknik Üniversitesi

    PROF.DR. ATAÇ SOYSAL

  2. 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

    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

  3. 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

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET COŞAR

  4. İ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

    Türkçe

    1998

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Uluslararası Bilgisayar Ana Bilim Dalı

    DOÇ. DR. MEHMET EMİN DALKILIÇ

  5. Öbek analizi algoritmaları

    Başlık çevirisi yok

    MUHAMMET ALTUN

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    Mühendislik Bilimleriİstanbul Teknik Üniversitesi

    Mühendislik Bilimleri Ana Bilim Dalı

    YRD. DOÇ. DR. ALİ ERCENGİZ