Ma`lumotlar : 1092
Xabarlar soni: 314
Bugun: 19.3.2024
Soat: 6:55
Operatsiyalar kompleksi uchun optimallashtirish masalalari
Muallif: Ochilov S.
Qo`shilgan sana: 2015-04-14
Operatsiyalar kompleksi uchun optimallashtirish masalalari.
Operatsiyalar kompleksini vaqt bo'yicha optimallashtirish masalalari. Tarmoq grafigida kiritik yo'l uzunligini ifodalovchi kiritik vaqtni minimallashtirish masalasi operatsiyalar kompleksini vaqt bo`yicha optimallashtirish masalasini ifodalaydi. Operatsiyalar kompleksining bajarilish vaqtini qiskartirish uchun ma’lum tadbirlarni amalga oshirish, shu jumladan, qo'shimcha mablag' sarflash zarur bo'ladi. Bunday tadbirlar doirasi keng. Ba’zi xollarda vaqtni qisqartirishga qayta rejalashtirish evaziga erishish mumkin. Bundan tashqari, ishlab chiqarishni avtomatlashtirish va mexanizatsiyalash, ishini tashkil qilishni yaxshilash, yangi texnologiyani qo'llash va shu kabi boshqa tadbirlar xisobiga operatsiyalar komleksining bajarilish muddatini qisqartirishga erishish mumkin. Umuman olganda operatsiyalar kompleksini vaqt bo'yicha optimallash masalasi qo'shimcha mablag' sarflash, xamda ichki rezervlarni ishga solish yordamida xal etiladi.
Kushimcha mablag' sarflab operatsiyalar kompleksini vaqt bo'yicha optimallashga doir ikki xil masalaning qo`yilishini qaraymiz. Operatsiyalar kompleksi orgraf (tarmoq grafigi) bilan berilgan bo'lsin. G grafda xar bir yoy Pij operatsiyani ifodalaydi Pij operatsiyaning bajarilish vaqti tij bo'lsin. Agar Pij operatsiya uchun xij qo'shimcha mablag' sarflansa uni bajarish vaqti tij dan t´ij=fij(xij) gacha kamayishi ma’lum, ya’ni t´ij=fij(xij)< tij Ammo qo'shimcha mablag'lar (resursiv) cheklangan xamda xar bir operatsiyani bajarishning minimal vakti (quyi chegarasi) dij mavjud.
Xar bir pij operatsiyani bajarishning boshlash vaqti va tugatish vaqti tmij xij qo'shimcha mablag' miqdorini topish kerakki, bunda;
A) Operatsiyalar kompleksining bajarilishi umumiy vaqti minimal bo'lsin.
B) Operatsiyalarga sarflangan qo'shimcha mablag'lar miqdorlari yig'indisidan oshmasin.
V) Xar bir operatsiyaning bajarish vaqti quyi chegara dij dan kam bo'lmasin.
Bu masalaning matematik ifodalanishi quyidagicha bo'ladi;
Bu masala matematik programmalash masalasi bo'lib fij(xij) funksiyaning kurinishiga qarab chiziqli yoki chiziqsiz programmalash usullari yordamida xal qilinadi. Bu masalaning qo'yilishi oldingi masaladan shu bilan farq qiladiki, unda operatsiyalar kompleksi bajarilish umumiy vaqtiga T0 kattalikdan oshmaslik sharti qo'yilgan. Qo'shimcha mablag' miqdorlari xij larni shunday tanlash talab qilinadiki, ularning yig'indisi minimal bo'lsin, ya’ni quyidagi masala qaraladi:
Endi ichki rezervlardan foydalanib vaqtni optimallash masalasini qaraymiz. B birlik mablag'ni operatsiyalarga tarqatish imkoniyati mavjud. Xar bir P operasiyani bajarish uchun bij birlik mablag' ajratiladi. Agar operatsiyadan xij birlik mablag' olinsa, uni bajarish vaqti tij dan gacha ko'payadi (tij´ >tij) agar xij birlik mablag' qo'shilsa, tij dan tij"=φij(xij)gacha kamayadi (tij<"tij).
Kritik bo'lmagan operatsiyalar rezerv vaqtga ega ekanligini e’tiborga olib ularda mablag' kamaytirilsa, kritik operatsiyalarda esa mablag' ko'paytirilsa operatsiyalar kompleksining bajarilish vaqtini kamaytirish imkoni tug'iladi.
Bu xolda biz quyidagi masalaga kelamiz:
Operatsiyalar kompleksini qiymat bo'yicha optimallashtirish.
Operatsiyalar kompleksini qiymat(xarajatlar) bo'yicha optimallashtirishning xususiy xolini ko'rib chiqamiz. Faraz qilaylik, ma’lum operatsiyani bajarish uchun ketgan xarajatlar uni bajarish uchun ketgan vaqtga teskari proporsional bo'lsin. Bu xolda Pij operatsiyaning qo'shimcha xarajatlar koeffitsienti Kij quyidagi formula bilan xisoblanadi:
Bu yerda tij´– eng ko'p Cij´ xarajatlar talab qiladigan operatsiyani tez bajarish rejimi, tij" – minimal Cij" xarajatlar talab qiladigan operatsiyani normal bajarish rejimi. Qo`shimcha xarajatlar koeffitsienti operatsiyalar bajarish vaqtini bir birlikka kamaytirish operatsiyaga ketgan xarajatlarni qanchaga oshirishini ko'rsatadi. Kritik yo'l uzunligi minimal bo'lgan minimal xarajatli operatsiyalar kompleksidagi kritik yo'lni topish algoritmini keltiramiz
Dastlabki qadam. Qo'shimcha xarajatlar koeffitsientlari f larni topamiz.Xar bir operatsiyaning tij´ bajarilish vaqtidan foydalanib, kritik yo'lni, kritik yo'l uzun-ligi(kritik vakt) tkp operatsiyalarning vakt buyicha tula rezervlari ni va operatsiyalar kompleksining umumiy bajarilish xarajatlari ni topamiz. Birinchi (umumiy) qadam. Kritik operatsiyalar ichida qo'shimcha xarajatlar koeffitsienti eng kichik bo'lganini topamiz. Agar topilgan operatsiya barcha kritik yo'llar uchun umumiy bo'lsa yoki kritik yo'l yagona bo'lsa, bu operatsiya vaqti qisqarishi kerak. Agarda topilgan operatsiya kritik yo'llar uchun umumiy bo'lmasa, lekin bunday yo'llar bir yoki bir necha umumiy operatsiyalarga ega bo'lsa, bu yo'llarning xar biri uchun qo'shimcha xarajatlar koeffitsienti kichik bo'lgan operatsiyani topamiz. Keyin bu operatsiyalar qo'shimcha xarajatlar koeffitsientlari yig'indisini xisoblaymiz va uni kritik yo'llar umumiy operasiyalarining eng kichik qo'shimcha xarajatlar koeffitsienti bilan solishtiramiz. Agar qo'shimcha xarajatlar koeffitsientlarining xosil qilingan yig'indisi kritik yo'llar umumiy operatsiyalarining minimal qiymatli qo'shimcha xarajatlar koeffitsientidan kichik bo'lsa, bu yig'indiga mos operatsiyalarning barchasining bajarilish vaqti qisqarishi kerak. Aks xolda kritik yo'llarning umumiy operatsiyasi bajarilish vaqti qisqarishi kerak. Agar kritik yo'llar umumiy operatsiyalarga ega bo'lmasa, ularning xar birida qo'shimcha xarajatlar koeffitsienti eng kichik bo'lgan operatsiya topiladi. Ikkinchi qadam. Operatsiyaning (operatsiyalarning) bajarilish vaqtini (ular) minimal tij qiymatga erishguncha yoki yangi kritik yo'l paydo bo'lguncha davom ettiramiz. Uchinchi qadam. Tarmoq grafigining xosil qilingan varianti uchun kritik yo'lni, uning uzunligi tkp operatsiyalarning vaqt bo'yicha to'la rezervlari Sij operatsiyalar kompleksining bajarilish xarajatlari ni topamiz. To'rtinchi qadam. Agar kritik yo'lning barcha operatsiyalari vaqt bo'yicha minimal bo'lsalar algoritmni to'xtatamiz, chunki kritik bo'lmagan operatsiyalarning vaqt bo'yicha qisqarishi kompleksini bajarish xarajatlarini ko'paytiradi, lekin kritik yo'l uzunligiga ta’sir qilmaydi. Agarda kritik yo'lning barcha operatsiyalari vaqt bo'yicha minimal bo'lmasalar 1-qadamni bajarishga qaytamiz. Operatsiyalar kompleksini resurslar bo'yicha optimallashtirish. Masalaning ko'yilishi. Operatsiyalar kompleksining tarmoq modeli G=(V ,É) orgrafdan iborat bo'lsin. M xilda Rs s=1‾m miqdorda resurslar bor deb xisoblaymiz. Xar bir Pij operatsiya uning bajarilish vaqti tij va intensivligi bilan xarakterlanadi. Operatsiyaning intensivligi deganda tij vaqt o'tishi mobaynida operatsiyaning bajarilishi uchun zarur bo'lgan resurs miqdoriga aytamiz. Tarmoq grafigidagi operatsiyalarni bajarishdan oldin kerakli bulgan resurslarni aniqlash va ularni bor bo'lgan resurslar bilan solishtirish kerak. Agar ba’zi vaqtlar oralig'ida bor bo'lgan resurslar operatsiyani bajarish uchun yetarli bo'lmasa quyidagi masalani xal qilish zarurati tug'iladi: Tarmoq grafigidagi operatsiyalarni bajarishning shunday boshlang'ich va oxirgi kalendar muddatlarini topingki, rejalashtirilayotgan vaqtda yetarlicha resurs mavjud bulib, operatsiyalar kompleksini bajarish vakti minimal bulsin. Bu masalani xal qilish algoritmini bayon kilganda intensivlik o'zgarmas va bir xil resurs bulgan xolni karaymiz. Quyidagi algoritm xamma vaqt xam optimal yechimni bermasada, unga yaqin yechimni beradi. Masalani yechish algoritmi. Dastlabki kadam. Operatsiyalar kompleksini bajarish chiziqli diagrammasini tuzamiz. Diagrammada xar bir operatsiya uzunligi uning bajarilish vaktiga teng bo'lgan kesma bilan ifodalanadi.Xar bir operatsiyaning boshlanishi undan oldingi operatsiyaning tugashaga to'g'ri kelishi kerak. Diagrammadan operatsiyalar kompleksining bajarilish kritik vaqti tkp va kritik yo'lni topamiz. Birinchi qadam. 1)Vaqt o'qiga xar operatsiyani bajarish vaqtining boshlanishi (τ0) va oxiri τ1 ning proeksiyasini tushiramiz (τ0, τ1 ) oraliq uchun operatsiyalar to'la vaqt rezervlari Sij ni topamiz. Tula vakt rezervlarini o'sish tartibida nomerlaymiz. To'la vaqt rezervlari bir xil bo'lgan operatsiyalarni intensivligi kamayish tartibida nomerlaymiz. (τ0, τ1 ) oraliqdan yuqorida joylashgan operatsiyalar intensivligini ularning nomerlari o'sishi tartibida yig'indisini olamiz va xosil bo'lgan yig'indilarni berilgan resurslar kattaligi R bilan solishtiramiz. Intensivliklari yig'indisi R intensivligini qo'shganda yigindi R dan oshib ketsa, bu operatsiyani qaraliyotgan oraliq uzunligiga unga suramiz va keyingi operatsiya intensivligini qo'shamiz va bu ishni (τ0, τ1 ) oraliqdan yuko-rida joylashgan barcha operatsiyalar qaralguncha davom ettiramiz. Bu amallarni bajarish natijasida yangi chiziqli diagramma paydo bo'ladi. (τ1, τkp ) oraliq ustida joylashgan (i,j) operatsiyalarni shunday joylashtiramizki, ularning boshlari voqealarning sodir bo'lish vaqtlari ustma-ust joylashsin. Umumiy qadam. Faraz qilaylik algoritmning k qadami bajarilgan va qolgan qis-mining boshlanishi momentda bo'lgan operatsiyalar kompleksi chiziqli diagrammasi xosil bo'lgan bo'lsin. (τk, τkp ) oraliqdan yuqorida joylashgan operatsiyalar boshi va oxirining vaqt o'qiga proeksiyasini olamiz va τk, ga eng yakin bulganini τk+1, belgilaymiz. Shunday qilib yangi (τk, τk+1 ) oralik aniqlanadi. (τk, τk+1 ) oraliqdan yuqorida joylashgan operatsiyalarning to'la vaqt rezervlari Sij larni topib ularni nomerlab chiqamiz. Nomerlashni to'la rezervlar o'sish tartibida bajaramiz. 3) Bu punktda birinchi qadamning 3-punktidagidek ish kilamiz. Ammo shu narsaga e’tibor kilish kerakki, agar τk, dan chapdagi (i,j) operatsiya surilishi kerak bo'lsa, birinchi xolda operatsiyani butunlay suramiz, ya’ni bu operatsiyaning boshini momentga qo'yamiz, ikkinchi xolda esa operatsiyani bo'laklarga bo'lamiz va operatsiyaning boshidan τk, gacha bo'lagini joyida qoldiramiz. Qolgan qismini , ya’ni τk, dan oxirigacha bo'lgan bo'lagini unga (τk, τk+1 ) oraliq uzunligigacha suramiz. Operatsiyalarning bo'laklarini keyinchalik yangi operatsiyalar deb xisoblab ularga mos voqealar nashrlarini beramiz. 4) Operatsiyalar kompleksidagi barcha operatsiyalar tekshirilgan bo'lsa, yechimni to'xtatamiz. Aks xolda umumiy qadamning 1-punktiga qaytamiz.
3764 marta o`qildi.