Çoxmərhələli Çevik İş Sexinin Cədvəlləşdirilməsi Problemi (Multi-Stage Flexible Job Shop Scheduling Problem, MS-FJSP), işləri istehsal mərhələlərinə bölən, bir mərhələdə bir neçə uyğun maşının seçilməsinə və seçilmiş maşınların emal ardıcıllığının dəyişdirilməsinə imkan verən kombinator cədvəlləşdirmə modelidir. Tədqiqat klassik çevik iş sexinin cədvəlləşdirilməsindəki tək maşın seçimi və daha sərt əməliyyat marşrutu fərziyyələrini genişləndirir; həll üçün hissəcik sürüsü optimallaşdırmasını iki qonşuluqlu tabu axtarışı ilə birləşdirən TS-PSO alqoritmini təklif edir. Modelin əsas optimallaşdırma məqsədi birbaşa istehsalın tamamlanma müddətini minimuma endirmək deyil, müəyyən edilmiş cədvəlləşdirmə üfüqü boyunca hər maşın növünə olan tələbin zaman üzrə dispersiyasını azaltmaqla tələb olunan maşın sayının daha balanslı paylanmasını təmin etməkdir.
TS-PSO-da hissəcik sürüsü optimallaşdırması (PSO) geniş həll fəzasında ilkin həll strukturunun qurulması və maşın tələbinin təxmini paylanmasının müəyyənləşdirilməsi üçün istifadə olunur. Daha sonra tabu axtarışı MS-FJSP-nin maşın seçimi və ardıcıllıq çevikliyinə uyğun qurulmuş iki ayrı qonşuluqda lokal yaxşılaşdırma aparır. Tədqiqatçılar metodu 120 müxtəlif problem miqyasına paylanmış ümumilikdə 12.000 yaradılmış MS-FJSP nümunəsi üzərində Simulated Annealing (SA), Ant Colony Optimization (ACO) və Genetic Algorithm (GA) ilə müqayisə etmiş, həmçinin alqoritmin komponentlərini ablasiya təcrübələri ilə araşdırmışlar.
Yaradılmış problem nümunələrində daha aşağı məqsəd funksiyası qiymətinin daha balanslı maşın tələbi demək olduğu qiymətləndirmədə TS-PSO bütün əsas müqayisə miqyaslarında üç baza metodundan daha aşağı məqsəd funksiyası qiymətləri əldə etmişdir. Mənbənin ümumi hesablamasına görə SA-nın TS-PSO ilə orta fərqi təxminən %1,21, GA-nın təxminən %3,22 və ACO-nun təxminən %4,04-dür. Bu keyfiyyət artımı bəzi nümunələrdə bir qədər daha yüksək hesablama müddəti hesabına əldə edilmişdir; müddətlər ümumilikdə müqayisə olunan alqoritmlərlə eyni böyüklük tərtibində qalmışdır.
Real dünya ilə əlaqə üçün First Bethune Hospital of Jilin University-nin 2024-cü il üzrə personal yerləşdirmə problemi MS-FJSP kimi modelləşdirilmişdir. Bu nümunədə 72 şöbə maşın növlərini, 26 peşəkar hazırlıq iş qruplarını, 491 əməkdaş işləri və orta hesabla 13 uyğun şöbə maşın uyğunluğunu təmsil edir. Mənbə bu model üçün həll fəzasını \(1\times10^{5194}\) kimi bildirir. TS-PSO burada da müqayisə olunan metodlardan daha aşağı dispersiya qiymətləri yaratmışdır. Bununla belə, nəticələr alqoritmik modelləşdirmə və hesablama təcrübəsinin doğrulanmasıdır; real müəssisədə cədvəlin tətbiqinin əməliyyat nəticələrini ölçən sahə təcrübəsi deyil.
MS-FJSP nədir?
MS-FJSP, işlərin mərhələli emal marşrutlarına malik olduğu və hər mərhələdə tələb olunan maşın növlərinin həm seçiminin, həm də ardıcıllığının müəyyən məhdudiyyətlər daxilində çevik saxlandığı çevik iş sexinin cədvəlləşdirilməsi problemidir. Klassik FJSP-dən əsas fərqi, bir əməliyyatın yalnız bir uyğun maşına təyin olunması məcburiyyətini yumşaldaraq eyni mərhələdə bir neçə maşın növündən istifadə edilməsinə və bu maşınların emal ardıcıllığının dəyişdirilməsinə imkan verməsidir.
Klassik FJSP-dən hansı baxımdan fərqlənir?
Klassik Flexible Job Shop Scheduling Problem (FJSP) iki əsas qərarı birlikdə nəzərdən keçirir: işlərin hansı ardıcıllıqla yerinə yetiriləcəyi və hər əməliyyatın hansı uyğun maşında həyata keçiriləcəyi. Araşdırılan tədqiqatda bu struktur iki istiqamətdə genişləndirilir. Birincisi, əməliyyatlar istehsal mərhələləri şəklində təşkil olunur və növbəti mərhələyə yalnız əvvəlki mərhələ tamamlandıqdan sonra keçmək mümkündür. İkincisi, bir mərhələdə tək bir maşın seçmək əvəzinə tələb olunan sayda maşın növü seçilə bilər və seçilmiş maşınların öz aralarındakı emal ardıcıllığı dəyişdirilə bilər.
Model həmçinin işləri emal marşrutlarına görə qruplaşdırır. Eyni iş qrupundakı işlər eyni emal sxemini izləyir. Bu qruplaşdırma Flexible Group Shop Scheduling Problem-də oxşar marşrutları bir araya gətirərək quraşdırma müddətini azaltmaq ideyası ilə eyni deyil. MS-FJSP-də qruplaşdırmanın məqsədi eyni iş tipinin təkrarlanan istehsalını və eyni sxem daxilində çoxsaylı işlərin mövcudluğunu modelləşdirməkdir.
Mərhələ anlayışı niyə vacibdir?
Mərhələli struktur istehsal və ya cədvəlləşdirmə prosesindəki seçimləri tək xətti maşın marşrutuna sıxışdırmaq əvəzinə qərarları ardıcıl, lakin daxilən çevik emal bloklarına ayırır. \(i\) iş qrupu üçün mərhələ sayı \(kn_i\) ilə göstərilir. \(k\) nömrəli mərhələdə istifadə oluna biləcək maşın növlərinin çoxluğu \(LM_{i,k}\), mövcud maşın növlərinin sayı \(NT_{i,k}\), həqiqətən tələb olunan maşın növlərinin sayı isə \(N_{i,k}\) ilə təmsil olunur.
Bu fərqləndirmə həll fəzasını sürətlə böyüdür. Bir mərhələdə yalnız hansı maşınların seçiləcəyi deyil, seçilmiş maşınların hansı ardıcıllıqla istifadə ediləcəyi də qərara daxildir. Buna görə problem maşın seçimləri və mərhələ sayı artdıqca klassik tək-təyinatlı strukturlarla müqayisədə daha böyük kombinator axtarış fəzası yaradır.
Modeldə zaman və maşın tələbinin təsviri
Tədqiqat iki əsas matrisdən istifadə edir. \(RM\) maşın təyinat matrisidir və iş × zaman strukturunda hansı işin hansı zaman addımında hansı maşın növündə emal edildiyini göstərir. \(RN\) isə maşın tələbi matrisidir; maşın növü × zaman strukturunda hər zaman addımında müəyyən maşın növündən neçə ədəd tələb olunduğunu göstərir.
| Simvol | Mənası |
|---|---|
| \(jn\) | Ümumi iş sayı |
| \(J_{i,j}\) | \(i\)-ci iş qrupundakı \(j\)-ci iş |
| \(gn\) | Ümumi iş qrupu sayı |
| \(gn_i\) | \(i\)-ci iş qrupundakı işlərin sayı |
| \(kn_i\) | \(i\)-ci iş qrupunun emal mərhələlərinin sayı |
| \(mn\) | Ümumi maşın növü sayı |
| \(M_l\) | \(l\)-ci maşın növü |
| \(M_0\) | Bütün əməliyyatların tamamlandığını bildirən virtual maşın |
| \(T_{\max}\) | Ümumi cədvəlləşdirmə müddəti / zaman üfüqü |
| \(pt_{i,k,l}\) | \(i\)-ci qrupun \(k\)-cı mərhələsinin \(M_l\) üzərində emal müddəti |
| \(bt_{i,j,k}\) | \(J_{i,j}\) işinin \(k\)-cı mərhələsinin başlanğıc zamanı |
| \(et_{i,j,k}\) | \(J_{i,j}\) işinin \(k\)-cı mərhələsinin tamamlanma zamanı |
| \(LM_{i,k}\) | \(i\)-ci qrupun \(k\)-cı mərhələsində istifadə oluna biləcək maşın indeksləri |
| \(NM_{i,j,k}\) | \(J_{i,j}\) işinin \(k\)-cı mərhələsində həqiqətən istifadə olunan maşın indeksləri |
| \(O_{i,k,n}\) | \(i\)-ci qrupun \(n\) maşın tələb edən \(k\)-cı mərhələ əməliyyatı |
| \(N_{i,k}\) | \(i\)-ci qrupun \(k\)-cı mərhələsində tələb olunan maşın növlərinin sayı |
| \(NT_{i,k}\) | \(i\)-ci qrupun \(k\)-cı mərhələsində mövcud maşın növlərinin sayı |
| \(RM\) | İş × zaman maşın təyinat matrisi |
| \(RN\) | Maşın növü × zaman maşın tələbi matrisi |
| \(\mu_{i,j,t,l}\) | \(J_{i,j}\) işi \(t\) anında \(M_l\) üzərində emal olunursa 1, əks halda 0 |
| \(\phi_{i,j,k,l}\) | \(J_{i,j}\) işi \(k\)-cı mərhələdə \(M_l\)-dən istifadə edirsə 1, əks halda 0 |
| \(\xi_{i,k,l}\) | \(i\)-ci qrupun \(k\)-cı mərhələsi \(M_l\)-dən istifadə edə bilirsə 1, əks halda 0 |
Məqsəd funksiyası nəyi optimallaşdırır?
Bu tədqiqatda MS-FJSP-nin məqsəd funksiyası hər maşın növünə zaman üzrə olan tələb miqdarının dispersiyalarını toplayır və bu cəmi minimuma endirir; buna görə daha aşağı qiymət eyni cədvəlləşdirmə üfüqü daxilində maşın ehtiyacının zamana daha balanslı paylanması deməkdir. Bu məqam vacibdir, çünki tədqiqat klassik FJSP araşdırmalarında tez-tez rast gəlinən yalnız makespan minimallaşdırılmasından fərqli olaraq maşın sayının bölüşdürülməsinin hamarlığını birbaşa optimallaşdırma məqsədinə çevirir.
Hər maşın növü üçün zaman ortalamasından kənarlaşmaların kvadratına əsaslanan əsas məqsəd funksiyası mənbədə belə müəyyən edilmişdir:
\[ 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\)-ci maşın növünə \(y\)-ci zaman addımındakı tələbi; mötərizə daxilindəki ikinci termin isə həmin maşın növünün bütün cədvəlləşdirmə üfüqündəki orta tələbini göstərir. Beləliklə, funksiya tələb əyrisinin orta ətrafında yayılmasını cərimələndirir.
Həll fəzası niyə bu qədər sürətlə böyüyür?
\(i\)-ci iş qrupunun \(k\)-cı mərhələsində \(NT_{i,k}\) mövcud maşın növü arasından ardıcıllıqla \(N_{i,k}\) maşın seçilə bilirsə, mənbə mümkün seçim və ardıcıllıq sayını belə müəyyən edir:
\[ p_{i,k}=\frac{NT_{i,k}!}{(NT_{i,k}-N_{i,k})!}. \]
Bir işin bütün mərhələlərindəki marşrutların sayı:
\[ P_i=\prod_{k=1}^{kn_i}p_{i,k}. \]
Eyni qrupdakı işlər fərqləndirilmirsə, ümumi cədvəlləşdirmə ehtimalı mənbədə:
\[ P= \prod_{i=1}^{gn} \frac{(P_i+gn_i-1)!}{gn_i!\,(P_i-1)!} \]
kimi; işlər fərqləndirilirsə isə:
\[ P= \prod_{i=1}^{gn}P_i^{gn_i} \]
kimi verilir. Bu ifadələr maşın sayı və mərhələ seçimləri artdıqca bütün həlləri kobud qüvvə ilə yoxlamağın niyə praktik olmaqdan çıxdığını göstərir.
TS-PSO niyə iki axtarış mexanizmini birləşdirir?
TS-PSO, PSO-nun geniş həll fəzasında sürətlə yaxşı ilkin struktur qurmaq xüsusiyyətini tabu axtarışının mövcud yaxşı həllin yaxınlığında ətraflı lokal axtarış aparmaq qabiliyyəti ilə birləşdirir. Tədqiqatdakı iş bölgüsü təxminən “PSO ilə ilkin strukturu və tələb paylanmasını qiymətləndir, sonra MS-FJSP-yə xas iki qonşuluqda tabu axtarışı ilə yaxşılaşdır” şəklindədir.
PSO qatı: kodlaşdırma, həll və ilkin struktur
PSO mərhələsində hər maşın növü üçün bir DM məlumat matrisi yaradılır. Matrisin sətirləri müvafiq maşın növünün iştirak etdiyi emal mərhələlərini, sütunları isə iş qrupu ölçüsü, emal müddəti və müvafiq zaman intervalı kimi məlumatları daşıyır. Bir hissəcik \(RC\in\mathbb{R}^{cn\times T_{\max}}\) matrisi ilə təmsil olunur. Başlanğıcda müvafiq zaman intervalına cəmi həmin qrupdakı işlərin sayına bərabər olacaq şəkildə mənfi olmayan tam ədədlər paylanır.
Hər hissəciyə həmçinin həmin hissəciyin çatdığı ən yaxşı vəziyyəti saxlayan \(RCR\) yaddaş matrisi təyin olunur. Kodlaşdırılmış hissəciklər emal müddətlərinə görə genişləndirildikdə \(res\in\mathbb{R}^{1\times T_{\max}}\) formasında tələb sırası əldə edilir. Mənbə bu sıranın zaman üzrə dispersiyasına əsaslanan PSO uyğunluq funksiyasını belə 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 hissəciyinin hədəf mövqeyi qlobal olaraq tapılmış ən yaxşı hissəcik \(RC_{best}\) və müvafiq hissəciyin yaddaş matrisi \(RCR\) istifadə olunmaqla qurulur. Tədqiqatda öyrənmə əmsalları \(c_1+c_2=1\) şərtini ödəyir və təcrübələrdə \(c_1=0{,}3\), \(c_2=0{,}7\) istifadə edilmişdir.
Hərəkət nisbəti və mənbədə qorunmalı olan göstərim məsələsi
Mənbə hərəkət nisbəti üçün Tənlik (23)-ü aşağıdakı formada verir və bunu Linearly Decreasing Weight strategiyası kimi müəyyən edir:
\[ r= r_{ini}- \frac{(r_{ini}-r_{end})(G_k-g)}{G_k} +r_{end}. \]
Bu tənlik burada mənbədə dərc olunduğu formada qorunmuşdur. Yazılı formulun adi cəbri şərhi ilə mətndəki “xətti şəkildə azalan” tərif arasında aydınlaşdırmaya ehtiyac vardır; buna görə Verianla mətni formulu səssizcə başqa standart LDW formuluna çevirmir. Oxşar şəkildə, mənbə Şəkil 1-in izahının bir yerində hərəkət nisbətindən danışarkən \(\gamma\) simvolundan istifadə edir; əsas metod izahında dəyişən \(r\)-dir.
İki qonşuluqlu tabu axtarışı
PSO-dan əldə olunan ilkin həldən sonra tabu axtarışı mövcud həllin yaxın ətrafında işləyir. Mənbə iki qonşuluq müəyyən edir:
- Swap qonşuluğu: seçilmiş maşınların ardıcıllığını dəyişdirərək yeni namizədlər yaradır.
- Replacement qonşuluğu: seçilmiş bir maşını mövcud, lakin seçilməmiş başqa maşınla əvəz edərək yeni namizədlər yaradır.
Mənbədə qonşuluq elementlərinin sayı:
\[ sn=\frac{1}{2}\left(N_{i,k}^{2}-N_{i,k}\right) =\frac{N_{i,k}(N_{i,k}-1)}{2} \]
və
\[ rn=(NT_{i,k}-N_{i,k})N_{i,k} \]
şəklində verilir. Birinci ifadə seçilmiş \(N_{i,k}\) maşının ikili yer dəyişmə kombinasiyalarının sayını, ikinci ifadə isə seçilmiş maşınla seçilməmiş, lakin mövcud maşın arasındakı əvəzləmə seçimlərinin sayını riyazi olaraq göstərir.
Mənbədaxili göstərim qeydi: Mətndəki “swap neighborhood is valid if \(N_{i,k}<NT_{i,k}\)” və “replacement neighborhood is valid if \(N_{i,k}\geq2\)” ifadələri Tənlik (25)–(26) və mənbə Şəkil 2-dəki operatorların vizual mənası ilə adlandırma səviyyəsində uyğun görünmür. Tənlik (25)-dəki swap sayının müsbət ola bilməsi üçün ən azı iki seçilmiş maşın tələb olunduğu halda, Tənlik (26)-dakı replacement əməliyyatı seçilməmiş alternativin mövcudluğunu tələb edir. Buna görə burada mənbə formulları qorunmuş, mətndəki şərtlər səssizcə “düzəldilmiş” hesab edilməmişdir.
Mənbə DNTS skan miqdarı üçün əlavə olaraq:
\[ d=mn\times\left\lceil\frac{T_{\max}}{sn}\right\rceil \]
ifadəsini verir. Tabu siyahısı daha əvvəl edilmiş dəyişikliklərin müəyyən müddət ərzində yenidən seçilməsinin qarşısını alır; hər iterasiyada tabu olmayan qonşular arasından uyğunluğu ən yaxşı namizəd seçilir və mövcud qlobal ən yaxşı həll yaxşılaşdırıla bilirsə yenilənir.
Modelin əsas fərziyyələri
Riyazi modelin şərhində aşağıdakı fərziyyələr kritik əhəmiyyət daşıyır:
- İşlərdə blocking və ya maşın setup müddəti nəzərə alınmır.
- Maşın bir işə təyin edildikdən sonra müvafiq əməliyyat kəsilmir.
- Hər maşın bir zaman vahidində yalnız bir işi emal edir.
- Maşının işi qəbul etmə və başqa nöqtəyə ötürmə müddəti nəzərə alınmır.
- Eyni iş qrupundakı işlər eyni emal sxemindən istifadə edir.
- Eyni sxemdə marşrut dəyişsə də ümumi emal müddətinin eyni qaldığı qəbul edilir.
- Bir işin növbəti mərhələsi yalnız əvvəlki mərhələ tamamlandıqdan sonra başlayır.
- Bir mərhələdə seçilmiş bir neçə maşının istifadə ardıcıllığı sərbəstdir.
- Modeldə hər maşın növünün miqdarı üçün sabit yuxarı tutum verilməmişdir; ehtiyac \(RN\) üzərindən hesablanır.
Bu fərziyyələr modelin hesablanma qabiliyyətini və tədqiqat sualını aydınlaşdırır; eyni zamanda real istehsal sisteminə tətbiq edilərkən setup, daşıma, növbə, texniki xidmət, fiziki maşın tutumu və digər yerli məhdudiyyətlərin ayrıca modelləşdirilməli ola biləcəyini göstərir.
Tədqiqatın Metodu və Nəticələri
Riyazi məhdudiyyət sistemi
Əsas optimallaşdırma problemi mənbədə:
\[ F=\min f(RN) \]
şəklində müəyyən edilir. Qalan tənliklər tətbiq oluna bilən cədvəlin hansı şərtləri ödəməli olduğunu müəyyən edir.
| Tənlik | Mənbənin riyazi strukturu | Elmi rolu |
|---|---|---|
| (8) | \(bt_{i,j,1}=1\) | Bütün işlərin ilk mərhələyə eyni başlanğıc anında daxil olduğu fərziyyəsini sabitləşdirir. |
| (9) | \(0\le RM_{x,y}\le mn\) | Maşın təyinat matrisinin etibarlı maşın indeksi intervalında qalmasını təmin edir. |
| (10) | \(\sum_{l=1}^{mn}\mu_{i,j,t,l}=1\) | Bir işin istənilən anda yalnız bir maşında emal edilməsini təmin edir. |
| (11) | \(bt_{i,j,k+1}=et_{i,j,k}+1\) | Mərhələlərin ardıcıl yerinə yetirilməsini məcburi edir. |
| (12) | \(NT_{i,k}\ge N_{i,k}\ge1\) | Tələb olunan maşın sayının mövcud maşın seçimlərini aşmasının qarşısını alır. |
| (13) | \(pt_{i,k,l}=pt_{i,k,l'}\), \(et_{i,j,k}=bt_{i,j,k}+pt_{i,k,l}N_{i,k}\) | Mənbənin eyni sxemdə marşrut dəyişsə belə emal müddətini ekvivalent qəbul edən fərziyyəsini kodlaşdırır. |
| (14) | \(T_{\max}\) ən uzun ümumi iş müddətinə bərabərdir. | Cədvəlləşdirmə üfüqünün ən uzun davam edən iş tərəfindən müəyyən edilməsini təmin edir. |
| (15) | \(0\le RN_{x,y}\le h\) | Maşın tələbinin mənfi olmamasını və böyük müsbət sərhəd daxilində ifadə edilməsini təmin edir. |
| (16) | \(\sum_{t=bt_{i,j,k}}^{et_{i,j,k}}\mu_{i,j,t,l}=pt_{i,k,l}\) | Seçilmiş maşının tələb olunan emal müddəti boyunca istifadə edilməsini əlaqələndirir. |
| (17) | \(\sum_{t'=t}^{t+pt_{i,k,l}-1}\mu_{i,j,t',l}=pt_{i,k,l}\) | İşin seçilmiş maşında emalının fasiləsiz zaman bloku daxilində baş verməsini təmin edir. |
Təcrübə quruluşu
Təcrübələr 72 nüvəli Intel Xeon Gold 6254 prosessoru və 256 GB yaddaşa malik platformada aparılmışdır. TS-PSO üçün hissəcik populyasiyası 30, öyrənmə çəkiləri \(c_1=0{,}3\) və \(c_2=0{,}7\), ilkin hərəkət nisbəti \(r=0{,}9\) olaraq təyin edilmişdir.
| Alqoritm | Əsas təcrübə parametrləri |
|---|---|
| TS-PSO | 30 hissəcik; \(c_1=0{,}3\); \(c_2=0{,}7\); başlanğıc \(r=0{,}9\) |
| SA | \(T_0=100\); soyuma əmsalı \(\alpha=0{,}95\); \(T_{end}=0{,}001\); təsadüfi pertürbasiya qonşuluğu |
| ACO | 50 qarışqa; \(\rho=0{,}1\); \(\alpha=1{,}0\); \(\beta=2{,}0\); \(\tau_0=0{,}1\) |
| GA | Populyasiya 100; rulet çarxı seçimi; \(P_c=0{,}8\); \(P_m=0{,}01\) |
12.000 nümunəlik benchmark necə yaradıldı?
Benchmark ümumilikdə 120 problem miqyasından ibarətdir və hər miqyas üçün 100 nümunə yaradılmaqla cəmi 12.000 MS-FJSP nümunəsi əldə edilir. Miqyas parametrləri:
| Parametr | Qiymətlər |
|---|---|
| Maşın növlərinin sayı \(M\) | \(\{15,30\}\) |
| İş qruplarının sayı \(G\) | \(\{10,25\}\) |
| İşlərin sayı \(J\) | \(\{100,200,300,400,500\}\) |
| Orta uyğun maşın sayı \(\bar M\) | \(\{3,5,7,9,12,15\}\) |
| Mərhələ sayı \(K\) | \(\{2,3,4,5\}\) çoxluğundan təsadüfi |
| Emal müddəti \(P\) | \(U(2,10)\) bərabər paylanmasından təsadüfi |
Müqayisələr 30 müstəqil icra və müxtəlif təsadüfi başlanğıclardan istifadə edilməklə aparılmışdır. Mənbə performans fərqini:
\[ Gap=\frac{v-v_{our}}{v_{our}}\times100\% \]
şəklində hesablayır. Burada \(v\) müqayisə olunan alqoritmin, \(v_{our}\) isə TS-PSO-nun məqsəd qiyməti olduğuna görə müsbət Gap qiyməti müqayisə olunan metodun TS-PSO-dan daha yüksək, yəni bu minimallaşdırma problemi baxımından daha pis məqsəd qiyməti yaratdığını göstərir.
Yaradılmış məlumat dəstində əsas nəticələr
Mənbə Cədvəl 2-nin əsas nəticəsi ardıcıldır: araşdırılan bütün \(M\), \(G\) və \(J\) kombinasiyalarının ümumiləşdirilmiş nəticələrində TS-PSO ən aşağı dispersiya qiymətini verir. Aşağıdakı cədvəl mənbə məlumatlarından müxtəlif miqyasları təmsil edəcək şəkildə seçilmiş nümunələri Verianla formatında göstərir.
| Miqyas \(M,G,J\) | TS-PSO Var | TS-PSO müddət (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 |
Mənbənin miqyaslar üzrə ümumi hesablamasında SA, TS-PSO-ya ən yaxın baza metodudur və orta fərq təxminən %1,21-dir. GA üçün orta fərq təxminən %3,22, ACO üçün isə təxminən %4,04 olaraq verilir. Bu nəticə tədqiqatın hədəflədiyi maşın tələbi dispersiyası baxımından TS-PSO-nun müqayisə olunan üç meta-evristik metoda nisbətən daha yaxşı nəticələr yaratdığını dəstəkləyir.
Sabitlik və yaxınlaşma
Mənbə Şəkil 3-də səkkiz müxtəlif problem miqyası üçün 30 müstəqil icranın qutu qrafiklərini verir. Vizual müqayisədə TS-PSO paylanmaları hər nümunədə daha aşağı məqsəd funksiyası sahəsində cəmlənir. Bu nəticə yalnız bir təsadüfi başlanğıcın uğurlu olmasından daha çox, təkrarlanan icralarda da oxşar performans meylinin alındığını göstərmək üçün istifadə edilmişdir.
Yaxınlaşma təcrübəsində \(15\times10\) miqyasındakı MS-FJSP nümunələri 1000 iterasiya boyunca izlənmişdir. Mənbə 100. iterasiyada TS-PSO məqsəd qiymətini 1405,78 kimi bildirir. 500. iterasiyanın sonunda TS-PSO həll qiymətinin SA, ACO və GA ilə müqayisədə müvafiq olaraq %18,14, %27,22 və %23,53 daha aşağı olduğu bildirilir. Müəlliflərin şərhinə görə əsas yaxşılaşmanın böyük hissəsi təxminən ilk 500 iterasiyada baş verir və 800–1000 iterasiya arasında əyri nəzərəçarpacaq dərəcədə düzləşir.
Hesablama dəyəri
Mənbə TS-PSO-nun ümumi zaman mürəkkəbliyini:
\[ O(G\times N\times S) \]
kimi ifadə edir; burada bu kontekstdəki \(G\) maksimum iterasiya sayını, \(N\) hissəcik populyasiyasını və \(S\) problem miqyasını təmsil edir. Bu mürəkkəblik göstərimindəki \(G\), MS-FJSP məlumat dəsti izahında istifadə olunan “iş qruplarının sayı” simvolu ilə eyni hərfin fərqli mənada işlədilməsi səbəbindən kontekstə uyğun oxunmalıdır.
Təcrübi müddətlər problem miqyası böyüdükcə bütün metodlarda artmışdır. Mənbə kiçik miqyasdan böyük miqyasa hesablama müddətinin artımını TS-PSO üçün %42,32, GA üçün %44,28, ACO üçün %43,53 və SA üçün %39,17 olaraq bildirir. TS-PSO bəzi miqyaslarda rəqiblərindən bir qədər daha uzun işləsə də müddətlər eyni böyüklük tərtibində qalmışdır. Buna görə mənbə nəticələri “ən sürətli alqoritm” iddiasından daha çox, əlavə müddət hesabına daha aşağı məqsəd funksiyası və daha güclü yaxınlaşma əldə edilməsi istiqamətindədir.
Ablasiya tədqiqatı: PSO və tabu axtarışının ayrı-ayrı töhfələri
TS-PSO-nun qazancının yalnız komponentlərdən birindən qaynaqlanıb-qaynaqlanmadığını görmək üçün tədqiqatçılar iki variantdan istifadə etmişlər: w/o TS tabu axtarışı çıxarılmış versiya, w/o PSO isə PSO çıxarılmış versiyadı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 |
Hər iki komponentdən birlikdə istifadə edən TS-PSO bu nümunələrin hamısında ən aşağı qiyməti yaratmışdır. Tabu axtarışı çıxarıldıqda performans itkisinin PSO-nun çıxarılmasına nisbətən daha böyük olması mənbə müəlliflərinin iki qonşuluqlu tabu axtarışını son lokal yaxşılaşdırmanın kritik komponenti kimi şərh etməsinə əsas verir. PSO isə tabu axtarışına daha keyfiyyətli ilkin/qonşuluq strukturu verərək axtarışın istiqamətləndirilməsinə töhfə verir.
Xəstəxana personalının cədvəlləşdirilməsi MS-FJSP-yə necə çevrildi?
Tədqiqatın real dünya nümunəsi First Bethune Hospital of Jilin University-də yeni işə qəbul olunan personalın şöbələrə təyin edilməsi ilə bağlı 2024-cü il cədvəlləşdirmə problemidir. Model uyğunlaşdırması belədir:
| Real problem elementi | MS-FJSP qarşılığı |
|---|---|
| Xəstəxana şöbələri | Maşın növləri |
| Personalın peşəkar hazırlığı | İş qrupları |
| Personal | İşlər |
| Bir peşəkar hazırlıqla uyğun şöbələr | Uyğun maşın seçimləri |
Mənbə bu problem nümunəsini \(M=72\), \(G=26\), \(J=491\) və \(\bar M=13\) kimi müəyyən edir və həll fəzasını \(1\times10^{5194}\) kimi verir.
| İterasiya | 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 | Müddət (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 | Müddət (s) | 8937,41 | 8695,87 | 8818,43 | 8734,25 |
100 iterasiyada TS-PSO digər metodlardan yalnız məhdud dərəcədə daha aşağı məqsəd qiymətləri yaratsa da, 1000 iterasiyada fərq nəzərəçarpacaq şəkildə artır. Bunun müqabilində TS-PSO-nun hesablama müddəti də bir qədər yüksəkdir. Mənbənin qiymətləndirməsinə görə bu nəticə çox böyük həll fəzasında iki qonşuluqlu lokal axtarışın daha çox iterasiya verildikdə üstünlüyünü artırdığını göstərir.
Tədqiqatın dəstəklədiyi nəticələr
Tədqiqat müəyyən edilmiş MS-FJSP riyazi modeli altında TS-PSO-nun tədqiqatçıların yaratdığı 12.000 benchmark nümunəsində SA, ACO və GA-dan daha aşağı maşın-tələb dispersiyası qiymətləri əldə etdiyini dəstəkləyir. Ablasiya nəticələri PSO və tabu axtarışının birlikdə istifadəsinin tək komponentli variantlardan daha yaxşı nəticə verdiyini göstərir. Xəstəxana məlumatlarından yaradılmış nümunə də MS-FJSP-nin istehsaldan kənar mürəkkəb resurs-təyinat problemlərinə riyazi olaraq uyğunlaşdırıla biləcəyini göstərir.
Tədqiqatın dəstəkləmədiyi nəticələr
Bu tədqiqat TS-PSO-nun bütün FJSP/MS-FJSP nümunələrində qlobal optimuma zəmanət verdiyini sübut etmir. Benchmark nəticələri araşdırılan problem yaratma prosedurundan, parametr intervallarından, müqayisə metodlarından və avadanlıq şəraitindən asılıdır. Xəstəxana nümunəsi real məlumatlardan modelləşdirilmiş optimallaşdırma nümunəsidir; təklif olunan cədvəlin real xəstəxana əməliyyatında tətbiqi və klinik, insan resursları və ya uzunmüddətli əməliyyat nəticələrinin ölçülməsi bu tədqiqatın təcrübə dizaynının bir hissəsi deyil.
Bundan əlavə, model əsas formullaşdırmada setup müddətlərini, daşıma müddətlərini, fasilələri, məhdud fiziki maşın ehtiyatını və müxtəlif marşrutların emal müddətlərini dəyişə bilməsini nəzərə almır. Buna görə metod başqa istehsal sistemi və ya institusional cədvəlləşdirmə mühitində istifadə ediləcəksə, yerli proses məhdudiyyətləri modelə ayrıca əlavə edilməli və performans yenidən doğrulanmalıdır.
Mənbədəki Tənlik (23), DNTS qonşuluq şərtlərinin adlandırılması və Algorithm 1-dəki bəzi dəyişən seçimləri tətbiq yönümlü yenidən istehsalda ayrıca yoxlanmalıdır. Bu məqamlar tədqiqat nəticələrini avtomatik etibarsız edən hökmlər kimi deyil, mənbənin dərc olunmuş göstərimində diqqət tələb edən təkrar istehsal oluna bilmə detalları kimi qiymətləndirilməlidir.
Mənbə və Metod Qeydi
Orijinal tədqiqat: Iterated Tabu Search Enhanced Particle Swarm Optimization for the Multi-Stage Flexible Job Shop Scheduling Problem
Müəlliflər: Chunyang Jiang; Hengyu Song; Baotong Ma; Shiwen Wang; Chulei Zhang; Peng Zhao; You Zhou.
Məsul müəlliflər: Chunyang Jiang və You Zhou.
Qurumlar: 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.
Jurnal: AI.
Nəşriyyat: MDPI.
Nəşr məlumatı: 2026, cild 7, nömrə 5, məqalə 165.
Nəşr tarixi: 9 May 2026. Mənbədə təqdim edilmə 1 Aprel 2026, düzəliş 23 Aprel 2026 və qəbul 24 Aprel 2026 kimi göstərilmişdir.
DOI: 10.3390/ai7050165
Mənbə növü və resenziya: Resenziyalı elmi jurnalda dərc olunmuş tədqiqat məqaləsi.
Lisenziya: Creative Commons Attribution 4.0 International (CC BY 4.0). Müəllif hüquqları müəlliflərdə saxlanılır, MDPI lisenziya sahibi/nəşriyyat kimi göstərilir.
Maliyyələşdirmə: Jilin Provincial Department of Science and Technology Project, Grant 20230201083GX.
Məlumatların əlçatanlığı: Müəlliflər tədqiqatda yaradılan və ya təhlil edilən məlumatların məqalədə olduğunu və əlavə xarici məlumata ehtiyac olmadığını bəyan edirlər.
Maraqlar toqquşması: Müəlliflər maraqlar toqquşmasının olmadığını bildirmişlər.
Etik bəyanatlar: Institutional Review Board və informed consent sahələri mənbədə “not applicable” kimi göstərilmişdir.
Müəllif töhfələri: Konseptuallaşdırma Chunyang Jiang və Peng Zhao; metodologiya Chunyang Jiang; proqram təminatı Chunyang Jiang və Peng Zhao; doğrulama, formal təhlil, araşdırma və resurslar Chunyang Jiang; məlumatların kurasiyası Chunyang Jiang və Hengyu Song; ilkin layihə Chunyang Jiang; nəzərdən keçirmə və redaktə Chunyang Jiang; vizuallaşdırma Chunyang Jiang və Shiwen Wang; nəzarət Chunyang Jiang və Baotong Ma; layihənin idarə edilməsi Chunyang Jiang və Chulei Zhang; maliyyələşdirmənin əldə edilməsi Chunyang Jiang və You Zhou tərəfindən həyata keçirilmişdir.
Verianla metod qeydi: Bu məzmun mənbə məqalənin cümlə-cümlə tərcüməsi və ya abzas-abzas yenidən yazılması deyil. Riyazi model, metod addımları, təcrübə parametrləri, ədədi nəticələr, vizualların elmi mesajı və məhdudiyyətlər mənbə tədqiqatdan çıxarılmış; izah Verianla üçün müstəqil tədris strukturunda yenidən qurulmuşdur. Mənbə şəkillərinin ekran görüntülərindən və ya orijinal qrafik tərtibatlardan istifadə edilməmişdir.
Şərh sərhədi: TS-PSO meta-evristik optimallaşdırma metodudur. Tədqiqatın bildirdiyi daha yaxşı məqsəd qiymətləri araşdırılan benchmarklar və modelləşdirilmiş real dünya nümunəsi üçün hesablama performansı sübutudur; bütün problem nümunələrində riyazi olaraq sübut edilmiş qlobal optimum zəmanəti deyil. Mənbədəki bəzi formul/pseudocode göstərimlərinin müstəqil yenidən tətbiqdə aydınlaşdırılmasına ehtiyac ola bilər.
Şərh yazın
E-poçt ünvanınız yayımlanmayacaq. Məcburi sahələr * ilə işarələnib