Geri Dön

Öğrenme-unutma etkili ve ayar süreli tek makine çizelgeleme problemleri için yeni çözüm yaklaşımları

New solution approaches for single machine scheduling problems with learning-forgetting effects and setup times

  1. Tez No: 611873
  2. Yazar: SETTAR MUŞTU
  3. Danışmanlar: PROF. DR. TAMER EREN
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2020
  8. Dil: Türkçe
  9. Üniversite: Kırıkkale Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 206

Özet

Bu tez çalışmasında, değişken işlem sürelerinin ve beraberinde ayar sürelerinin olduğu iki farklı tek makine çizelgeleme problemi ele alınmıştır. İlk olarak; sıra bağımlı ayar süreleri ve pozisyona bağlı öğrenme etkisi olan toplam gecikme problemi tanımlanmıştır. NP-zor olan bu problemin kesin çözümleri için dal-sınır algoritması, yaklaşık çözümleri için ise iki adet genetik, iki adet de değişken komşu arama algoritması geliştirilmiştir. Dal-sınır algoritmasında kullanılmak üzere polinom zamanda türetilebilen bir alt sınır ve algoritmanın etkinliğini artırmak için iki farklı baskınlık kuralı ortaya konmuştur. Genetik algoritmanın uygunluk fonksiyonuna tavlama benzetimindeki sıcaklık parametresi ve değişken komşu arama algoritmasının karıştırma operatörüne de baskınlık kuralları eklenerek işlevsellikleri artırılmıştır. Rasgele türetilen problem örnekleri ile yapılan uygulama deneyleri neticesinde, çözüm yöntemlerinin performansları değerlendirilmiştir. Deney sonuçları, dal-sınır algoritmasının küçük boyutlu problem örneklerini makul sürelerde çözebildiğini, sezgisel yöntemlerin de yaklaşık çözümleri elde etme konusunda başarılı olduklarını göstermiştir. Bunun yanında, sezgisel yöntemlere uyarlanmış ilave özelliklerin performans üzerindeki olumlu etkileri de gözlemlenmiştir. İkinci olarak; sıra bağımsız ayar süreleri, zamana bağlı öğrenme etkisi ve yine zamana bağlı unutma etkisi olan maksimum tamamlanma zamanı problemi tanımlanmıştır. Tanımlanan problemde, bir işe yansıyan öğrenme şiddeti kendisinden önce çizelgelenmiş olan işlerin normal işlem süreleri toplamına bağlı bir fonksiyonla ifade edilmiştir. Her işlemden önce üretimin durmasına yol açan ayar süreleri, unutma etkisinin temel kaynağı olarak ele alınmıştır. Bu nedenle, bir işe yansıyan unutma şiddeti, hem duruştan önceki öğrenme şiddetine hem de o işe ait olan ayar süresine bağlı bir fonksiyonla ifade edilmiştir. İşlem süreleri öğrenme etkisinin, ayar süreleri de unutma etkisinin parametresi olduğundan, iki değişkenli yeni bir öğrenme-unutma modeli tanımlanmıştır. Probleme ait bir takım özellikler sayesinde çözüm karmaşıklığının normal şiddette NP-zor olduğu ıspatlanmıştır. Bu nedenle, kesin çözüm yöntemi olarak tam sayılı doğrusal olmayan programlama modeli ve dinamik programlama algoritması geliştirilmiştir. Önerilen dinamik programlama algoritmasının sözde-polinom zamanlı bir çözüm yöntemi olması, tanımlanan problemin normal şiddette NP-zor olduğunu desteklemiştir. Rasgele türetilen problem örnekleri ile yapılan uygulama deneyleri neticesinde, önerilen her iki yöntemin de etkinliği gösterilmiştir.

Özet (Çeviri)

In this thesis, two different single machine scheduling problems with variable processing times and setup times are discussed. At first; the total tardiness problem with sequence-dependent setup times and a position-dependent learning effect is defined. Since the problem is NP-hard, a branch&bound algorithm is proposed to obtain exact solutions. Furthermore, genetic and variable neighborhood search algorithms are proposed to obtain approximate solutions. A lower bound which can be calculated in polynomial time and two different dominance rules are employed in the branch&bound. The functionality of heuristics is increased by utilizing dominance rules in the shaking operator of the variable neighborhood search and adapting the temperature parameter of the simulated annealing to the fitness function of the genetic algorithm. Some computational experiments are performed on randomly generated test problems to evaluate the performance of solution approaches. Results show that the branch&bound can optimally solve the small-sized problem samples in a reasonable time and heuristics are successful in obtaining approximate solutions. Furthermore, the positive effects of additional features adapted to heuristics are also observed. Secondly; the makespan problem with sequence-independent setup times, time-dependent learning effect and time-dependent forgetting effect is defined. The learning amount of a job is represented by a function of the-sum-of-normal-processing-times of jobs scheduled before. Setup times are assumed to be the reason for forgetting since they lead to interruptions in the production period before each job. Therefore, the forgetting amount of a job is represented by a function of the setup time and existing amount of learning before the interruption. A new bivariate learning-forgetting model is defined since processing times are the parameter of the learning effect and setup times are the parameter of the forgetting effect. By means of problem properties, it is proved that the computational complexity of the defined problem is ordinary NP-hard. Therefore, an integer-nonlinear-programming-model and a dynamic programming algorithm are proposed as exact solution methods. The fact that the proposed dynamic programming is a pseudo-polynomial time algorithm supports the ordinary NP-hardness of the described problem. Some computational experiments with randomly generated problem samples are performed and results indicate the effectiveness of solution methods.

Benzer Tezler

  1. Fake news classification using machine learning and deep learning approaches

    Makine öğrenimi ve derin öğrenme yaklaşımlarını kullanarak sahte haber sınıflandırması

    SAJA ABDULHALEEM MAHMOOD AL-OBAIDI

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ TUBA ÇAĞLIKANTAR

  2. Protein fold classification and motif retrieval methods by using the primary and secondary structures

    Primer ve sekonder yapılar kullanılarak proteinlerin fold düzeyinde sınıflandırılması ve motif çıkarımı

    ÖZLEM POLAT

    Doktora

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. ZÜMRAY DOKUR ÖLMEZ

  3. Investigation metacognitive judgments under misinformation effect in the retrieval-induced forgetting paradigm: Effects of cue and feedback

    Yanlış bilgi etkisini içeren geri getirme yollu unutma paradigmasında üst bilişsel yargıların incelenmesi: İpucu ve geri bildirimin etkisi

    CEREN AKÇAM

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    PsikolojiBahçeşehir Üniversitesi

    Bilişsel Nöropsikoloji Ana Bilim Dalı

    PROF. DR. METEHAN IRAK

  4. Derin öğrenme ve büyük veri analitiği yöntemleriKullanarak Covid-19 yayılımının ileriye dönük tahmini

    Forecasting the spread of covid-19 using deep learning and big data analytics methods

    CYLAS KIGANDA

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

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

    Bilgisayar Bilimleri Ana Bilim Dalı

    PROF. DR. MUHAMMET ALİ AKCAYOL

  5. Okuma hatalarının okuma alışkanlığına etkisi

    Başlık çevirisi yok

    SARE MAVİ

    Yüksek Lisans

    Türkçe

    Türkçe

    1995

    Eğitim ve ÖğretimAnkara Üniversitesi

    DOÇ.DR. FİRDEVS GÜNEŞ