Çok Aşamalı Esnek İş Atölyesi Çizelgeleme Problemi (Multi-Stage Flexible Job Shop Scheduling Problem, MS-FJSP), işleri üretim aşamalarına ayıran, bir aşamada birden fazla uyumlu makinenin seçilebilmesine ve seçilen makinelerin işleme sırasının değişebilmesine izin veren bir kombinatoryal çizelgeleme modelidir. Çalışma, klasik esnek iş atölyesi çizelgelemesindeki tek makine seçimi ve daha katı işlem rotası varsayımlarını genişletmekte; çözüm için parçacık sürü optimizasyonunu çift-komşuluklu tabu aramasıyla birleştiren TS-PSO algoritmasını önermektedir. Modelin temel optimizasyon hedefi doğrudan üretim tamamlanma süresini en aza indirmek değil, belirlenen çizelgeleme ufku boyunca her makine türüne yönelik talebin zamansal varyansını azaltarak gerekli makine sayısının daha dengeli dağıtılmasını sağlamaktır.
TS-PSO'da parçacık sürü optimizasyonu (PSO), geniş çözüm uzayında başlangıç çözüm yapısının oluşturulması ve makine talebinin yaklaşık dağılımının belirlenmesi için kullanılır. Ardından tabu araması, MS-FJSP'nin makine seçimi ve sıralama esnekliğine göre oluşturulan iki ayrı komşuluk üzerinde yerel iyileştirme yapar. Araştırmacılar yöntemi 120 farklı problem ölçeğine dağıtılmış toplam 12.000 üretilmiş MS-FJSP örneği üzerinde Simulated Annealing (SA), Ant Colony Optimization (ACO) ve Genetic Algorithm (GA) ile karşılaştırmış; ayrıca algoritmanın bileşenlerini ablasyon deneyleriyle incelemiştir.
Üretilmiş problem örneklerinde daha düşük amaç fonksiyonu değerinin daha dengeli makine talebi anlamına geldiği değerlendirmede TS-PSO bütün ana karşılaştırma ölçeklerinde üç temel yöntemin altında amaç fonksiyonu değerleri elde etmiştir. Kaynağın genel hesaplamasına göre SA'nın TS-PSO'ya ortalama farkı yaklaşık %1,21, GA'nın yaklaşık %3,22 ve ACO'nun yaklaşık %4,04'tür. Bu kalite artışı bazı örneklerde biraz daha yüksek hesaplama süresi pahasına elde edilmiştir; süreler genel olarak karşılaştırılan algoritmalarla aynı büyüklük mertebesinde kalmıştır.
Gerçek-dünya bağlantısı için First Bethune Hospital of Jilin University'nin 2024 personel yerleştirme problemi MS-FJSP olarak modellenmiştir. Bu örnekte 72 bölüm makine türlerini, 26 mesleki arka plan iş gruplarını, 491 personel işleri ve ortalama 13 uyumlu bölüm makine uyumluluğunu temsil etmektedir. Kaynak, bu model için çözüm uzayını \(1\times10^{5194}\) olarak raporlamaktadır. TS-PSO burada da karşılaştırılan yöntemlerden daha düşük varyans değerleri üretmiştir. Bununla birlikte sonuçlar bir algoritmik modelleme ve hesaplamalı deney doğrulamasıdır; gerçek kurumda çizelgenin uygulanmasının operasyonel sonuçlarını ölçen bir saha deneyi değildir.
MS-FJSP Nedir?
MS-FJSP, işlerin aşamalı işlem rotalarına sahip olduğu ve her aşamada gereken makine türlerinin hem seçiminin hem de sırasının belirli kısıtlar altında esnek tutulduğu bir esnek iş atölyesi çizelgeleme problemidir. Klasik FJSP'den ayrılan temel nokta, bir işlemin yalnız tek bir uyumlu makineye atanması zorunluluğunu gevşeterek aynı aşamada birden fazla makine türünün kullanılabilmesine ve bu makinelerin işleme sırasının değiştirilebilmesine izin vermesidir.
Klasik FJSP'den hangi açıdan ayrılıyor?
Klasik Flexible Job Shop Scheduling Problem (FJSP) iki temel kararı birlikte ele alır: işlerin hangi sırayla yürütüleceği ve her işlemin hangi uyumlu makinede gerçekleştirileceği. İncelenen çalışmada bu yapı iki yönden genişletilmektedir. Birincisi, işlemler üretim aşamaları halinde düzenlenmekte ve bir sonraki aşamaya ancak önceki aşama tamamlandıktan sonra geçilebilmektedir. İkincisi, bir aşamada tek bir makine seçmek yerine gerekli sayıda makine türü seçilebilmekte ve seçilen makinelerin kendi aralarındaki işlem sırası değişebilmektedir.
Model ayrıca işleri işlem rotalarına göre gruplandırır. Aynı iş grubundaki işler aynı işlem şemasını izler. Bu gruplandırma, Flexible Group Shop Scheduling Problem'deki benzer rotaları bir araya getirerek kurulum süresini azaltma fikriyle aynı değildir. MS-FJSP'deki gruplandırmanın amacı aynı iş tipinin tekrarlı üretimini ve aynı şema içinde çok sayıda işin bulunmasını modellemektir.
Aşama kavramı neden önemli?
Aşamalı yapı, bir üretim veya çizelgeleme sürecindeki seçenekleri tek bir doğrusal makine rotasına sıkıştırmak yerine, kararları ardışık fakat kendi içinde esnek işlem bloklarına ayırır. Bir iş grubu \(i\) için aşama sayısı \(kn_i\) ile gösterilir. \(k\) numaralı aşamada kullanılabilecek makine türlerinin kümesi \(LM_{i,k}\), kullanılabilir makine türü sayısı \(NT_{i,k}\), gerçekten gerekli makine türü sayısı ise \(N_{i,k}\) ile temsil edilir.
Bu ayrım çözüm uzayını hızla büyütür. Bir aşamada yalnız hangi makinelerin seçileceği değil, seçilen makinelerin hangi sırayla kullanılacağı da karara dahildir. Dolayısıyla problem, makine seçenekleri ve aşama sayısı arttıkça klasik tek-atamalı yapılara göre çok daha büyük bir kombinatoryal arama uzayı oluşturur.
Modelin zaman ve makine talebi temsili
Çalışma iki temel matris kullanır. \(RM\) makine atama matrisidir ve iş × zaman yapısında hangi işin hangi zaman adımında hangi makine türünde işlendiğini temsil eder. \(RN\) ise makine talep matrisidir; makine türü × zaman yapısında her zaman adımında belirli bir makine türünden kaç adet gerektiğini gösterir.
| Sembol | Anlamı |
|---|---|
| \(jn\) | Toplam iş sayısı |
| \(J_{i,j}\) | \(i\). iş grubundaki \(j\). iş |
| \(gn\) | Toplam iş grubu sayısı |
| \(gn_i\) | \(i\). iş grubundaki iş sayısı |
| \(kn_i\) | \(i\). iş grubunun işlem aşaması sayısı |
| \(mn\) | Toplam makine türü sayısı |
| \(M_l\) | \(l\). makine türü |
| \(M_0\) | Tüm işlemlerin tamamlandığını belirten sanal makine |
| \(T_{\max}\) | Toplam çizelgeleme süresi / zaman ufku |
| \(pt_{i,k,l}\) | \(i\). grubun \(k\). aşamasının \(M_l\) üzerindeki işlem süresi |
| \(bt_{i,j,k}\) | \(J_{i,j}\) işinin \(k\). aşamasının başlangıç zamanı |
| \(et_{i,j,k}\) | \(J_{i,j}\) işinin \(k\). aşamasının tamamlanma zamanı |
| \(LM_{i,k}\) | \(i\). grubun \(k\). aşamasında kullanılabilecek makine indeksleri |
| \(NM_{i,j,k}\) | \(J_{i,j}\) işinin \(k\). aşamasında gerçekten kullanılan makine indeksleri |
| \(O_{i,k,n}\) | \(i\). grubun \(n\) makine gerektiren \(k\). aşama işlemi |
| \(N_{i,k}\) | \(i\). grubun \(k\). aşamasında gerekli makine türü sayısı |
| \(NT_{i,k}\) | \(i\). grubun \(k\). aşamasında kullanılabilir makine türü sayısı |
| \(RM\) | İş × zaman makine atama matrisi |
| \(RN\) | Makine türü × zaman makine talep matrisi |
| \(\mu_{i,j,t,l}\) | \(J_{i,j}\) işi \(t\) anında \(M_l\) üzerinde işleniyorsa 1, aksi halde 0 |
| \(\phi_{i,j,k,l}\) | \(J_{i,j}\) işi \(k\). aşamada \(M_l\) kullanıyorsa 1, aksi halde 0 |
| \(\xi_{i,k,l}\) | \(i\). grubun \(k\). aşaması \(M_l\)'yi kullanabiliyorsa 1, aksi halde 0 |
Amaç Fonksiyonu Neyi Optimize Ediyor?
MS-FJSP'nin bu çalışmadaki amaç fonksiyonu, her makine türüne yönelik zaman içindeki talep miktarının varyanslarını toplayıp bu toplamı en aza indirir; dolayısıyla daha düşük değer, aynı çizelgeleme ufku içinde makine ihtiyacının zamana daha dengeli yayılması anlamına gelir. Bu nokta önemlidir çünkü çalışma klasik FJSP çalışmalarında sık görülen yalnızca makespan minimizasyonundan farklı olarak makine sayısı tahsisinin düzgünlüğünü doğrudan optimizasyon hedefi haline getirir.
Her makine türü için zaman ortalamasından sapmaların karesine dayanan temel amaç fonksiyonu kaynakta şu şekilde tanımlanmıştır:
\[ f(RN)= \sum_{x=1}^{mn} \sum_{y=1}^{T_{\max}} \frac{ \left( RN_{x,y}- \frac{\sum_{y'=1}^{T_{\max}}RN_{x,y'}}{T_{\max}} \right)^2 }{ T_{\max} }. \]
Burada \(RN_{x,y}\), \(x\). makine türüne \(y\). zaman adımındaki talebi; parantez içindeki ikinci terim ise aynı makine türünün tüm çizelgeleme ufkundaki ortalama talebini gösterir. Dolayısıyla fonksiyon, talep eğrisinin ortalama etrafındaki yayılımını cezalandırmaktadır.
Çözüm uzayı neden çok hızlı büyüyor?
\(i\). iş grubunun \(k\). aşamasında \(NT_{i,k}\) adet kullanılabilir makine türü arasından sıralı olarak \(N_{i,k}\) makine seçilebiliyorsa kaynak, olası seçim ve sıralama sayısını şöyle tanımlar:
\[ p_{i,k}=\frac{NT_{i,k}!}{(NT_{i,k}-N_{i,k})!}. \]
Bir işin bütün aşamalarındaki rota sayısı:
\[ P_i=\prod_{k=1}^{kn_i}p_{i,k}. \]
Aynı gruptaki işler ayırt edilemiyorsa toplam çizelgeleme olasılığı kaynakta:
\[ P= \prod_{i=1}^{gn} \frac{(P_i+gn_i-1)!}{gn_i!\,(P_i-1)!} \]
olarak; işler ayırt edilebiliyorsa ise:
\[ P= \prod_{i=1}^{gn}P_i^{gn_i} \]
olarak verilmektedir. Bu ifadeler, makine sayısı ve aşama seçenekleri arttığında kaba kuvvetle bütün çözümleri taramanın neden pratik olmaktan çıktığını gösterir.
TS-PSO Neden İki Arama Mekanizmasını Birleştiriyor?
TS-PSO, PSO'nun geniş çözüm uzayında hızla iyi bir başlangıç yapısı oluşturma özelliğini tabu aramasının mevcut iyi çözümün çevresinde ayrıntılı yerel arama yapabilmesiyle birleştirir. Çalışmadaki iş bölümü yaklaşık olarak “PSO ile başlangıç yapısını ve talep dağılımını kestir, ardından MS-FJSP'ye özgü iki komşuluk üzerinde tabu aramasıyla iyileştir” biçimindedir.
PSO katmanı: kodlama, çözme ve başlangıç yapısı
PSO aşamasında her makine türü için bir DM veri matrisi oluşturulur. Matrisin satırları ilgili makine türünün yer aldığı işlem aşamalarını, sütunları ise iş grubu büyüklüğü, işlem süresi ve ilgili zaman aralığı gibi bilgileri taşır. Bir parçacık \(RC\in\mathbb{R}^{cn\times T_{\max}}\) matrisiyle temsil edilir. Başlangıçta ilgili zaman aralığına, toplamı o gruptaki iş sayısına eşit olacak biçimde negatif olmayan tam sayılar dağıtılır.
Her parçacığa ayrıca o parçacığın ulaştığı en iyi durumu tutan bir \(RCR\) bellek matrisi atanır. Kodlanmış parçacıklar işlem sürelerine göre genişletildiğinde \(res\in\mathbb{R}^{1\times T_{\max}}\) biçiminde bir talep dizisi elde edilir. Kaynak, bu dizinin zamansal varyansına dayalı PSO uygunluk fonksiyonunu şu biçimde verir:
\[ f_{res}= \frac{ \sum_{i=0}^{T_{\max}-1} \left( res[i]- \frac{\sum_{i'=0}^{T_{\max}-1}res[i']}{T_{\max}} \right)^2 }{ T_{\max} }. \]
PSO parçacığının hedef konumu, küresel olarak en iyi bulunan parçacık \(RC_{best}\) ile ilgili parçacığın bellek matrisi \(RCR\) kullanılarak oluşturulur. Çalışmada öğrenme katsayıları \(c_1+c_2=1\) koşulunu sağlar ve deneylerde \(c_1=0{,}3\), \(c_2=0{,}7\) kullanılmıştır.
Hareket oranı ve kaynakta korunması gereken gösterim sorunu
Kaynak hareket oranı için Denklem (23)'ü aşağıdaki biçimde vermekte ve bunu Linearly Decreasing Weight stratejisi olarak tanımlamaktadır:
\[ r= r_{ini}- \frac{(r_{ini}-r_{end})(G_k-g)}{G_k} +r_{end}. \]
Bu denklem burada kaynakta yayımlandığı biçimiyle korunmuştur. Yazılı formülün sıradan cebirsel yorumu ile metindeki “doğrusal olarak azalan” tanım arasında açıklığa ihtiyaç vardır; bu nedenle Verianla metni formülü sessizce başka bir standart LDW formülüne dönüştürmemektedir. Benzer biçimde kaynak Şekil 1 açıklamasının bir noktasında hareket oranından söz ederken \(\gamma\) simgesini kullanmaktadır; ana yöntem anlatımında değişken \(r\)'dir.
Çift-komşuluklu tabu araması
PSO'dan elde edilen başlangıç çözümünün ardından tabu araması mevcut çözümün yakın çevresinde çalışır. Kaynak iki komşuluk tanımlar:
- Swap komşuluğu: seçilmiş makinelerin sıralamasını değiştirerek yeni adaylar üretir.
- Replacement komşuluğu: seçilmiş bir makineyi kullanılabilir fakat seçilmemiş başka bir makineyle değiştirerek yeni adaylar üretir.
Kaynakta komşuluk elemanı sayıları:
\[ sn=\frac{1}{2}\left(N_{i,k}^{2}-N_{i,k}\right) =\frac{N_{i,k}(N_{i,k}-1)}{2} \]
ve
\[ rn=(NT_{i,k}-N_{i,k})N_{i,k} \]
şeklinde verilmektedir. İlk ifade seçilmiş \(N_{i,k}\) makinenin ikili yer değiştirme kombinasyonlarının sayısını, ikinci ifade ise seçilmiş makine ile seçilmemiş fakat kullanılabilir makine arasındaki değiştirme seçeneklerinin sayısını matematiksel olarak temsil eder.
Kaynak içi gösterim notu: Metindeki “swap neighborhood is valid if \(N_{i,k}<NT_{i,k}\)” ve “replacement neighborhood is valid if \(N_{i,k}\geq2\)” ifadeleri, Denklem (25)–(26) ile kaynak Şekil 2'deki operatörlerin görsel anlamlarıyla isim düzeyinde uyuşmuyor görünmektedir. Denklem (25)'teki swap sayısının pozitif olabilmesi için en az iki seçilmiş makine gerekirken, Denklem (26)'daki replacement işlemi seçilmemiş alternatif bulunmasını gerektirir. Bu nedenle burada kaynak formülleri korunmuş, metindeki koşullar sessizce “düzeltilmiş” kabul edilmemiştir.
Kaynak, DNTS tarama miktarı için ayrıca:
\[ d=mn\times\left\lceil\frac{T_{\max}}{sn}\right\rceil \]
ifadesini verir. Tabu listesi daha önce gerçekleştirilen değişimlerin belirli süre boyunca tekrar seçilmesini önler; her iterasyonda tabu olmayan komşular arasından uygunluğu en iyi aday seçilir ve mevcut küresel en iyi çözüm iyileştirilebiliyorsa güncellenir.
Modelin temel varsayımları
Matematiksel modelin yorumlanmasında aşağıdaki varsayımlar kritik önemdedir:
- İşlerde blocking veya makine setup süresi dikkate alınmaz.
- Bir makine bir işe atandıktan sonra ilgili işlem kesintiye uğramaz.
- Her makine bir zaman biriminde yalnız bir işi işler.
- Makinenin işi alma ve başka noktaya aktarma süresi ihmal edilir.
- Aynı iş grubundaki işler aynı işlem şemasını kullanır.
- Aynı şema içinde rota değişse de toplam işlem süresinin aynı kaldığı kabul edilir.
- Bir işin sonraki aşaması ancak önceki aşaması tamamlandıktan sonra başlar.
- Bir aşamada seçilmiş birden fazla makinenin kullanım sırası serbesttir.
- Modelde her makine türünün miktarı için sabit bir üst kapasite verilmez; ihtiyaç \(RN\) üzerinden hesaplanır.
Bu varsayımlar modelin hesaplanabilirliğini ve araştırma sorusunu netleştirir; aynı zamanda gerçek bir üretim sistemine aktarılırken setup, taşıma, vardiya, bakım, fiziksel makine kapasitesi ve başka yerel kısıtların ayrıca modellenmesi gerekebileceğini gösterir.
Çalışmanın Yöntemi ve Bulguları
Matematiksel kısıt sistemi
Ana optimizasyon problemi kaynakta:
\[ F=\min f(RN) \]
şeklinde tanımlanır. Kalan denklemler uygulanabilir bir çizelgenin hangi koşulları sağlaması gerektiğini belirler.
| Denklem | Kaynak matematiksel yapısı | Bilimsel rolü |
|---|---|---|
| (8) | \(bt_{i,j,1}=1\) | Bütün işlerin ilk aşamaya aynı başlangıç anından girdiği varsayımını sabitler. |
| (9) | \(0\le RM_{x,y}\le mn\) | Makine atama matrisinin geçerli makine indeksi aralığında kalmasını sağlar. |
| (10) | \(\sum_{l=1}^{mn}\mu_{i,j,t,l}=1\) | Bir işin herhangi bir anda yalnız bir makinede işlenmesini sağlar. |
| (11) | \(bt_{i,j,k+1}=et_{i,j,k}+1\) | Aşamaların ardışık yürütülmesini zorunlu kılar. |
| (12) | \(NT_{i,k}\ge N_{i,k}\ge1\) | Gerekli makine sayısının kullanılabilir makine seçeneklerini aşmasını engeller. |
| (13) | \(pt_{i,k,l}=pt_{i,k,l'}\), \(et_{i,j,k}=bt_{i,j,k}+pt_{i,k,l}N_{i,k}\) | Kaynağın aynı şema içinde rota değişse bile işlem süresini eşdeğer kabul eden varsayımını kodlar. |
| (14) | \(T_{\max}\) en uzun toplam iş süresine eşittir. | Çizelgeleme ufkunun en uzun süren iş tarafından belirlenmesini sağlar. |
| (15) | \(0\le RN_{x,y}\le h\) | Makine talep miktarının negatif olmamasını ve büyük bir pozitif sınır içinde ifade edilmesini sağlar. |
| (16) | \(\sum_{t=bt_{i,j,k}}^{et_{i,j,k}}\mu_{i,j,t,l}=pt_{i,k,l}\) | Seçilmiş makinenin gerekli işlem süresi boyunca kullanılmasını bağlar. |
| (17) | \(\sum_{t'=t}^{t+pt_{i,k,l}-1}\mu_{i,j,t',l}=pt_{i,k,l}\) | İşin seçilmiş bir makinedeki işleminin kesintisiz bir zaman bloğunda gerçekleşmesini sağlar. |
Deney düzeneği
Deneyler 72 çekirdekli Intel Xeon Gold 6254 işlemci ve 256 GB bellek içeren bir platformda gerçekleştirilmiştir. TS-PSO için parçacık popülasyonu 30, öğrenme ağırlıkları \(c_1=0{,}3\) ve \(c_2=0{,}7\), ilk hareket oranı \(r=0{,}9\) olarak ayarlanmıştır.
| Algoritma | Temel deney parametreleri |
|---|---|
| TS-PSO | 30 parçacık; \(c_1=0{,}3\); \(c_2=0{,}7\); başlangıç \(r=0{,}9\) |
| SA | \(T_0=100\); soğuma katsayısı \(\alpha=0{,}95\); \(T_{end}=0{,}001\); rastgele pertürbasyon komşuluğu |
| ACO | 50 karınca; \(\rho=0{,}1\); \(\alpha=1{,}0\); \(\beta=2{,}0\); \(\tau_0=0{,}1\) |
| GA | Popülasyon 100; rulet tekeri seçimi; \(P_c=0{,}8\); \(P_m=0{,}01\) |
12.000 örneklik benchmark nasıl oluşturuldu?
Benchmark toplam 120 problem ölçeğinden oluşur ve her ölçek için 100 örnek üretilerek toplam 12.000 MS-FJSP örneğine ulaşılır. Ölçek parametreleri:
| Parametre | Değerler |
|---|---|
| Makine türü sayısı \(M\) | \(\{15,30\}\) |
| İş grubu sayısı \(G\) | \(\{10,25\}\) |
| İş sayısı \(J\) | \(\{100,200,300,400,500\}\) |
| Ortalama uyumlu makine sayısı \(\bar M\) | \(\{3,5,7,9,12,15\}\) |
| Aşama sayısı \(K\) | \(\{2,3,4,5\}\) kümesinden rastgele |
| İşlem süresi \(P\) | \(U(2,10)\) düzgün dağılımından rastgele |
Karşılaştırmalar 30 bağımsız çalıştırma ve farklı rastgele başlangıçlar kullanılarak yapılmıştır. Kaynak performans farkını:
\[ Gap=\frac{v-v_{our}}{v_{our}}\times100\% \]
şeklinde hesaplar. Burada \(v\) karşılaştırılan algoritmanın, \(v_{our}\) ise TS-PSO'nun amaç değeri olduğundan pozitif Gap değeri karşılaştırılan yöntemin TS-PSO'dan daha yüksek, yani bu minimizasyon problemi açısından daha kötü amaç değeri ürettiğini ifade eder.
Üretilmiş veri setindeki ana sonuçlar
Kaynak Tablo 2'nin ana sonucu tutarlıdır: incelenen bütün \(M\), \(G\) ve \(J\) kombinasyonlarının toplulaştırılmış sonuçlarında TS-PSO en düşük varyans değerini vermektedir. Aşağıdaki tablo, kaynak verilerinden farklı ölçekleri temsil edecek biçimde seçilmiş örnekleri Verianla düzeninde gösterir.
| Ölçek \(M,G,J\) | TS-PSO Var | TS-PSO süre (s) | SA Gap | ACO Gap | GA Gap |
|---|---|---|---|---|---|
| 15, 10, 100 | 1090,72 | 630,41 | %1,71 | %6,42 | %4,55 |
| 15, 25, 200 | 1833,28 | 690,26 | %1,12 | %4,37 | %2,96 |
| 15, 25, 500 | 3961,42 | 762,49 | %0,75 | %2,16 | %2,26 |
| 30, 10, 300 | 1462,92 | 835,82 | %1,04 | %4,87 | %3,79 |
| 30, 25, 400 | 3062,53 | 865,88 | %0,42 | %2,92 | %2,31 |
| 30, 25, 500 | 4162,57 | 899,62 | %0,90 | %2,20 | %2,21 |
Kaynağın ölçekler üzerinden yaptığı genel hesaplamada SA, TS-PSO'ya en yakın temel yöntemdir ve ortalama fark yaklaşık %1,21'dir. GA için ortalama fark yaklaşık %3,22, ACO için yaklaşık %4,04 olarak verilmektedir. Bu sonuç, çalışmanın hedeflediği makine talep varyansı açısından TS-PSO'nun karşılaştırılan üç meta-sezgisel yönteme göre daha iyi sonuçlar ürettiğini desteklemektedir.
Kararlılık ve yakınsama
Kaynak Şekil 3'te sekiz farklı problem ölçeği için 30 bağımsız çalıştırmanın kutu grafikleri verilmektedir. Görsel karşılaştırmada TS-PSO dağılımları her örnekte daha düşük amaç fonksiyonu bölgesinde yoğunlaşmaktadır. Bu sonuç yalnız tek bir rastgele başlangıcın başarılı olmasından ziyade, tekrarlı çalıştırmalarda da benzer performans eğiliminin elde edildiğini göstermek için kullanılmıştır.
Yakınsama deneyinde \(15\times10\) ölçeğindeki MS-FJSP örnekleri 1000 iterasyon boyunca izlenmiştir. Kaynak, 100. iterasyonda TS-PSO amaç değerini 1405,78 olarak raporlamaktadır. 500. iterasyon sonunda TS-PSO çözüm değerinin SA, ACO ve GA'ya göre sırasıyla %18,14, %27,22 ve %23,53 daha düşük olduğu belirtilmektedir. Yazarların yorumuna göre ana iyileştirmenin büyük kısmı yaklaşık ilk 500 iterasyonda gerçekleşmekte ve 800–1000 iterasyon arasında eğri belirgin biçimde yataylaşmaktadır.
Hesaplama maliyeti
Kaynak TS-PSO'nun genel zaman karmaşıklığını:
\[ O(G\times N\times S) \]
olarak ifade eder; burada bu bağlamdaki \(G\) maksimum iterasyon sayısını, \(N\) parçacık popülasyonunu ve \(S\) problem ölçeğini temsil etmektedir. Bu karmaşıklık gösterimindeki \(G\), MS-FJSP veri kümesi açıklamasında kullanılan “iş grubu sayısı” sembolüyle aynı harfin farklı anlamda kullanılması nedeniyle bağlama göre okunmalıdır.
Deneysel süreler problem ölçeği büyüdükçe bütün yöntemlerde artmıştır. Kaynak, küçük ölçekten büyük ölçeğe hesaplama süresi artışını TS-PSO için %42,32, GA için %44,28, ACO için %43,53 ve SA için %39,17 olarak bildirir. TS-PSO bazı ölçeklerde rakiplerinden biraz daha uzun çalışmasına rağmen süreler aynı büyüklük mertebesinde kalmıştır. Dolayısıyla kaynak sonuçları bir “en hızlı algoritma” iddiasından çok, ek süre karşılığında daha düşük amaç fonksiyonu ve daha güçlü yakınsama elde edildiği yönündedir.
Ablasyon çalışması: PSO ve tabu aramasının ayrı katkısı
TS-PSO'nun kazancının yalnız bileşenlerden birinden kaynaklanıp kaynaklanmadığını görmek için araştırmacılar iki varyant kullanmıştır: w/o TS tabu araması çıkarılmış sürüm, w/o PSO ise PSO çıkarılmış sürümdür.
| \(M\) | \(G\) | \(J\) | TS-PSO | w/o TS | w/o PSO |
|---|---|---|---|---|---|
| 15 | 10 | 100 | 1090,26 | 1145,32 | 1102,18 |
| 15 | 25 | 500 | 3961,01 | 4032,78 | 3984,26 |
| 30 | 10 | 300 | 1462,69 | 1523,76 | 1476,29 |
| 30 | 25 | 500 | 4162,21 | 4258,73 | 4187,96 |
Her iki bileşeni birlikte kullanan TS-PSO bu örneklerin tamamında en düşük değeri üretmiştir. Tabu araması çıkarıldığında performans kaybının PSO çıkarılmasına göre daha büyük olması, kaynak yazarlarının çift-komşuluklu tabu aramasını nihai yerel iyileştirmenin kritik bileşeni olarak yorumlamasına temel oluşturmaktadır. PSO ise tabu aramasına daha kaliteli bir başlangıç/komşuluk yapısı sağlayarak aramanın yönlendirilmesine katkıda bulunmaktadır.
Hastane personel çizelgelemesi nasıl MS-FJSP'ye dönüştürüldü?
Çalışmanın gerçek-dünya örneği, First Bethune Hospital of Jilin University'nin yeni işe alınan personelin bölümlere atanmasına ilişkin 2024 çizelgeleme problemidir. Model eşlemesi şöyledir:
| Gerçek problem öğesi | MS-FJSP karşılığı |
|---|---|
| Hastane bölümleri | Makine türleri |
| Personelin mesleki arka planları | İş grupları |
| Personel | İşler |
| Bir mesleki arka planla uyumlu bölümler | Uyumlu makine seçenekleri |
Kaynak bu problem örneğini \(M=72\), \(G=26\), \(J=491\) ve \(\bar M=13\) olarak tanımlar ve çözüm uzayını \(1\times10^{5194}\) olarak verir.
| İterasyon | Metrik | TS-PSO | SA | ACO | GA |
|---|---|---|---|---|---|
| 100 | Var | 2010,08 | 2052,12 | 2114,98 | 2087,49 |
| 100 | Gap | — | %2,09 | %5,22 | %3,85 |
| 100 | Süre (s) | 853,12 | 846,24 | 847,12 | 846,49 |
| 1000 | Var | 1215,27 | 1426,53 | 1758,21 | 1533,29 |
| 1000 | Gap | — | %17,38 | %44,67 | %26,17 |
| 1000 | Süre (s) | 8937,41 | 8695,87 | 8818,43 | 8734,25 |
100 iterasyonda TS-PSO diğer yöntemlerden yalnız sınırlı miktarda daha düşük amaç değerleri üretirken, 1000 iterasyonda fark belirgin biçimde açılmaktadır. Buna karşılık TS-PSO'nun hesaplama süresi de biraz daha yüksektir. Kaynağın değerlendirmesine göre bu sonuç, çok büyük çözüm uzayında çift-komşuluklu yerel aramanın daha fazla iterasyon verildiğinde avantajını artırdığını göstermektedir.
Çalışmanın desteklediği sonuçlar
Çalışma, tanımlanan MS-FJSP matematiksel modeli altında TS-PSO'nun araştırmacıların oluşturduğu 12.000 benchmark örneğinde SA, ACO ve GA'dan daha düşük makine-talep varyansı değerleri elde ettiğini desteklemektedir. Ablasyon sonuçları PSO ve tabu aramasının birlikte kullanılmasının tek bileşenli varyantlardan daha iyi sonuç verdiğini gösterir. Hastane verisinden oluşturulan örnek de MS-FJSP'nin üretim dışındaki karmaşık kaynak-atama problemlerine matematiksel olarak uyarlanabileceğini göstermektedir.
Çalışmanın desteklemediği sonuçlar
Bu çalışma TS-PSO'nun bütün FJSP/MS-FJSP örneklerinde küresel optimumu garanti ettiğini kanıtlamaz. Benchmark sonuçları incelenen problem üretim prosedürü, parametre aralıkları, karşılaştırma yöntemleri ve donanım koşullarına bağlıdır. Hastane örneği gerçek veriden modellenmiş bir optimizasyon örneğidir; önerilen çizelgenin gerçek hastane operasyonunda uygulanması ve klinik, insan kaynakları veya uzun dönem operasyon sonuçlarının ölçülmesi bu çalışmanın deney tasarımının parçası değildir.
Ayrıca model setup sürelerini, taşıma sürelerini, kesintileri, sınırlı fiziksel makine stoğunu ve farklı rotaların işlem sürelerini değiştirebilmesini ana formülasyonda dikkate almamaktadır. Bu nedenle farklı bir üretim sistemi veya kurumsal çizelgeleme ortamında yöntem kullanılacaksa yerel süreç kısıtlarının modele ayrıca eklenmesi ve performansın yeniden doğrulanması gerekir.
Kaynakta bulunan Denklem (23), DNTS komşuluk koşullarının adlandırılması ve Algorithm 1'deki bazı değişken seçimleri uygulamaya dönük yeniden üretimde ayrıca kontrol edilmelidir. Bu noktalar, çalışma sonuçlarını otomatik olarak geçersiz kılan hükümler olarak değil, kaynağın yayımlanmış gösteriminde dikkat gerektiren yeniden üretilebilirlik ayrıntıları olarak değerlendirilmelidir.
Kaynak ve Yöntem Notu
Özgün çalışma: Iterated Tabu Search Enhanced Particle Swarm Optimization for the Multi-Stage Flexible Job Shop Scheduling Problem
Yazarlar: Chunyang Jiang; Hengyu Song; Baotong Ma; Shiwen Wang; Chulei Zhang; Peng Zhao; You Zhou.
Sorumlu yazarlar: Chunyang Jiang ve You Zhou.
Kurumlar: College of Computer Science and Technology, Jilin University; School of Artificial Intelligence, Jilin University; The First Hospital of Jilin University; Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Çin.
Dergi: AI.
Yayınevi: MDPI.
Yayın bilgisi: 2026, cilt 7, sayı 5, makale 165.
Yayın tarihi: 9 Mayıs 2026. Kaynakta gönderim 1 Nisan 2026, revizyon 23 Nisan 2026 ve kabul 24 Nisan 2026 olarak belirtilmiştir.
DOI: 10.3390/ai7050165
Kaynak türü ve hakemlik: Hakemli bilimsel dergide yayımlanmış araştırma makalesi.
Lisans: Creative Commons Attribution 4.0 International (CC BY 4.0). Telif yazarlar tarafından korunmakta, MDPI lisans sahibi/yayıncı olarak belirtilmektedir.
Finansman: Jilin Provincial Department of Science and Technology Project, Grant 20230201083GX.
Veri erişilebilirliği: Yazarlar, çalışmada üretilen veya analiz edilen verilerin makalede bulunduğunu ve ek harici veriye ihtiyaç olmadığını beyan etmektedir.
Çıkar çatışması: Yazarlar çıkar çatışması olmadığını bildirmiştir.
Etik beyanlar: Institutional Review Board ve informed consent alanları kaynakta “not applicable” olarak belirtilmiştir.
Yazar katkıları: Kavramsallaştırma Chunyang Jiang ve Peng Zhao; metodoloji Chunyang Jiang; yazılım Chunyang Jiang ve Peng Zhao; doğrulama, formal analiz, araştırma ve kaynaklar Chunyang Jiang; veri kürasyonu Chunyang Jiang ve Hengyu Song; ilk taslak Chunyang Jiang; gözden geçirme ve düzenleme Chunyang Jiang; görselleştirme Chunyang Jiang ve Shiwen Wang; denetim Chunyang Jiang ve Baotong Ma; proje yönetimi Chunyang Jiang ve Chulei Zhang; finansman edinimi Chunyang Jiang ve You Zhou tarafından gerçekleştirilmiştir.
Verianla yöntem notu: Bu içerik kaynak makalenin cümle cümle çevirisi veya paragraf-paragraf yeniden yazımı değildir. Matematiksel model, yöntem adımları, deney parametreleri, sayısal sonuçlar, görsellerin bilimsel mesajı ve sınırlılıklar kaynak çalışmadan çıkarılmış; anlatım Verianla için bağımsız bir öğretim yapısında yeniden kurulmuştur. Kaynak şekillerinin ekran görüntüleri veya özgün grafik düzenleri kullanılmamıştır.
Yorum sınırı: TS-PSO meta-sezgisel bir optimizasyon yöntemidir. Çalışmanın raporladığı daha iyi amaç değerleri, incelenen benchmarklar ve modellenmiş gerçek-dünya örneği için hesaplamalı performans kanıtıdır; bütün problem örneklerinde matematiksel olarak kanıtlanmış küresel optimum garantisi değildir. Kaynakta bulunan bazı formül/pseudocode gösterimlerinin bağımsız yeniden uygulamada açıklığa kavuşturulması gerekebilir.
Bir yorum bırakın
E-posta adresiniz yayınlanmayacaktır. Gerekli alanlar * ile işaretlenmiştir