WikiDer > Nazariy rejalashtirish muammolari uchun yozuv

Notation for theoretic scheduling problems

Qulay nazariy rejalashtirish muammolari uchun yozuv tomonidan kiritilgan Ronald Grem, Evgeniy Lawler, Jan Karel Lenstra va Aleksandr Rinnooy Kan yilda.^[1] U uchta maydondan iborat: a, β va γ.

Har bir maydon so'zlarning vergul bilan ajratilgan ro'yxati bo'lishi mumkin. A maydoni mashina muhitini, ish xususiyatlari va cheklovlarini va ob'ektiv funktsiyani tavsiflaydi.

1970-yillarning oxiridan boshlab, yozuvlar doimiy ravishda uzaytirilib, ba'zan bir-biriga mos kelmaydi. Natijada, bugungi kunda bir nechta qog'ozlarda alohida belgilar bilan paydo bo'ladigan ba'zi muammolar mavjud.

Mashina muhiti

Yagona bosqich muammolari

Har bir ish ma'lum bir ishlov berish vaqti bilan birga keladi.

1: bitta mashina bor
P: lar bor ${displaystyle m}$ parallel bir xil mashinalar
Q: lar bor ${displaystyle m}$ berilgan tezligi har xil bo'lgan parallel mashinalar, ish muddati ${displaystyle j}$ mashinada ${displaystyle i}$ ishlov berish vaqti ${displaystyle p_ {j}}$ tezlik bilan bo'linadi ${displaystyle s_ {i}}$ .
R: lar bor ${displaystyle m}$ parallel bo'lmagan mashinalar, ishlov berish vaqtlari berilgan ${displaystyle p_ {ij}}$ ish uchun ${displaystyle j}$ mashinada ${displaystyle i}$

Ushbu harflardan keyin bu erda aniqlangan mashinalar soni bo'lishi mumkin ${displaystyle m}$ keyin belgilangan raqamni anglatadi. Masalan, ${displaystyle P2 || C_ {max}}$ ning har birini tayinlash muammosi ${displaystyle n}$ mashinalar bo'yicha maksimal ishlov berish vaqtini minimallashtirish uchun berilgan 2 ta mashinadan biriga ish berildi.

Ko'p bosqichli muammo

