Көп баскычтуу ийкемдүү жумуш цехин пландаштыруу маселеси (Multi-Stage Flexible Job Shop Scheduling Problem, MS-FJSP) — жумуштарды өндүрүш баскычтарына бөлгөн, бир баскычта бир нече ылайыктуу машинаны тандоого жана тандалган машиналардын иштетүү ыраатын өзгөртүүгө мүмкүндүк берген комбинатордук пландаштыруу модели. Изилдөө классикалык ийкемдүү жумуш цехин пландаштыруудагы бир машинаны тандоо жана кыйла катуу иштетүү маршруту тууралуу божомолдорду кеңейтет; чечүү үчүн бөлүкчөлөр тобун оптималдаштырууну эки коңшулуктагы табу издөөсү менен бириктирген TS-PSO алгоритмин сунуштайт. Моделдин негизги оптималдаштыруу максаты өндүрүштүн аяктоо убактысын түздөн-түз минималдаштыруу эмес, белгиленген пландаштыруу горизонту боюнча ар бир машина түрүнө болгон суроо-талаптын убакыттык дисперсиясын азайтуу аркылуу талап кылынган машиналардын санын тең салмактуураак бөлүштүрүү болуп саналат.
TS-PSOдо бөлүкчөлөр тобун оптималдаштыруу (PSO) чоң чечим мейкиндигинде баштапкы чечим түзүмүн калыптандыруу жана машинага болгон суроо-талаптын болжолдуу бөлүштүрүлүшүн аныктоо үчүн колдонулат. Андан кийин табу издөөсү MS-FJSPнин машина тандоо жана ырааттуулук ийкемдүүлүгүнө ылайык түзүлгөн эки өзүнчө коңшулукта жергиликтүү жакшыртууну жүргүзөт. Изилдөөчүлөр ыкманы 120 ар башка маселе масштабына бөлүштүрүлгөн жалпы 12.000 түзүлгөн MS-FJSP үлгүсүндө Simulated Annealing (SA), Ant Colony Optimization (ACO) жана Genetic Algorithm (GA) менен салыштырышкан; ошондой эле алгоритмдин компоненттерин абляциялык эксперименттер аркылуу изилдешкен.
Түзүлгөн маселе үлгүлөрүндө максат функциясынын төмөн мааниси машинага болгон суроо-талаптын тең салмактуураак экенин билдирген баалоодо TS-PSO негизги салыштыруу масштабдарынын баарында үч базалык ыкмадан төмөн максат функциясынын маанилерин алган. Булактын жалпы эсеби боюнча SAнын TS-PSOго салыштырмалуу орточо айырмасы болжол менен %1,21, GAныкы болжол менен %3,22 жана ACOнуку болжол менен %4,04. Бул сапаттык өсүш айрым үлгүлөрдө бир аз көбүрөөк эсептөө убактысынын эсебинен алынган; убакыттар жалпысынан салыштырылган алгоритмдер менен бирдей чоңдук тартибинде калган.
Чыныгы дүйнө менен байланыш үчүн First Bethune Hospital of Jilin Universityнин 2024-жылдагы кызматкерлерди жайгаштыруу маселеси MS-FJSP катары моделденген. Бул үлгүдө 72 бөлүм машина түрлөрүн, 26 кесиптик даярдык жумуш топторун, 491 кызматкер жумуштарды жана орточо 13 ылайыктуу бөлүм машина шайкештигин билдирет. Булак бул модель үчүн чечим мейкиндигин \(1\times10^{5194}\) деп көрсөтөт. TS-PSO бул жерде да салыштырылган ыкмаларга караганда төмөн дисперсия маанилерин берген. Бирок натыйжалар алгоритмдик моделдөө жана эсептөө экспериментин ырастоо болуп саналат; чыныгы мекемеде графикти ишке ашыруунун операциялык натыйжаларын өлчөгөн талаа эксперименти эмес.
MS-FJSP деген эмне?
MS-FJSP — жумуштар баскычтуу иштетүү маршруттарына ээ болуп, ар бир баскычта талап кылынган машина түрлөрүнүн тандоосу да, ырааты да белгилүү чектөөлөрдүн ичинде ийкемдүү сакталган ийкемдүү жумуш цехин пландаштыруу маселеси. Классикалык FJSPден негизги айырмасы — операцияны жалгыз гана ылайыктуу машинага дайындоо талабын жумшартып, ошол эле баскычта бир нече машина түрүн колдонууга жана алардын иштетүү ыраатын өзгөртүүгө мүмкүндүк берүүсү.
Классикалык FJSPден кайсы жагынан айырмаланат?
Классикалык Flexible Job Shop Scheduling Problem (FJSP) эки негизги чечимди бирге карайт: жумуштар кайсы ыраатта аткарылары жана ар бир операция кайсы ылайыктуу машинада жүргүзүлөрү. Каралган изилдөөдө бул түзүм эки багытта кеңейтилет. Биринчиден, операциялар өндүрүш баскычтары түрүндө уюштурулат жана кийинки баскычка мурунку баскыч бүткөндөн кийин гана өтүүгө болот. Экинчиден, бир баскычта бир гана машинаны тандоонун ордуна талап кылынган сандагы машина түрлөрүн тандап, тандалган машиналардын өз ара иштетүү ыраатын өзгөртүүгө болот.
Модель жумуштарды иштетүү маршруттарына жараша да топтойт. Бир эле жумуш тобундагы жумуштар бир эле иштетүү схемасын карманат. Бул топтоо Flexible Group Shop Scheduling Problemдеги окшош маршруттарды бириктирип, setup убактысын кыскартуу идеясы менен бирдей эмес. MS-FJSPдеги топтоонун максаты — бир эле жумуш түрүнүн кайталанма өндүрүшүн жана бир эле схема ичинде көп сандагы жумуштардын болушун моделдөө.
Баскыч түшүнүгү эмне үчүн маанилүү?
Баскычтуу түзүм өндүрүш же пландаштыруу процессиндеги варианттарды бир сызыктуу машина маршрутуна кысуунун ордуна, чечимдерди ырааттуу, бирок ички жагынан ийкемдүү иштетүү блокторуна бөлөт. \(i\) жумуш тобу үчүн баскычтардын саны \(kn_i\) менен белгиленет. \(k\)-баскычта колдонулушу мүмкүн болгон машина түрлөрүнүн жыйындысы \(LM_{i,k}\), жеткиликтүү машина түрлөрүнүн саны \(NT_{i,k}\), чындап талап кылынган машина түрлөрүнүн саны болсо \(N_{i,k}\) менен көрсөтүлөт.
Бул айырмалоо чечим мейкиндигин тез чоңойтот. Бир баскычта кайсы машиналар тандалары гана эмес, тандалган машиналар кайсы ыраатта колдонулары да чечимге кирет. Ошондуктан машина варианттары жана баскычтардын саны көбөйгөн сайын маселе классикалык бир дайындоолуу түзүмдөргө караганда кыйла чоң комбинатордук издөө мейкиндигин түзөт.
Моделде убакыт жана машина суроо-талабынын көрсөтүлүшү
Изилдөө эки негизги матрицаны колдонот. \(RM\) — машина дайындоо матрицасы жана жумуш × убакыт түзүмүндө кайсы жумуш кайсы убакыт кадамында кайсы машина түрүндө иштетилерин көрсөтөт. \(RN\) болсо машина суроо-талабынын матрицасы; машина түрү × убакыт түзүмүндө ар бир убакыт кадамында белгилүү бир машина түрүнөн канча даана талап кылынарын көрсөтөт.
| Белги | Мааниси |
|---|---|
| \(jn\) | Жалпы жумуш саны |
| \(J_{i,j}\) | \(i\)-жумуш тобундагы \(j\)-жумуш |
| \(gn\) | Жалпы жумуш топторунун саны |
| \(gn_i\) | \(i\)-жумуш тобундагы жумуштардын саны |
| \(kn_i\) | \(i\)-жумуш тобунун иштетүү баскычтарынын саны |
| \(mn\) | Жалпы машина түрлөрүнүн саны |
| \(M_l\) | \(l\)-машина түрү |
| \(M_0\) | Бардык операциялар бүткөнүн көрсөткөн виртуалдык машина |
| \(T_{\max}\) | Жалпы пландаштыруу убактысы / убакыт горизонту |
| \(pt_{i,k,l}\) | \(i\)-топтун \(k\)-баскычын \(M_l\) машинасында иштетүү убактысы |
| \(bt_{i,j,k}\) | \(J_{i,j}\) жумушунун \(k\)-баскычынын башталуу убактысы |
| \(et_{i,j,k}\) | \(J_{i,j}\) жумушунун \(k\)-баскычынын бүтүү убактысы |
| \(LM_{i,k}\) | \(i\)-топтун \(k\)-баскычында колдонулушу мүмкүн болгон машина индекстери |
| \(NM_{i,j,k}\) | \(J_{i,j}\) жумушунун \(k\)-баскычында чындап колдонулган машина индекстери |
| \(O_{i,k,n}\) | \(i\)-топтун \(n\) машина талап кылган \(k\)-баскыч операциясы |
| \(N_{i,k}\) | \(i\)-топтун \(k\)-баскычында талап кылынган машина түрлөрүнүн саны |
| \(NT_{i,k}\) | \(i\)-топтун \(k\)-баскычында жеткиликтүү машина түрлөрүнүн саны |
| \(RM\) | Жумуш × убакыт машина дайындоо матрицасы |
| \(RN\) | Машина түрү × убакыт машина суроо-талап матрицасы |
| \(\mu_{i,j,t,l}\) | \(J_{i,j}\) жумушу \(t\) учурунда \(M_l\) машинасында иштетилсе 1, болбосо 0 |
| \(\phi_{i,j,k,l}\) | \(J_{i,j}\) жумушу \(k\)-баскычта \(M_l\) машинасын колдонсо 1, болбосо 0 |
| \(\xi_{i,k,l}\) | \(i\)-топтун \(k\)-баскычы \(M_l\) машинасын колдоно алса 1, болбосо 0 |
Максат функциясы эмнени оптималдаштырат?
Бул изилдөөдөгү MS-FJSP максат функциясы ар бир машина түрүнө убакыт боюнча болгон суроо-талап көлөмүнүн дисперсияларын кошуп, бул сумманы минималдаштырат; демек төмөнүрөөк маани ошол эле пландаштыруу горизонту ичинде машина муктаждыгынын убакыт боюнча тең салмактуураак бөлүштүрүлгөнүн билдирет. Бул маанилүү, анткени изилдөө классикалык FJSP иштеринде көп кездешкен makespanды гана минималдаштыруудан айырмаланып, машина санын бөлүштүрүүнүн бир калыптуулугун түздөн-түз оптималдаштыруу максатына айлантат.
Ар бир машина түрү үчүн убакыттык орточодон четтөөлөрдүн квадратына негизделген негизги максат функциясы булакта төмөнкүдөй аныкталган:
\[ 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} }. \]
Бул жерде \(RN_{x,y}\) — \(x\)-машина түрүнө \(y\)-убакыт кадамындагы суроо-талап; кашаанын ичиндеги экинчи мүчө болсо ошол эле машина түрүнүн бүткүл пландаштыруу горизонтундагы орточо суроо-талабын көрсөтөт. Демек, функция суроо-талап ийри сызыгынын орточо маанинин айланасындагы таралышын жазалайт.
Чечим мейкиндиги эмне үчүн өтө тез чоңоёт?
\(i\)-жумуш тобунун \(k\)-баскычында \(NT_{i,k}\) жеткиликтүү машина түрүнүн ичинен ирети менен \(N_{i,k}\) машина тандалса, булак мүмкүн болгон тандоо жана иреттөө санын төмөнкүдөй аныктайт:
\[ p_{i,k}=\frac{NT_{i,k}!}{(NT_{i,k}-N_{i,k})!}. \]
Бир жумуштун бардык баскычтарындагы маршруттардын саны:
\[ P_i=\prod_{k=1}^{kn_i}p_{i,k}. \]
Бир топтогу жумуштар айырмаланбаса, жалпы пландаштыруу мүмкүнчүлүктөрүнүн саны булакта:
\[ P= \prod_{i=1}^{gn} \frac{(P_i+gn_i-1)!}{gn_i!\,(P_i-1)!} \]
түрүндө; ал эми жумуштар айырмаланса:
\[ P= \prod_{i=1}^{gn}P_i^{gn_i} \]
түрүндө берилет. Бул туюнтмалар машина саны жана баскыч варианттары көбөйгөндө бардык чечимдерди күч менен толук карап чыгуу эмне үчүн практикалык болбой каларын көрсөтөт.
TS-PSO эмне үчүн эки издөө механизмин бириктирет?
TS-PSO PSOнун чоң чечим мейкиндигинде тез арада жакшы баштапкы түзүм түзүү касиетин табу издөөсүнүн учурдагы жакшы чечимдин айланасында деталдуу жергиликтүү издөө жүргүзө алуу жөндөмү менен бириктирет. Изилдөөдөгү милдет бөлүштүрүү болжол менен “PSO менен баштапкы түзүмдү жана суроо-талап бөлүштүрүлүшүн баала, андан соң MS-FJSPге мүнөздүү эки коңшулукта табу издөөсү менен жакшырт” деген схемага туура келет.
PSO катмары: коддоо, чечмелөө жана баштапкы түзүм
PSO баскычында ар бир машина түрү үчүн DM маалымат матрицасы түзүлөт. Матрицанын саптары тиешелүү машина түрү катышкан иштетүү баскычтарын, мамычалары болсо жумуш тобунун көлөмү, иштетүү убактысы жана тиешелүү убакыт аралыгы сыяктуу маалыматтарды камтыйт. Бир бөлүкчө \(RC\in\mathbb{R}^{cn\times T_{\max}}\) матрицасы менен көрсөтүлөт. Башында тиешелүү убакыт аралыгына суммасы ошол топтогу жумуштардын санына тең болгон терс эмес бүтүн сандар бөлүштүрүлөт.
Ар бир бөлүкчөгө ошол бөлүкчө жеткен эң жакшы абалды сактаган \(RCR\) эс тутум матрицасы да дайындалат. Коддолгон бөлүкчөлөр иштетүү убактысына жараша кеңейтилгенде \(res\in\mathbb{R}^{1\times T_{\max}}\) түрүндөгү суроо-талап катары алынат. Булак бул катардын убакыттык дисперсиясына негизделген PSO ылайыктуулук функциясын төмөнкүдөй берет:
\[ 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 бөлүкчөсүнүн максаттуу абалы глобалдык түрдө табылган эң жакшы бөлүкчө \(RC_{best}\) жана тиешелүү бөлүкчөнүн эс тутум матрицасы \(RCR\) колдонулуп түзүлөт. Изилдөөдө үйрөнүү коэффициенттери \(c_1+c_2=1\) шартын аткарат жана эксперименттерде \(c_1=0{,}3\), \(c_2=0{,}7\) колдонулган.
Кыймыл катышы жана булакта сакталууга тийиш болгон көрсөтүү маселеси
Булак кыймыл катышы үчүн Теңдеме (23)тү төмөнкү формада берип, аны Linearly Decreasing Weight стратегиясы деп аныктайт:
\[ r= r_{ini}- \frac{(r_{ini}-r_{end})(G_k-g)}{G_k} +r_{end}. \]
Бул теңдеме бул жерде булакта жарыяланган формасында сакталган. Жазылган формуланын кадимки алгебралык чечмелөөсү менен тексттеги “сызыктуу түрдө азайуучу” аныктаманын ортосунда тактоо талап кылынат; ошондуктан Verianla тексти формуланы унчукпай башка стандарттуу LDW формуласына өзгөртпөйт. Ошол сыяктуу, булак 1-сүрөттүн түшүндүрмөсүнүн бир жеринде кыймыл катышы тууралуу сөз кылганда \(\gamma\) белгисин колдонот; негизги ыкма баянында өзгөрмө \(r\) болуп саналат.
Эки коңшулуктагы табу издөөсү
PSOдон алынган баштапкы чечимден кийин табу издөөсү учурдагы чечимдин жакын аймагында иштейт. Булак эки коңшулукту аныктайт:
- Swap коңшулугу: тандалган машиналардын ыраатын өзгөртүү аркылуу жаңы талапкерлерди түзөт.
- Replacement коңшулугу: тандалган машинаны жеткиликтүү, бирок тандалбаган башка машина менен алмаштыруу аркылуу жаңы талапкерлерди түзөт.
Булакта коңшулук элементтеринин саны:
\[ sn=\frac{1}{2}\left(N_{i,k}^{2}-N_{i,k}\right) =\frac{N_{i,k}(N_{i,k}-1)}{2} \]
жана
\[ rn=(NT_{i,k}-N_{i,k})N_{i,k} \]
түрүндө берилет. Биринчи туюнтма тандалган \(N_{i,k}\) машинанын экиден орун алмаштыруу комбинацияларынын санын, экинчи туюнтма болсо тандалган машина менен тандалбаган, бирок жеткиликтүү машинанын ортосундагы алмаштыруу варианттарынын санын математикалык түрдө көрсөтөт.
Булак ичиндеги көрсөтүү эскертүүсү: Тексттеги “swap neighborhood is valid if \(N_{i,k}<NT_{i,k}\)” жана “replacement neighborhood is valid if \(N_{i,k}\geq2\)” туюнтмалары Теңдеме (25)–(26) жана булактагы 2-сүрөттөгү операторлордун визуалдык мааниси менен аталыш деңгээлинде дал келбей тургандай көрүнөт. Теңдеме (25)теги swap саны оң болушу үчүн кеминде эки тандалган машина керек болсо, Теңдеме (26)дагы replacement операциясы тандалбаган альтернатива болушун талап кылат. Ошондуктан бул жерде булактын формулалары сакталган жана тексттеги шарттар унчукпай “түзөтүлгөн” деп кабыл алынган эмес.
Булак DNTS скан көлөмү үчүн кошумча түрдө:
\[ d=mn\times\left\lceil\frac{T_{\max}}{sn}\right\rceil \]
туюнтмасын берет. Tabu тизмеси мурда жасалган өзгөртүүлөрдүн белгилүү убакыт ичинде кайра тандалышына жол бербейт; ар бир итерацияда табу эмес коңшулардын арасынан ылайыктуулугу эң жакшы талапкер тандалат жана учурдагы глобалдык эң жакшы чечим жакшыртылса жаңыланат.
Моделдин негизги божомолдору
Математикалык моделди чечмелөөдө төмөнкү божомолдор өзгөчө маанилүү:
- Жумуштарда blocking же машина setup убактысы эске алынбайт.
- Машина жумушка дайындалгандан кийин тиешелүү операция үзгүлтүккө учурабайт.
- Ар бир машина бир убакыт бирдигинде бир гана жумушту иштетет.
- Машинанын жумушту кабыл алуу жана башка чекитке өткөрүү убактысы эске алынбайт.
- Бир эле жумуш тобундагы жумуштар бир эле иштетүү схемасын колдонушат.
- Бир эле схема ичинде маршрут өзгөрсө да жалпы иштетүү убактысы өзгөрбөйт деп кабыл алынат.
- Жумуштун кийинки баскычы мурунку баскыч аяктагандан кийин гана башталат.
- Бир баскычта тандалган бир нече машинаны колдонуу ырааты эркин.
- Моделде ар бир машина түрүнүн саны үчүн туруктуу жогорку кубаттуулук берилбейт; муктаждык \(RN\) аркылуу эсептелет.
Бул божомолдор моделдин эсептелүү мүмкүнчүлүгүн жана изилдөө суроосун тактайт; ошол эле учурда чыныгы өндүрүш системасына өткөрүүдө setup, ташуу, смена, техникалык тейлөө, физикалык машина кубаттуулугу жана башка жергиликтүү чектөөлөр өзүнчө моделдениши керек болушу мүмкүн экенин көрсөтөт.
Изилдөөнүн Ыкмасы жана Жыйынтыктары
Математикалык чектөөлөр системасы
Негизги оптималдаштыруу маселеси булакта:
\[ F=\min f(RN) \]
түрүндө аныкталат. Калган теңдемелер ишке жарамдуу график кайсы шарттарды аткарышы керек экенин белгилейт.
| Теңдеме | Булактагы математикалык түзүм | Илимий ролу |
|---|---|---|
| (8) | \(bt_{i,j,1}=1\) | Бардык жумуштар биринчи баскычка бир эле башталуу убактысында кирет деген божомолду бекитет. |
| (9) | \(0\le RM_{x,y}\le mn\) | Машина дайындоо матрицасынын жарактуу машина индексинин диапазонунда калышын камсыздайт. |
| (10) | \(\sum_{l=1}^{mn}\mu_{i,j,t,l}=1\) | Жумуштун каалаган учурда бир гана машинада иштетилишин камсыздайт. |
| (11) | \(bt_{i,j,k+1}=et_{i,j,k}+1\) | Баскычтардын ырааттуу аткарылышын милдеттендирет. |
| (12) | \(NT_{i,k}\ge N_{i,k}\ge1\) | Талап кылынган машиналардын саны жеткиликтүү машина варианттарынан ашып кетишине жол бербейт. |
| (13) | \(pt_{i,k,l}=pt_{i,k,l'}\), \(et_{i,j,k}=bt_{i,j,k}+pt_{i,k,l}N_{i,k}\) | Булактын бир эле схема ичинде маршрут өзгөрсө да иштетүү убактысын эквиваленттүү деп эсептеген божомолун коддойт. |
| (14) | \(T_{\max}\) эң узак жалпы жумуш убактысына барабар. | Пландаштыруу горизонту эң узак созулган жумуш менен аныкталышын камсыздайт. |
| (15) | \(0\le RN_{x,y}\le h\) | Машина суроо-талабынын терс болбошун жана чоң оң чек ичинде көрсөтүлүшүн камсыздайт. |
| (16) | \(\sum_{t=bt_{i,j,k}}^{et_{i,j,k}}\mu_{i,j,t,l}=pt_{i,k,l}\) | Тандалган машинанын талап кылынган иштетүү убактысы бою колдонулушун байланыштырат. |
| (17) | \(\sum_{t'=t}^{t+pt_{i,k,l}-1}\mu_{i,j,t',l}=pt_{i,k,l}\) | Жумуштун тандалган машинадагы иштетүүсү үзгүлтүксүз убакыт блогунда өтүшүн камсыздайт. |
Эксперименттик түзүлүш
Эксперименттер 72 өзөктүү Intel Xeon Gold 6254 процессору жана 256 GB эс тутуму бар платформада жүргүзүлгөн. TS-PSO үчүн бөлүкчөлөр популяциясы 30, үйрөнүү салмактары \(c_1=0{,}3\) жана \(c_2=0{,}7\), баштапкы кыймыл катышы \(r=0{,}9\) деп коюлган.
| Алгоритм | Негизги эксперимент параметрлери |
|---|---|
| TS-PSO | 30 бөлүкчө; \(c_1=0{,}3\); \(c_2=0{,}7\); баштапкы \(r=0{,}9\) |
| SA | \(T_0=100\); муздоо коэффициенти \(\alpha=0{,}95\); \(T_{end}=0{,}001\); кокустук perturbation коңшулугу |
| ACO | 50 кумурска; \(\rho=0{,}1\); \(\alpha=1{,}0\); \(\beta=2{,}0\); \(\tau_0=0{,}1\) |
| GA | Популяция 100; рулетка дөңгөлөгү менен тандоо; \(P_c=0{,}8\); \(P_m=0{,}01\) |
12.000 үлгүлүү benchmark кантип түзүлдү?
Benchmark жалпы 120 маселе масштабынан турат жана ар бир масштаб үчүн 100 үлгү түзүлүп, жалпысынан 12.000 MS-FJSP үлгүсүнө жетет. Масштаб параметрлери:
| Параметр | Маанилер |
|---|---|
| Машина түрлөрүнүн саны \(M\) | \(\{15,30\}\) |
| Жумуш топторунун саны \(G\) | \(\{10,25\}\) |
| Жумуштардын саны \(J\) | \(\{100,200,300,400,500\}\) |
| Орточо ылайыктуу машина саны \(\bar M\) | \(\{3,5,7,9,12,15\}\) |
| Баскычтардын саны \(K\) | \(\{2,3,4,5\}\) жыйындысынан кокустук |
| Иштетүү убактысы \(P\) | \(U(2,10)\) бир калыптагы бөлүштүрүүдөн кокустук |
Салыштыруулар 30 көз карандысыз иштетүү жана ар башка кокустук баштапкы абалдар менен жүргүзүлгөн. Булак аткаруу айырмасын:
\[ Gap=\frac{v-v_{our}}{v_{our}}\times100\% \]
түрүндө эсептейт. Бул жерде \(v\) салыштырылган алгоритмдин, \(v_{our}\) болсо TS-PSOнун максат мааниси болгондуктан, оң Gap мааниси салыштырылган ыкма TS-PSOдон жогору, башкача айтканда бул минималдаштыруу маселеси үчүн начарыраак максат маанисин бергенин билдирет.
Түзүлгөн маалымат топтомундагы негизги жыйынтыктар
Булактагы 2-таблицанын негизги жыйынтыгы туруктуу: каралган бардык \(M\), \(G\) жана \(J\) комбинацияларынын жалпыланган натыйжаларында TS-PSO эң төмөн дисперсия маанисин берет. Төмөнкү таблица булак маалыматтарынан ар башка масштабдарды өкүлчүлүк кылуу үчүн тандалган үлгүлөрдү Verianla тартибинде көрсөтөт.
| Масштаб \(M,G,J\) | TS-PSO Var | TS-PSO убакыт (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 |
Булактын масштабдар боюнча жалпы эсебинде SA TS-PSOго эң жакын базалык ыкма жана орточо айырма болжол менен %1,21. GA үчүн орточо айырма болжол менен %3,22, ACO үчүн болжол менен %4,04 деп берилет. Бул жыйынтык изилдөө көздөгөн машина суроо-талабынын дисперсиясы боюнча TS-PSO салыштырылган үч мета-эвристикалык ыкмага караганда жакшы натыйжаларды берерин колдойт.
Туруктуулук жана жакындашуу
Булак 3-сүрөттө сегиз ар башка маселе масштабы үчүн 30 көз карандысыз иштетүүнүн кутуча диаграммаларын берет. Визуалдык салыштырууда TS-PSO бөлүштүрүүлөрү ар бир үлгүдө максат функциясынын төмөн маанилеринин аймагында топтолот. Бул натыйжа бир гана кокустук баштапкы абал ийгиликтүү болгонун эмес, кайталанган иштетүүлөрдө да окшош аткаруу тенденциясы алынганын көрсөтүү үчүн колдонулган.
Жакындашуу экспериментинде \(15\times10\) масштабындагы MS-FJSP үлгүлөрү 1000 итерация бою көзөмөлдөнгөн. Булак 100-итерацияда TS-PSO максат маанисин 1405,78 деп берет. 500-итерациянын аягында TS-PSO чечим мааниси SA, ACO жана GAга салыштырмалуу тиешелүүлүгүнө жараша %18,14, %27,22 жана %23,53 төмөн экени көрсөтүлгөн. Авторлордун түшүндүрмөсүнө ылайык, негизги жакшыртуунун көпчүлүк бөлүгү болжол менен алгачкы 500 итерацияда жүрөт жана 800–1000 итерациянын ортосунда ийри сызык байкаларлык түрдө түзөлөт.
Эсептөө чыгымы
Булак TS-PSOнун жалпы убакыт татаалдыгын:
\[ O(G\times N\times S) \]
деп көрсөтөт; бул жерде ушул контексттеги \(G\) максималдуу итерациялардын санын, \(N\) бөлүкчөлөр популяциясын жана \(S\) маселенин масштабын билдирет. Бул татаалдык көрсөтүлүшүндөгү \(G\), MS-FJSP маалымат топтомунун түшүндүрмөсүндө колдонулган “жумуш топторунун саны” белгиси менен бир эле тамганын башка мааниде колдонулушуна байланыштуу контекст боюнча окулушу керек.
Эксперименттик убакыттар маселенин масштабы чоңойгон сайын бардык ыкмаларда өскөн. Булак кичине масштабдан чоң масштабга эсептөө убактысынын өсүшүн TS-PSO үчүн %42,32, GA үчүн %44,28, ACO үчүн %43,53 жана SA үчүн %39,17 деп билдирет. TS-PSO айрым масштабдарда атаандаштарына караганда бир аз узагыраак иштесе да, убакыттар бирдей чоңдук тартибинде калган. Ошондуктан булак жыйынтыктары “эң ылдам алгоритм” деген дооматтан көрө, кошумча убакыттын эсебинен төмөн максат функциясы жана күчтүүрөөк жакындашуу алынганын көрсөтөт.
Абляциялык изилдөө: PSO жана табу издөөсүнүн өзүнчө салымы
TS-PSOнун артыкчылыгы компоненттердин бирөөсүнөн гана келип чыгабы же жокпу текшерүү үчүн изилдөөчүлөр эки вариантты колдонушкан: w/o TS — табу издөөсү алынып салынган версия, w/o PSO болсо PSO алынып салынган версия.
| \(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 |
Эки компонентти тең бирге колдонгон TS-PSO бул үлгүлөрдүн баарында эң төмөн маанини берген. Tabu издөөсү алынып салынганда аткаруунун жоготуусу PSO алынып салынганга караганда чоңураак болушу булак авторлорунун эки коңшулуктагы табу издөөсүн акыркы жергиликтүү жакшыртуунун маанилүү компоненти катары чечмелөөсүнө негиз берет. PSO болсо табу издөөсүнө сапаттуураак баштапкы/коңшулук түзүм берип, издөөнү багыттоого салым кошот.
Оорукана кызматкерлерин пландаштыруу MS-FJSPге кантип айландырылды?
Изилдөөнүн чыныгы дүйнөдөгү мисалы — First Bethune Hospital of Jilin Universityге жаңы кабыл алынган кызматкерлерди бөлүмдөргө дайындоо боюнча 2024-жылдагы пландаштыруу маселеси. Моделдин дал келүүсү төмөнкүдөй:
| Чыныгы маселе элементи | MS-FJSPдеги дал келүүсү |
|---|---|
| Оорукана бөлүмдөрү | Машина түрлөрү |
| Кызматкерлердин кесиптик даярдыгы | Жумуш топтору |
| Кызматкерлер | Жумуштар |
| Белгилүү кесиптик даярдыкка ылайыктуу бөлүмдөр | Ылайыктуу машина варианттары |
Булак бул маселе үлгүсүн \(M=72\), \(G=26\), \(J=491\) жана \(\bar M=13\) деп аныктап, чечим мейкиндигин \(1\times10^{5194}\) деп берет.
| Итерация | Метрика | 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) | 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) | 8937,41 | 8695,87 | 8818,43 | 8734,25 |
100 итерацияда TS-PSO башка ыкмаларга караганда чектелүү өлчөмдө гана төмөн максат маанилерин берсе, 1000 итерацияда айырма кыйла ачылат. Муну менен катар TS-PSOнун эсептөө убактысы да бир аз жогору. Булактын баалоосу боюнча бул натыйжа өтө чоң чечим мейкиндигинде эки коңшулуктагы жергиликтүү издөө көбүрөөк итерация берилгенде өзүнүн артыкчылыгын күчөтөрүн көрсөтөт.
Изилдөө колдогон жыйынтыктар
Изилдөө аныкталган MS-FJSP математикалык моделинин ичинде TS-PSO изилдөөчүлөр түзгөн 12.000 benchmark үлгүсүндө SA, ACO жана GAга караганда төмөн машина-суроо-талап дисперсия маанилерин алганын колдойт. Абляция жыйынтыктары PSO менен табу издөөсүн бирге колдонуу бир компоненттүү варианттарга караганда жакшыраак натыйжа берерин көрсөтөт. Оорукана маалыматтарынан түзүлгөн мисал да MS-FJSPни өндүрүштөн тышкаркы татаал ресурс-дайындоо маселелерине математикалык жактан ыңгайлаштырууга болорун көрсөтөт.
Изилдөө колдобогон жыйынтыктар
Бул изилдөө TS-PSO бардык FJSP/MS-FJSP үлгүлөрүндө глобалдык оптимумга кепилдик берерин далилдебейт. Benchmark натыйжалары каралган маселе түзүү процедурасына, параметр диапазондоруна, салыштыруу ыкмаларына жана аппараттык шарттарга көз каранды. Оорукана мисалы чыныгы маалыматтан моделденген оптималдаштыруу үлгүсү; сунушталган графиктин чыныгы оорукана ишинде колдонулушу жана клиникалык, адам ресурстары же узак мөөнөттүү операциялык натыйжалардын өлчөнүшү бул изилдөөнүн эксперименттик дизайнына кирбейт.
Мындан тышкары, модель негизги формулировкасында setup убакыттарын, ташуу убакыттарын, үзгүлтүктөрдү, чектелүү физикалык машина запасын жана ар башка маршруттардын иштетүү убакыттарын өзгөртө алышын эске албайт. Ошондуктан ыкма башка өндүрүш системасында же мекемелик пландаштыруу чөйрөсүндө колдонулса, жергиликтүү процесс чектөөлөрү моделге өзүнчө кошулуп, аткаруу кайра текшерилиши керек.
Булактагы Теңдеме (23), DNTS коңшулук шарттарынын аталышы жана Algorithm 1деги айрым өзгөрмө тандоолор практикалык кайра ишке ашырууда өзүнчө текшерилиши керек. Бул пункттар изилдөө натыйжаларын автоматтык түрдө жараксыз кылган өкүмдөр катары эмес, булактын жарыяланган көрсөтүлүшүндө көңүл бурууну талап кылган кайра өндүрүмдүүлүк деталдары катары бааланууга тийиш.
Булак жана Ыкма Жөнүндө Эскертүү
Түп нуска изилдөө: Iterated Tabu Search Enhanced Particle Swarm Optimization for the Multi-Stage Flexible Job Shop Scheduling Problem
Авторлор: Chunyang Jiang; Hengyu Song; Baotong Ma; Shiwen Wang; Chulei Zhang; Peng Zhao; You Zhou.
Жооптуу авторлор: Chunyang Jiang жана You Zhou.
Мекемелер: 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, Кытай.
Журнал: AI.
Басмакана: MDPI.
Жарыя маалыматтары: 2026, том 7, сан 5, макала 165.
Жарыя күнү: 9 Май 2026. Булакта тапшыруу 1 Апрель 2026, кайра карап чыгуу 23 Апрель 2026 жана кабыл алуу 24 Апрель 2026 деп көрсөтүлгөн.
DOI: 10.3390/ai7050165
Булак түрү жана рецензия: Рецензияланган илимий журналда жарыяланган изилдөө макаласы.
Лицензия: Creative Commons Attribution 4.0 International (CC BY 4.0). Автордук укук авторлордо сакталат, MDPI лицензия ээси/басмакана катары көрсөтүлгөн.
Каржылоо: Jilin Provincial Department of Science and Technology Project, Grant 20230201083GX.
Маалыматтардын жеткиликтүүлүгү: Авторлор изилдөөдө түзүлгөн же талданган маалыматтар макалада бар экенин жана кошумча тышкы маалымат талап кылынбай турганын билдиришкен.
Кызыкчылыктардын кагылышы: Авторлор кызыкчылыктардын кагылышы жок экенин билдиришкен.
Этикалык билдирүүлөр: Institutional Review Board жана informed consent талаалары булакта “not applicable” деп көрсөтүлгөн.
Авторлордун салымы: Концепциялаштыруу Chunyang Jiang жана Peng Zhao; методология Chunyang Jiang; программалык камсыздоо Chunyang Jiang жана Peng Zhao; текшерүү, формалдык талдоо, изилдөө жана ресурстар Chunyang Jiang; маалыматтарды курациялоо Chunyang Jiang жана Hengyu Song; баштапкы долбоор Chunyang Jiang; кайра карап чыгуу жана редакциялоо Chunyang Jiang; визуалдаштыруу Chunyang Jiang жана Shiwen Wang; көзөмөл Chunyang Jiang жана Baotong Ma; долбоорду башкаруу Chunyang Jiang жана Chulei Zhang; каржылоону алуу Chunyang Jiang жана You Zhou тарабынан аткарылган.
Verianla ыкма эскертүүсү: Бул мазмун булак макаланын сүйлөммө-сүйлөм котормосу же абзацма-абзац кайра жазылышы эмес. Математикалык модель, ыкманын кадамдары, эксперимент параметрлери, сандык натыйжалар, визуалдардын илимий билдирүүсү жана чектөөлөр булак изилдөөдөн алынган; баяндоо Verianla үчүн өз алдынча окутуу түзүмүндө кайра курулган. Булак сүрөттөрүнүн скриншоттору же түп нуска графикалык жайгашуулары колдонулган эмес.
Түшүндүрмө чеги: TS-PSO — мета-эвристикалык оптималдаштыруу ыкмасы. Изилдөө билдирген жакшыраак максат маанилери каралган benchmarkдар жана моделденген чыныгы дүйнө мисалы үчүн эсептөө көрсөткүчүнүн далили; бардык маселе үлгүлөрүндө математикалык жактан далилденген глобалдык оптимум кепилдиги эмес. Булактагы айрым формула/pseudocode көрсөтүүлөрүн өз алдынча кайра ишке ашырууда тактоо талап кылынышы мүмкүн.
Пикир калтырыңыз
E-mail дарегиңиз жарыяланбайт. Милдеттүү талаалар * менен белгиленген