Geri Dön

Primal-dual heuristics for solving the set covering problem

Küme örtüleme problemlerinin çözümü için temel-eşlenik sezgiseller

  1. Tez No: 309383
  2. Yazar: BELMA YELBAY
  3. Danışmanlar: DOÇ. DR. Ş.İLKER BİRBİL, YRD. DOÇ. DR. KEREM BÜLBÜL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2009
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 50

Özet

Küme örtüleme problemi çizelgeleme, üretim, hizmet planlama, ağ eniyilemesi, uziletişim gibi pek çok alanda uygulanan iyi bilinen bir birleşi eniyileme problemidir. Küme örtüleme probleminin NP-zor olduğu kanıtlanmış olup, problemin etkin bir şekilde çözümüne yönelik çok sayıda birerleme algoritmaları ve sezgiseller geliştirilmiştir. Bu çalışmanın temel amacı küme örtüleme problemi için etkin bir sezgisel geliştirmektir. Sezgisel temel-eşlenik yaklaşımına dayalı olup literatürde NP-zor birleşi eniyileme problemlerini yaklaşıklamak için kullanılmaktadır.Bu çalışmada, sezgiselin başarımını değerlendirmek için sayısal çözümlemelerle birlikte sezgiselin geliştirilme aşamalarında elde ettiğimiz gözlemler sunulmaktadır. Elde edilen sonuçlar sezgiselin çözüm kalitesi ve hesaplama zamanı açısından iyi sonuçlar verdiğini göstermektedir. Bunun yanısıra sezgiselin basit, kolay uygulanabilir, ve büyük ölçekli problemleri etkin bir şekilde çözme potansiyeli olduğunu göstermektedir.

Özet (Çeviri)

The set covering problem (SCP) is a well known combinatorial optimization problem applied widely in areas such as; scheduling, manufacturing, service planning, network optimization, telecommunications, and so on. It has been already shown that SCP is NP-hard in the strong sense. Therefore, many heuristic and enumerative algorithms have been developed to solve SCP effectively. The primary purpose of the present study is to develop an effective heuristic for SCP. The heuristic is based on a primal-dual approach which is commonly used in the literature for approximating NP-hard optimization problems.In this study, we present numerical results to evaluate the performance of the heuristics as well as our observations throughout the development process. Our results indicate that the heuristic is able to produce good results in terms of both solution quality and computation time. Moreover, we show that the proposed heuristic is simple, easy to implement and has a potential to solve large-scale SCPs efficiently.

Benzer Tezler

  1. Efficient algorithms for the minimum cost perfect matching problem on general graphs

    Genel çizelgede en küçük maliyetli tam eşleme problemi için etkin algoritmalar

    ALPER ATAMTÜRK

    Yüksek Lisans

    İngilizce

    İngilizce

    1993

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA AKGÜL

  2. Sıkıştırılmış algılamada sezgisel algoritmaların kullanımına dayalı yöntemlerin incelenmesi ve geliştirilmesi

    Analyzing and development of heuristic algorithms in compressed sensing

    MURAT EMRE ERKOÇ

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    Elektrik ve Elektronik MühendisliğiErciyes Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. NURHAN KARABOĞA

  3. Ağ tasarım problemlerinde farklı bağlantılılıkların incelenmesi

    The examination of different connectivities on network design problems

    HAKAN KUTUCU

    Doktora

    Türkçe

    Türkçe

    2011

    MatematikEge Üniversitesi

    Matematik Ana Bilim Dalı

    PROF. DR. URFAT NURİYEV

  4. Yöneylem araştırmasında şebeke modellerine vekil kısıt uygulamaları

    Surrogate constraint applications to network models in operations research

    AYŞE SAKALLIOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    MatematikGiresun Üniversitesi

    Matematik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ HANDE GÜNAY AKDEMİR

  5. İç nokta algoritmaları ve simpleks yöntemi ile zamansal karşılaştırma

    Interior point algorithms and comparsion regarding time with the simplex method

    E. ESER BAYLAKOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    1999

    İstatistikGazi Üniversitesi

    İstatistik Ana Bilim Dalı

    YRD. DOÇ. DR. İHSAN ALP