Geri Dön

A branch and bound algorithm for resource leveling problem

Kaynak dengelenme probleminin çözülmesi amacıyla bir dal ve sınır algoritması geliştirilmesi

  1. Tez No: 269095
  2. Yazar: MUSTAFA ÇAĞDAŞ MUTLU
  3. Danışmanlar: DOÇ. DR. RIFAT SÖNMEZ
  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: 2010
  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ı: Belirtilmemiş.
  13. Sayfa Sayısı: 121

Özet

Kaynak Dengeleme Problemi (KDP), kaynak çizelgelerindeki istenmeyen dalgalanmaların asgari düzeye indirilmesini, böylelikle bu dalgalanmaların yol açabileceği olası sorunların önlenmesini amaçlamaktadır. Proje planlamasında ve yönetiminde yaygın olarak kullanılan paket programların KDP'ni çözmede yetersiz kaldıkları çok sayıda araştırmada belirtilmiştir. Bu çalışma kapsamında, tek ve çok kaynaklı, küçük ölçekli şebekelerde KDP için en optimal çözümü bulmayı amaçlayan bir dal ve sınır algoritması geliştirilmiştir. Geliştirilen algoritma derinliğine arama stratejisini esas almakta ve arama ağacının herbir düğümünde belirli bir aktivite için geçerli bir başlangıç tarihi saklamaktadır. 4 ayrı kaynak dengeleme ölçütü için en optimal çözümü bulabilen yöntem, çok sayıda alt sınır hesaplama tekniğine yer vererek arama alanını sınırlandırılmaya çalışmaktadır. 20 iş programı üzerinde yapılan deneyler, geliştirilen algoritmanın 20 aktiviteli şebekelere kadar olan problemlerde en optimal çözümleri bulabildiğini göstermiştir.Sunulan yöntem literatüre iki önemli noktada katkı sağlamaktadır. Öncelikle, önerilen alt sınır hesaplama tekniği (izin verilebilen en fazla günlük kaynak tüketimi) en optimal çözümün bulunması için ihtiyaç duyulan hesaplama zamanının kısaltılmasını sağlamıştır. Ayrıca, bazı küçük ölçekli kaynak dengeleme problemlerinin çeşitli ölçütler için optimal çözümleri sunularak gelecekte geliştirilecek sezgisel yöntemlerin performanslarının değerlendirilmesi amacıyla bir örnek problem seti oluşturulmuştur. Yakın zamanda önerilmiş olan ?atıl kaynak günü? kaynak dengeleme ölçütü için pekçok problemin en optimal çözümleri literatürde ilk defa bulunmuştur. Geliştirilen yöntemin kısıtlamaları tartışılmış ve ileride yapılabilecek çalışmalar ile ilgili önerilerde bulunulmuştur.

Özet (Çeviri)

Resource Leveling Problem (RLP) aims to minimize undesired fluctuations in resource distribution curves which cause several practical problems. Many studies conclude that commercial project management software packages can not effectively deal with RLP. In this study a branch and bound algorithm is presented for solving RLP for single and multi resource, small size networks. The algorithm adopts a depth-first strategy and stores start times of non-critical activities in the nodes of the search tree. Optimal resource distributions for 4 different types of resource leveling metrics can be obtained via the developed procedure. To prune more of the search tree and thereby reduce the computation time, several lower bound calculation methods are employed. Experiment results from 20 problems showed that the suggested algorithm can successfully locate optimal solutions for networks with up to 20 activities.The algorithm presented in this study contributes to the literature in two points. First, the new lower bound improvement method (maximum allowable daily resources method) introduced in this study reduces computation time required for achieving the optimal solution for the RLP. Second, optimal solutions of several small sized problems have been obtained by the algorithm for some traditional and recently suggested leveling metrics. Among these metrics, Resource Idle Day (RID) has been utilized in an exact method for the first time. All these solutions may form a basis for performance evaluation of heuristic and metaheuristic procedures for the RLP. Limitations of the developed branch and bound procedure are discussed and possible further improvements are suggested.

Benzer Tezler

  1. An efficient branch and bound algorithm for the resource leveling problem

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

    HÜSEYİN YENİOCAK

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    İnşaat Mühendisliği Bölümü

    DOÇ. DR. RIFAT SÖNMEZ

    YRD. DOÇ. DR. SABRİ TANKUT ATAN

  2. Resource leveling of a linear construction project using branch and bound algorithm

    Doğrusal bir inşaat projesinin dal ve sınır algoritması kullanılarak kaynak dengelemesi

    RESULALİ EMRE ÖRGÜT

    Yüksek Lisans

    İngilizce

    İngilizce

    2012

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÜL POLAT TATAR

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

  4. Minimizing makespan in a resource constrained project scheduling problem

    Kaynak kısıtlı proje çizelgeleme probleminde proje süresinin minimizasyonu

    YAĞMUR YAŞAR

    Yüksek Lisans

    İngilizce

    İngilizce

    1996

    İşletmeOrta Doğu Teknik Üniversitesi

    Y.DOÇ.DR. CEMAL AKYEL

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