Sıra bağımlı hazırlık süresi ve makine kısıtları ile ilişkisiz paralel makine çizelgeleme problemine değişken komşuluk araması yaklaşımı
Variable neighborhood search approach on the unrelated parallel machine scheduling problem with sequence-dependent setup times and machine constraints
- Tez No: 897337
- Danışmanlar: DR. ÖĞR. ÜYESİ AHMED BURAK PAÇ
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: Türkçe
- Üniversite: Gebze Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 57
Özet
Bu çalışmada, sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemi ele alınmıştır. İşlerin birden fazla ilişkisiz paralel makinelerde işlenebileceği ve her işin işlenmeye başlamadan önce bir hazırlık süresine ihtiyaç duyduğu bir üretim ortamı modellenmektedir. Hazırlık süresi, makineye ve işlerin sırasına bağlı olarak değişkenlik göstermektedir. Problem, makinelerin planlı duruşlar nedeniyle belirli bir süre boyunca kullanılamayacağı varsayımı altında incelenmektedir. Çalışmanın amacı, toplam gecikme ve erken teslim sürelerini en aza indirmektir. NP-zor olarak sınıflandırılan problemin uzun çözüm süreleri ve kesin çözüme ulaşmanın zorluğu nedeniyle problemin çözümünde metasezgisel algoritmalar tercih edilmiştir. Çalışmada ele alınan sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemi için yeni bir Değişken Komşuluk Arama (DKA) algoritması önerilmiştir. Önerilen algoritma, çeşitli başlangıç çözümlerden başlayarak çözüm uzayının farklı alanlarını keşfetmek üzere tasarlanmış üç farklı komşuluk yapısı ve Değişken Komşuluk İniş (DKİ) algoritmasını kullanılmaktadır. Komşuluk dereceleri ile giderek büyüyen bir çözüm uzayı keşfedilmekte olup, mevcut duruma göre adaptif bir şekilde komşuluk yapısı seçimi yapılmaktadır. Bu yaklaşım, algoritmanın arama verimliliğini artırmayı ve global optimuma ulaşma süresini hızlandırmayı amaçlamaktadır. Sentetik veri oluşturma algoritmasıyla üretilen ve gerçek dünya verilerini iyi bir şekilde temsil eden test problemleri kullanılarak, önerilen DKA algoritması matematiksel programlama çözümleri ile karşılaştırıldı. Elde edilen sonuçlar, önerilen algoritmanın problemin çeşitli boyutları ve karmaşıklık düzeyleri için matematiksel programlama çözümlerine kıyasla çözüm süresi ve en iyi çözüme yakınsama yeteneğine göre daha etkin ve verimli bir yöntem olduğunu göstermektedir.
Özet (Çeviri)
In this study, the unrelated parallel machine scheduling problem with sequence-dependent setup times is addressed. A production environment is modeled where jobs can be processed on multiple unrelated parallel machines, and each job requires a setup time before processing. The setup time varies depending on the machine and the job sequence. The problem is examined under the assumption that machines may be unavailable for certain periods due to scheduled downtimes. The objective of the study is to minimize total tardiness and early completion times. Due to the NP-hard classification of the problem, which results in prolonged solution times and the difficulty of achieving exact solutions, metaheuristic algorithms have been employed. This study proposes a new Variable Neighborhood Search (VNS) algorithm for the unrelated parallel machine scheduling problem with sequence-dependent setup times. The proposed algorithm leverages three distinct neighborhood structures and the Variable Neighborhood Descent (VND) algorithm, designed to explore different regions of the solution space from various initial solutions. The neighborhood degrees facilitate the exploration of an increasingly expansive solution space, while the adaptive selection of the neighborhood structure is performed based on the current state of the solution. This approach aims to improve the efficiency of the search process and expedite the attainment of the global optimum. The proposed VNS algorithm was compared with mathematical programming solutions using test problems generated by a synthetic data generation algorithm, which well represents real-world data. The obtained results demonstrate that the proposed algorithm is a more effective and efficient method in terms of solution time and convergence ability to the best solution compared to mathematical programming solutions for various problem sizes and complexity levels.
Benzer Tezler
- A hybrid flow shop scheduling problem in ink production
Mürekkep üretiminde esnek akış tipi çizelgeleme problemi
AYLİN AKÇALI
Yüksek Lisans
İngilizce
2016
Mühendislik BilimleriYaşar ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ADALET ÖNER
- Sıra bağımlı hazırlık süreli, makine uygunluk kısıtları olan benzer paralel makine çizelgeleme problemi için sezgisel bir algoritma
A heuristic algorithm for uniform parallel machine scheduling problems with sequence dependent setup time, machine eligibility restrictions
FATİH FIRAT
Yüksek Lisans
Türkçe
2021
Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MÜJGAN SAĞIR
- Hazırlık süreli, makine uygunluk kısıtları ve ortak kaynak olduğu sıra bağımlı paralel makine çizelgeleme problemi için model etkileşimli genetik algoritma
Genetic algorithm with model interaction for sequence dependent parallel machine scheduling problem with setup time, machine eligibility restrictions and shared resources
EMİNE AKYOL
Yüksek Lisans
Türkçe
2013
Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TUĞBA SARAÇ
- Plastik enjeksiyon makinelerinde hammadde tabanlı ve sıra bağımlı hazırlık süreli tek makine çizelgeleme problemi: Bir otomotiv sektörü uygulaması
The single machine schedule problem with raw material based and sequence dependent setup time in plastic injection machines: An automotive industry application
GAZİ DİLEKÇİ
Yüksek Lisans
Türkçe
2023
Endüstri ve Endüstri MühendisliğiEskişehir Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ZEHRA KAMIŞLI ÖZTÜRK
- Dynamic scheduling of flexible job shops under capacity and setup constraints
Kapasite ve ayar kısıtları altında esnek atölyelerin dinamik çizelgelenmesi
FATMA SELEN KARASLAN
Doktora
İngilizce
2017
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ADİL BAYKASOĞLU