Büyük komşuluk arama ve tavlama benzetimi ile askeri nöbet programının planlanması
Military duty scheduling with large neighborhood search and simulated annealing
- Tez No: 1024428
- Danışmanlar: DOÇ. DR. CANER ÖZCAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Nöbet çizelgeleme, Optimizasyon, Tavlama benzetimi, Duty scheduling, Optimization, Simulated annealing
- Yıl: 2026
- Dil: Türkçe
- Üniversite: Karabük Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Askeri personel tarafından belirli zaman dilimlerinde ve konumlarda tutulan nöbetlerin planlanması; nöbet yeri, zaman ve personel sayısının artmasıyla birlikte karmaşık bir çizelgeleme problemine dönüşmektedir. Uygulamada bu planlamalar çoğunlukla elle veya belirli bir mantık çerçevesinde yapıldığından, personel arasında adil olmayan nöbet dağılımları ortaya çıkabilmektedir. Bu tez çalışmasında askeri nöbet çizelgeleme problemi bir kombinatorik optimizasyon modeli olarak kurulmuştur. Model, yer ve zamana bağlı zorluk katsayılarını, belirli yer--gün--zaman birleşimlerine tanımlanan istisnai zorlukları, tek ve çift nöbet noktalarını ve personelin geçmiş nöbet yükünü dikkate alan kümülatif adillik unsurlarını bir arada içermektedir. Katı kısıt ihlalleri ise amaç fonksiyonuna ihlal başına sabit ve yüksek bir ceza puanıyla bağlanmıştır. Çift nöbetlerdeki ikili tercih, izin ve dinlenme kısıtları nedeniyle can dostun (askerin birlikte nöbet tutmayı tercih ettiği arkadaşının) her nöbette hazır bulunamayabileceği gerçeğinden hareketle, manga yapısına dayalı dereceli bir uyum ölçüsüyle modellenmiştir. Problemin çözümü için Tavlama Benzetimi (Simulated Annealing, SA) ve Büyük Komşuluk Araması (Large Neighborhood Search, LNS) temelli metasezgisel yöntemler sistematik olarak karşılaştırılmıştır. Karşılaştırma; hamle ölçeği, operatör bilgisi ve kabul kuralı olmak üzere üç boyutta yürütülmüş, iki yöntemin problem bilgisiyle donatılmış biçimleri ile hibrit birleşimlerini de kapsamıştır. Yöntemler, kapasite baskısı içeren küçük, orta ve büyük boyutlu üç sentetik senaryoda, bütün iyileştirme yöntemlerine eşit süre tanıyan bir protokolle ve eşleştirilmiş istatistiksel testlerle sınanmıştır. En iyi sonucu, problem bilgisiyle donatılmış (problem bilgili) SA vermiştir. Yöntem bütün senaryolarda katı kısıtları ihlal etmeyen çizelgeler üretmiş ve çift nöbetlerde 0,96--0,99 ortalama uyuma ulaşmıştır. Problem bilgili SA'ya kıyasla toplam maliyet; basit yöntemlerde yaklaşık 9--11 kat, klasik SA'da 1,3--1,4 kat, klasik LNS'de ise 6--8 kat daha yüksektir. Bileşen katkıları eşleştirilmiş deneylerle ayrıştırılmıştır. Problem bilgili operatörler klasik SA'yı %25--30, klasik LNS'yi %15--23 iyileştirmiştir. Metropolis kabulü birim ölçekli komşuluklarda toplam maliyeti %46--55 iyileştirmiş, salt blok komşuluğunda ise katkı sağlamamıştır. Blok ölçekli hamleler hibrite katkı getirmemiş, problem büyüdükçe anlamlı bir maliyet artışına yol açmıştır. Kapasite baskısı altında ortaya çıkan başlangıç ihlalleri, amaç fonksiyonundaki yüksek ceza terimi sayesinde bütün yöntemlerde onarılmıştır. Geçmiş puanı ile dönem yükü arasındaki güçlü negatif ilişki ve iki ardışık dönemde kümülatif yük sapmasının %50--73 oranında azalması, adillik mekanizmasının hem personel düzeyinde hem dönemler arasında çalıştığını doğrulamıştır. Sonuçlar, sentetik senaryolar kapsamında, kazanan yaklaşımın adil, hızlı ve otomatik bir nöbet planlama aracı olarak kullanılabileceğine işaret etmektedir.
Özet (Çeviri)
The planning of military guard duties, performed by personnel at specific time slots and locations, turns into a complex scheduling problem as the number of duty points, time slots and personnel increases. In practice these schedules are usually prepared manually or with ad-hoc rules, which often results in an unfair distribution of duties among personnel. In this thesis, the military duty scheduling problem is formulated as a combinatorial optimization model. The model jointly captures location- and time-dependent difficulty coefficients, exceptional difficulties defined for specific location--day--time combinations, single and double duty posts, and cumulative fairness that accounts for each person's past duty load. Hard-constraint violations are attached to the objective through a fixed, high per-violation penalty term. Since leave and rest constraints do not always keep the buddy available, pair preference in double duties is modelled as a graded compatibility measure based on the squad structure rather than a binary indicator. To solve the problem, metaheuristic methods based on Simulated Annealing (SA) and Large Neighborhood Search (LNS) are systematically compared. The comparison is conducted along three dimensions, namely move scale, operator knowledge and acceptance rule, and covers the problem-informed variants of both methods as well as their hybrid combination. The methods are evaluated on three synthetic scenarios of small, medium and large size under capacity pressure, using a protocol that grants every improvement method an equal wall-clock budget together with paired statistical tests. The best results are obtained by problem-informed SA. The method produces schedules with zero hard-constraint violations in all scenarios and reaches an average pair compatibility of 0.96--0.99. The total cost of the naive methods is roughly 9--11 times, that of classical SA 1.3--1.4 times and that of classical LNS 6--8 times that of problem-informed SA. Component contributions are isolated through paired ablation experiments. Problem-informed operators improve classical SA by 25--30% and classical LNS by 15--23%. Metropolis acceptance improves the total cost by 46--55% on unit-scale neighborhoods, while providing no benefit on the block-only neighborhood. Block-scale moves do not contribute to the hybrid and cause a significant cost increase as the problem grows. Initial infeasibilities arising under capacity pressure are repaired by all methods thanks to the high penalty term in the objective. The strong negative correlation between past scores and assigned loads, together with the cumulative load deviation decreasing by 50--73% over two consecutive periods, confirms that the fairness mechanism works both at the personnel level and across periods. The results indicate that, within these synthetic scenarios, the winning approach can serve as a fair, fast and automated duty planning tool.
Benzer Tezler
- Kapasiteli araç rotalama problemi için değişken komşuluk iniş ve tavlama benzetimi hibrit sezgisel çözüm yaklaşımı
Variable neighborhood descent and simulated annealing hybrid heuristic solution approach for capacitated vehicle routing problem
HÜSNA TOKEL
Yüksek Lisans
Türkçe
2024
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. ERTAN GÜNER
- Fractal geometry inspired solution generation to enhance effectiveness of metaheuristic algorithms
Metasezgisel algoritmaların etkinliğini arttırmak için esin kaynağı fraktal geometri olan çözüm oluşturma
MELİKE ÖZTÜRK
Doktora
İngilizce
2020
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiMühendislik Yönetimi Ana Bilim Dalı
PROF. DR. ÇİĞDEM ALABAŞ USLU
- P-hub center and routing network design problem and solution algorithms
P-ana dağıtım üssü merkez ve rotalama ağ tasarımı problemı ve çözüm algorıtmaları
ABDUL KADER KASSOUMEH
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET ARSLAN
DR. ÖĞR. ÜYESİ ZÜHAL KARTAL
- Modeling and optimization of the drone base stations location allocation problem
Drone baz istasyonlarının yerleşim-tahsis probleminin modellenmesi ve optimizasyonu
ÖZGE ŞATIR AKPUNAR
Doktora
İngilizce
2025
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ŞENER AKPINAR
- Sıra bağımlı hazırlık süresi bulunan ilişkisiz paralel makine çizelgeleme probleminin melez ateş böceği algoritması ile çözümü
Solving the unrelated parallel machine scheduling problem with sequence-dependent setup times using a hybrid firefly algorithm
BUĞRA DAVUT DAŞKIN
Yüksek Lisans
Türkçe
2024
Endüstri ve Endüstri MühendisliğiKaradeniz Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ KADİR BÜYÜKÖZKAN