O: Do'konni ochish muammosi. Har bir ish ${displaystyle j}$ dan iborat ${displaystyle m}$ operatsiyalar ${displaystyle O_ {ij}}$ uchun ${displaystyle i = 1, ldots, m}$ . Operatsiyalar har qanday tartibda rejalashtirilishi mumkin. Ishlash ${displaystyle O_ {ij}}$ uchun qayta ishlanishi kerak ${displaystyle p_ {ij}}$ mashinadagi birliklar ${displaystyle i}$ .
F: Oqim do'koni muammosi. Har qanday ish ${displaystyle j}$ dan iborat ${displaystyle n_ {j}}$ operatsiyalar ${displaystyle O_ {ij}}$ uchun ${displaystyle k = 1, ldots, n_ {j}}$ , shu tartibda rejalashtirilgan bo'lishi kerak. Ishlash ${displaystyle O_ {ij}}$ uchun qayta ishlanishi kerak ${displaystyle p_ {ij}}$ mashinadagi birliklar ${displaystyle i}$ .
J: Ish do'konidagi muammo. Har qanday ish ${displaystyle j}$ dan iborat ${displaystyle n_ {j}}$ operatsiyalar ${displaystyle O_ {kj}}$ uchun ${displaystyle k = 1, ldots, n_ {j}}$ , shu tartibda rejalashtirilgan bo'lishi kerak. Ishlash ${displaystyle O_ {kj}}$ uchun qayta ishlanishi kerak ${displaystyle p_ {kj}}$ maxsus mashinadagi birliklar ${displaystyle mu _ {kj}}$ bilan ${displaystyle mu _ {kj} eq mu _ {k'j}}$ uchun ${displaystyle keq k '}$ .

Ish xususiyatlari

Qayta ishlash muddati barcha ish joylari uchun teng bo'lishi mumkin ( ${displaystyle p_ {i} = p}$ , yoki ${displaystyle p_ {ij} = p}$ ) yoki hatto birlik uzunligini ( ${displaystyle p_ {i} = 1}$ , yoki ${displaystyle p_ {ij} = 1}$ ). Barcha ishlov berish vaqtlari butun sonlar deb qabul qilinadi. Ba'zi eski tadqiqot ishlarida ular ratsional deb taxmin qilinadi.

${displaystyle r_ {j}}$: har bir ish uchun bo'shatish vaqti beriladi, undan oldin uni rejalashtirish mumkin emas, sukut bo'yicha 0 bo'ladi.
${displaystyle online-r_ {j}}$: Bu onlayn muammo. Ish joylari bo'shatilish vaqtida aniqlanadi. Shu nuqtai nazardan, algoritmning ishlashi uning yordamida o'lchanadi raqobatdoshlik koeffitsienti.
${displaystyle d_ {j}}$: har bir ish uchun belgilangan sana beriladi. Ushbu g'oya shundan iboratki, har bir ish o'z muddatidan oldin bajarilishi kerak va kechikib tugatilgan ish uchun jazo mavjud. Ushbu jazo ob'ektiv qiymat bilan belgilanadi. Ish xarakteristikasining mavjudligi ${displaystyle d_ {j}}$ masalan, ba'zi bir cheklovlar mavjud bo'lmasa, to'g'ridan-to'g'ri taxmin qilinadi va muammo nomida belgilanmaydi ${displaystyle d_ {j} = d}$ , barcha belgilangan sanalar ma'lum bir sanaga teng deb hisoblasak.
${displaystyle {ar {d}} _ {j}}$: har bir ish uchun qat'iy muddat beriladi. Har bir ish o'z muddatidan oldin bajarilishi kerak.
pmtn: Ishlar oldindan tayyorlanishi va boshqa mashinada davom ettirilishi mumkin. Ba'zan "prmp" bilan belgilanadi.
${displaystyle size_ {j}}$: Har bir ish bir vaqtning o'zida rejalashtirilgan bo'lishi kerak bo'lgan bir nechta mashinalar bilan birga keladi, sukut bo'yicha 1 ga teng.

Birinchi darajali munosabatlar

Ishlar uchun ustuvor munosabatlar qisman buyurtma shaklida berilishi mumkin, ya'ni agar men ushbu tartibda i 'ning oldingisi bo'lsam, men tugallangandan keyingina boshlashim mumkin.

oldingi: Umumiy ustunlik munosabati berilgan. Agar ${displaystyle iprec j}$ keyin boshlanish vaqti ${displaystyle j}$ tugashidan oldin bo'lmasligi kerak ${displaystyle i}$ .
zanjirlar: Zanjir shaklida ustuvorlik munosabati berilgan (daraja va daraja ko'pi bilan 1 ga teng).
daraxt: Daraxt ko'rinishidagi umumiy ustunlik munosabati, xoh samimiy bo'lsin, xoh tashqarida.
tayyor: Intree shaklida umumiy ustuvorlik munosabati berilgan (tashqi darajalar ko'pi bilan 1 ga teng).
daraxt: Outtree shaklida umumiy ustunlik munosabati berilgan (darajalar ko'pi bilan 1 ga teng).
qarama-qarshi o'rmon: Shaxslar va odatlar to'plami ko'rinishidagi umumiy ustunlik munosabati.
sp-grafik: Ketma-ket parallel grafik shaklida berilgan ustuvorlik munosabati.
cheklangan balandlik: Berilgan ustuvorlik munosabati, bu erda eng uzun yo'nalish doimiy bilan chegaralanadi.
darajadagi tartib: Berilgan ustuvorlik munosabati, bu erda berilgan l darajadagi har bir tepalik (ya'ni bu tepalikdan boshlanadigan eng uzun yo'nalishning uzunligi l) l-1 darajadagi barcha tepaliklarning oldingisi.
intervalli tartib: Haqiqiy chiziqdagi intervalni har bir tepalikka bog'lash mumkin bo'lgan ustuvorlik munosabati berilgan va x va y orasida ustunlik mavjud, agar faqat yarim ochiq intervallar x = [s_x, e_x) va y = [s_y, e_y) bo'lsa. shunday qilib, e_x s_y dan kichik yoki unga teng.
kvazi-intervalli tartib: Kvazi-intervalli buyurtmalar - bu Moukrim-da aniqlangan intervalli buyruqlarning superklassi: yangi buyurtma klassi uchun parallel mashinalarda optimal rejalashtirish, Operations Research Letters, 24 (1): 91-95, 1999.
haddan tashqari oraliq buyurtma: Haddan tashqari intervallar - bu Chardon va Moukrimda aniqlangan kvazi-intervalli buyurtmalarning superklassi: Kofman-Grem algoritmi UET topshiriq tizimlarini ortiqcha intervalli buyurtmalar bilan optimal tarzda hal qiladi, SIAM Journal on Discrete Mathematics, 19 (1): 109-121, 2005.
Buyurtma: Am buyurtmalari - bu Moukrim va Quilliot-da belgilangan haddan tashqari intervalli buyurtmalarning superklassi: multiprotsessorlarni rejalashtirish va chiziqli dasturlash o'rtasidagi bog'liqlik. Buyurtma, 14 (3): 269-278, 1997 yil.
DC grafigi: Bo'lish va yutib olish grafigi - bu Kubiak va boshqalarda aniqlangan ketma-ket parallel grafiklarning subklassi. UET vazifalari grafikalarini bir xil parallel protsessorlarda rejalashtirish uchun HLF ning optimalligi. Diskret optimallashtirish, 6: 79-91, 2009.
2-xira qisman buyurtma: 2 o'lchovli qisman tartib k = 2 uchun k o'lchovli qisman tartibdir.
k-dim qisman tartib: Pozet k o'lchovli qisman tartibdir, agar u k o'lchovli evklid fazosiga joylashtirilishi mumkin bo'lsa, har bir tugun k o'lchovli nuqta bilan ifodalanadigan va har qanday kishi uchun ikkita tugun i va j iff o'rtasida ustunlik mavjud. koordinatasi i koordinatasi j ning koordinatasidan kichik yoki unga teng.

Agar ustunlik munosabati mavjud bo'lsa, qo'shimcha ravishda taxmin qilish mumkin vaqt kechikmoqda. Ruxsat bering ${displaystyle S_ {j}}$ ishning boshlanish vaqtini bildiradi va ${displaystyle C_ {j}}$ uning tugash vaqti. Keyin ustunlik munosabati ${displaystyle iprec j}$ cheklovni nazarda tutadi ${displaystyle C_ {i} + l_ {ij} leq S_ {j}}$ . Agar vaqt kechikmasa ${displaystyle l_ {ij}}$ ko'rsatilgan bo'lsa, u nolga teng deb hisoblanadi. Vaqt kechikishlari ijobiy yoki salbiy sonlar bo'lishi mumkin.

l: ishdan mustaqil vaqt kechikishi. Boshqa so'zlar bilan aytganda ${displaystyle l_ {ij} = l}$ barcha ish juftlari uchun i, j va berilgan l raqami.
${displaystyle l_ {ij}}$: ish juftligiga bog'liq o'zboshimchalik bilan vaqt kechikishi.

Transportning kechikishi

${displaystyle t_ {jk}}$: Operatsiyani yakunlash o'rtasida ${displaystyle O_ {kj}}$ ish ${displaystyle j}$ mashinada ${displaystyle k}$ va ishning boshlanishi ${displaystyle O_ {k + 1, j}}$ ish ${displaystyle j}$ mashinada ${displaystyle k + 1}$ , hech bo'lmaganda transportning kechikishi mavjud ${displaystyle t_ {jk}}$ birliklar.
${displaystyle t_ {jkl}}$: Operatsiyani yakunlash o'rtasida ${displaystyle O_ {kj}}$ ish ${displaystyle j}$ mashinada ${displaystyle k}$ va ishning boshlanishi ${displaystyle O_ {l, j}}$ ish ${displaystyle j}$ mashinada ${displaystyle l}$ , hech bo'lmaganda transportning kechikishi mavjud ${displaystyle t_ {jkl}}$ birliklar.
${displaystyle t_ {k}}$: Mashinaga bog'liq transportni kechiktirish. Operatsiyani yakunlash o'rtasida ${displaystyle O_ {kj}}$ ish ${displaystyle j}$ mashinada ${displaystyle k}$ va ishning boshlanishi ${displaystyle O_ {k + 1, j}}$ ish ${displaystyle j}$ mashinada ${displaystyle k + 1}$ , hech bo'lmaganda transportning kechikishi mavjud ${displaystyle t_ {k}}$ birliklar.
${displaystyle t_ {kl}}$: Mashina juftligiga bog'liq transportni kechiktirish. Operatsiyani yakunlash o'rtasida ${displaystyle O_ {kj}}$ ish ${displaystyle j}$ mashinada ${displaystyle k}$ va ish boshlanishi ${displaystyle O_ {l, j}}$ ish ${displaystyle j}$ mashinada ${displaystyle l}$ , hech bo'lmaganda transportning kechikishi mavjud ${displaystyle t_ {kl}}$ birliklar.
${displaystyle t_ {j}}$: Ishga bog'liq transportni kechiktirish. Operatsiyani yakunlash o'rtasida ${displaystyle O_ {kj}}$ ish ${displaystyle j}$ mashinada ${displaystyle k}$ va ishning boshlanishi ${displaystyle O_ {l, j}}$ ish ${displaystyle j}$ mashinada ${displaystyle l}$ , hech bo'lmaganda transportning kechikishi mavjud ${displaystyle t_ {j}}$ birliklar.

Turli xil cheklovlar

rcrc: "Moslashuvchan ish do'koni" deb nomlangan resirkulyatsiya. Va'da ${displaystyle mu}$ ko'tarilgan va ba'zi juftliklar uchun ${displaystyle keq k '}$ bizda bo'lishi mumkin ${displaystyle mu _ {kj} = mu _ {k'j}}$ .
kutish kerak emas: Amaliyot ${displaystyle O_ {k + 1, i}}$ ishlayotganda aniq boshlash kerak ${displaystyle O_ {k, i}}$ yakunlaydi. Ba'zan "nwt" deb ham belgilanadi.
bo'sh: Ikki qatl o'rtasida hech qanday mashina bo'sh ishlamaydi.
${displaystyle size_ {j}}$: Xuddi shu parallel mashinalarda ko'p protsessorli vazifalar. Ishni bajarish ${displaystyle j}$ bir vaqtning o'zida amalga oshiriladi ${displaystyle size_ {j}}$ parallel mashinalar.
${displaystyle fix_ {j}}$: Multiprotsessor vazifalari. Har qanday ish ${displaystyle j}$ mashinalar to'plami bilan beriladi ${displaystyle fix_ {j} subseteq {1, ldots, m}}$ va bir vaqtning o'zida barcha ushbu mashinalarning bajarilishi kerak. Ba'zan "MPT" bilan belgilanadi.
${displaystyle M_ {j}}$: Ko'p maqsadli mashinalar. Har qanday ish ${displaystyle j}$ berilgan to'plamdan bitta mashinada rejalashtirilgan bo'lishi kerak ${displaystyle M_ {j} subseteq {1, ldots, m}}$ . Ba'zan "M_j" bilan belgilanadi.

Ob'ektiv funktsiyalar

Odatda maqsad ob'ektiv qiymatni minimallashtirishdir. Bitta farq - bu yozuv ${displaystyle summasi U_ {j}}$ bu erda belgilangan muddatgacha bajariladigan ishlarning sonini maksimal darajada oshirish. Bunga yana ishlab chiqarish. Ob'ektiv qiymatni yig'ish mumkin, ehtimol ba'zi bir ustuvor vaznlar bilan tortish mumkin ${displaystyle w_ {j}}$ bir ish uchun.

-: Ob'ektiv qiymatning yo'qligi bitta chiziqcha bilan belgilanadi. Bu shuni anglatadiki, muammo shunchaki mumkin bo'lgan rejalashtirishni ishlab chiqishda va barcha cheklovlarni qondirishda iborat.
${displaystyle C_ {j}}$: Bu tugatish vaqti ish ${displaystyle j}$ .
${displaystyle F_ {j}}$: The oqim vaqti ishning tugashi va bo'shashish vaqti o'rtasidagi farq, ya'ni. ${displaystyle F_ {j} = C_ {j} -r_ {j}}$ .
${displaystyle L_ {j}}$: Kechikish. Har qanday ish ${displaystyle j}$ belgilangan muddat berilgan ${displaystyle d_ {j}}$ . Ishning kechikishi ${displaystyle j}$ sifatida belgilanadi ${displaystyle C_ {j} -d_ {j}}$ . Ba'zan ${displaystyle L_ {max}}$ muddati bilan bog'liq muammoning maqsadga muvofiqligini ko'rsatish uchun ishlatiladi. Darhaqiqat, ikkilik qidiruv yordamida texnik-iqtisodiy versiyaning murakkabligi minimallashtirishga teng ${displaystyle L_ {max}}$ .
${displaystyle U_ {j}}$: O'tkazish qobiliyati. Har bir ishning belgilangan sanasi beriladi ${displaystyle d_ {j}}$ . Bir martani bajaradigan ish uchun birlik foydasi mavjud, ya'ni. ${displaystyle U_ {j} = 1}$ agar ${displaystyle C_ {j} leq d_ {j}}$ va ${displaystyle U_ {j} = 0}$ aks holda. Ba'zan ${displaystyle U_ {j}}$ adabiyotda teskari yo'naltirilgan bo'lib, bu muammoning qaror variantini ko'rib chiqishda tengdir, ammo bu taxminlar uchun juda katta farq qiladi.
${displaystyle T_ {j}}$: Kechikish. Har qanday ish ${displaystyle j}$ belgilangan muddat berilgan ${displaystyle d_ {j}}$ . Ishning kechikishi ${displaystyle j}$ sifatida belgilanadi ${displaystyle T_ {j} = max {0, C_ {j} -d_ {j}}}$ .
${displaystyle E_ {j}}$: Erkaklik. Har qanday ish ${displaystyle j}$ belgilangan muddat berilgan ${displaystyle d_ {j}}$ . Ish qobiliyati ${displaystyle j}$ sifatida belgilanadi ${displaystyle E_ {j} = max {0, d_ {j} -C_ {j}}}$ . Ushbu maqsad juda muhimdir "vaqtida" rejalashtirish.

Misollar

Uyg'unlashtirildi ^[1]

1 | oldindan | ${displaystyle L_ {max}}$: maksimal kechikishni minimallashtiradigan bitta mashina, umumiy ustunlik cheklovi.

R | pmtn | ${displaystyle summasi C_ {i}}$: o'zaro bog'liq bo'lmagan parallel mashinalarning o'zgaruvchan soni, oldindan ishlashga imkon beradigan, yakunlashning umumiy vaqtini minimallashtiradigan.

J3 | ${displaystyle p_ {ij}}$ | ${displaystyle C_ {max}}$: Qurilmani qayta ishlash muddatlari bilan maksimal ishlash muddatini minimallashtiradigan 3 ta dastgoh ish do'koni.

P | ${displaystyle size_ {j}}$ | ${displaystyle C_ {max}}$: ${displaystyle m}$ parallel bir xil mashinalar, har bir ish bir vaqtning o'zida rejalashtirilgan bo'lishi kerak bo'lgan bir qancha mashinalar bilan ta'minlanadi va maksimal bajarish vaqtini minimallashtiradi (shuningdek qarang parallel vazifalarni rejalashtirish muammosi).

Adabiyotlar

B. Chen, KN Potts va G.J. Voy. "Mashinalar jadvalini ko'rib chiqish: murakkablik, algoritmlar va yaqinlik". Kombinatorial optimallashtirish bo'yicha qo'llanma (3-jild) (muharrirlar: D.-Z. Du va P. Pardalos), 1998, Kluwer Academic Publishers. 21-169. ISBN 0-7923-5285-8 (HB) 0-7923-5019-7 (to'siq)
Kristof Dyur, Sigrid Nust, Damien Prot, Oskar C. Vaskes. "Hayvonot bog'ini rejalashtirish".
Piter Bryuker, Sigrid Nust. Muammolarni rejalashtirish uchun murakkablik natijalari

^ ^a ^b Grem, R. L .; Lawler, E. L.; Lenstra, J.K .; Rinnooy Kan, A.G.G. (1979). "Deterministik tartiblash va rejalashtirishda optimallashtirish va yaqinlashtirish: so'rovnoma" (PDF). NATO tizimlari ilmiy panelining diskret optimallashtirish va tizimlarni qo'llash bo'yicha ilg'or tadqiqot instituti va diskret optimallashtirish simpoziumi materiallari.. Elsevier. (5) 287-36-betlar.

[initial_specification-1] Grem, R. L .; Lawler, E. L.; Lenstra, J.K .; Rinnooy Kan, A.G.G. (1979). "Deterministik tartiblash va rejalashtirishda optimallashtirish va yaqinlashtirish: so'rovnoma" (PDF). NATO tizimlari ilmiy panelining diskret optimallashtirish va tizimlarni qo'llash bo'yicha ilg'or tadqiqot instituti va diskret optimallashtirish simpoziumi materiallari.. Elsevier. (5) 287-36-betlar.

[1]

Navigation