Parallel vazifalarni rejalashtirish muammosi - Parallel task scheduling problem

Nazariy kompyuter fanida parallel vazifalarni rejalashtirish muammosi bu Qattiq-qattiq optimallashtirish muammosi. Berilgan to'plam ${ displaystyle n}$ parallel vazifalar, shuningdek, ish deb nomlanadi, rejalashtirish kerak ${ displaystyle m}$ ba'zida protsessor deb nomlanadigan bir xil mashinalar, eng so'nggi tugash vaqtini minimallashtiradi. Veltman va boshqalarda.^[1] va Drozdovskiy^[2], bu muammo bilan belgilanadi ${ displaystyle P | size_ {j} | C _ { max}}$ ichida uch maydonli yozuv Graham va boshqalar tomonidan kiritilgan ^[3]. Ushbu muammoni shakllantirishning kelib chiqishi 1960 yilda boshlangan^[4]. Ushbu muammo uchun koeffitsientdan kichik bo'lgan polinomiya vaqtini taxmin qilish algoritmi mavjud emas ${ displaystyle 3/2}$ agar bo'lmasa ${ displaystyle P = NP}$.

Ta'rif

Ushbu muammoda bizga to'plam berilgan ${ displaystyle { mathcal {J}}}$ ning ${ displaystyle n}$ ish o'rinlari, shuningdek ${ displaystyle m}$ bir xil mashinalar.Har bir ish ${ displaystyle j in { mathcal {J}}}$ ishlov berish vaqti bor ${ displaystyle p_ {j} in mathbb {N}}$ va bir vaqtning o'zida foydalanishni talab qiladi ${ displaystyle q_ {j} in mathbb {N}}$ Jadval har bir ishni tayinlaydi ${ displaystyle j in { mathcal {J}}}$ boshlanish vaqtiga ${ displaystyle s_ {j} in mathbb {N} _ {0}}$ va to'plam ${ displaystyle m_ {j} subseteq {1, dots, m }}$ ning ${ displaystyle | m_ {j} | = q_ {j}}$ Agar har bir protsessor istalgan vaqtda eng ko'p bitta ishni bajaradigan bo'lsa, jadvalni amalga oshirish mumkin. Muammoning maqsadi ${ displaystyle P | size_ {j} | C _ { max}}$ minimal uzunlikdagi jadvalni topishdir ${ displaystyle C _ { max} = max _ {j in { mathcal {J}}} (s_ {j} + p_ {j})}$, shuningdek jadvalning maketpanasi deb nomlanadi.Jadvalni amalga oshirish uchun etarli shart quyidagilar

${ displaystyle sum _ {j in { mathcal {J}}, s_ {j} leq t$.

Agar ushbu xususiyat barcha boshlang'ich vaqtlari uchun ma'qul bo'lsa, vaqt jadvalidan boshlab har bir qatorda ish joylariga bepul mashinalarni tayinlash orqali mumkin bo'lgan jadval tuzilishi mumkin. ${ displaystyle t = 0}$.^[5][6]. Bundan tashqari, har bir qadamda ish joylari va bo'sh vaqt oralig'ida ishlatiladigan mashina intervallari soni bilan chegaralanishi mumkin ${ displaystyle | { mathcal {J}} | +1}$^[5]. Bu erda mashina oralig'i - bu maksimal barcha kardinallikdagi ketma-ket mashinalar to'plami, chunki bu to'plamdagi barcha mashinalar bir xil ishni bajaradilar. Mashina oralig'i uning birinchi va oxirgi mashinalari indekslari bilan to'liq belgilanadi. Shuning uchun polinom kattaligi bilan chiqishni kodlashning ixcham usulini olish mumkin.

Qattiqlik

Ushbu muammo hatto doimiy mashinalar soni uchun ham NP-ga qiyin ${ displaystyle P2 || C _ { max}}$ ga mos keladi bo'lim muammosi. Bundan tashqari, Du va Leung^[7] bu muammo ekanligini ko'rsatdi qattiq NP-qattiq mashinalar soni kamida bo'lsa ${ displaystyle m = 5}$va mavjudligini a psevdo-polinom vaqt algoritm, bu mashinalar soni ko'pi bilan aniq bo'lsa muammoni aniq hal qiladi ${ displaystyle m = 3}$. Keyinchalik Henning va boshq.^[8] Mashinalar soni ko'p bo'lsa, muammo ham qattiq NP-qattiq ekanligini ko'rsatdi ${ displaystyle m = 4}$. Agar mashinalar soni doimiy bilan chegaralanmagan bo'lsa, taxminiy nisbati kichikroq bo'lgan taxminiy algoritm bo'lishi mumkin emas. ${ displaystyle 3/2}$ agar bo'lmasa ${ displaystyle P = NP}$ chunki bu muammo quyidagilarni o'z ichiga oladi axlat qutisi muammosi subfakt sifatida, ya'ni barcha ish joylarida ishlov berish vaqti bo'lganida ${ displaystyle p_ {j} = 1}$.

Variantlar

Ushbu muammoning o'rganilgan bir nechta variantlari mavjud^[2]. Quyidagi variantlar ham bir-biri bilan birgalikda ko'rib chiqilgan.

Qo'shni ishlar: Ushbu variantda mashinalar belgilangan tartibga ega ${ displaystyle (M_ {1}, nuqtalar, M_ {m})}$. Ishlarni biron bir kichik guruhga tayinlash o'rniga ${ displaystyle m_ {j} subseteq {M_ {1}, dots, M_ {m} }}$, ishlarni mashinalar oralig'iga berish kerak. Ushbu muammo .ning formulasiga mos keladi Iplarni qadoqlash muammosi.

Qoplanadigan ish joylari: Ushbu variantda har bir ish ${ displaystyle j in { mathcal {J}}}$ mumkin bo'lgan mashina raqamlari to'plamiga ega ${ displaystyle D subseteq {1, dots m }}$ va ushbu raqamlarning har biri uchun ${ displaystyle d in D}$ unda ishlov berish vaqti bor ${ displaystyle p_ {j, d}}$. Ishni rejalashtirish uchun ${ displaystyle j in { mathcal {J}}}$, algoritm mashina raqamini tanlashi kerak ${ displaystyle d in D}$ va uni boshlanish vaqtiga belgilang ${ displaystyle s_ {j}}$ va ga ${ displaystyle d}$ vaqt oralig'ida mashinalar ${ displaystyle [s_ {j}, s_ {j} + p_ {j, d}).}$ Ushbu turdagi muammolar uchun odatiy taxmin - bu ishning ta'rifi ${ displaystyle d cdot p_ {j, d}}$ tobora ko'payib borayotgan mashinalar uchun ko'paytirilmaydi.

Bir nechta platformalar: Ushbu variantda mashinalar to'plami mustaqil platformalarda bo'linadi. Rejalashtirilgan ish faqat bitta platformaning mashinalaridan foydalanishi mumkin va ishlov berishda bir nechta platformalar bo'ylab tarqalishiga yo'l qo'yilmaydi.

Algoritmlar

Garey va Grem tomonidan ro'yxatni rejalashtirish algoritmi^[9] mutlaq nisbatga ega ${ displaystyle 2}$, Turek va boshqalar ta'kidlaganidek.^[10] va Lyudvig va Tivari^[11]. Feldmann, Sgall va Teng^[12] ro'yxatni rejalashtirish algoritmi tomonidan ishlab chiqarilgan oldindan belgilanmagan jadvalning uzunligi aslida eng ko'p ekanligi kuzatildi ${ displaystyle (2-1 / m)}$ eng maqbul prepanektivlik vaqtini ko'paytiradi. Ko'p sonli vaqtni taxminiy sxemasi (PTAS), bu raqam uchun ${ displaystyle m}$ protsessorlari doimiy, bilan belgilanadi ${ displaystyle Pm | size_ {j} | C _ { max}}$, Amoura va boshqalar tomonidan taqdim etilgan.^[13] va Yansen va boshq.^[14]Keyinchalik, Yansen va Töle ^[6] protsessorlar soni ish sonida polinom bilan chegaralangan holat uchun PTAS topdi. Ushbu algoritmda mashinalar soni algoritmning vaqt murakkabligida polinomal ko'rinishda bo'ladi. Umuman olganda, mashinalar soni faqat logaritmik ko'rinishda nusxa ko'rinishida paydo bo'lganligi sababli, bu algoritm soxta polinomiyali vaqtni taxminiy sxemasi hamdir. A ${ displaystyle (3/2 + varepsilon)}$- yaqinlashishni Yansen bergan^[15], bu bo'shliqni pastki chegaragacha yopadi ${ displaystyle 3/2}$ o'zboshimchalik bilan kichkintoydan tashqari ${ displaystyle varepsilon}$.

Qo'shni va qo'shni bo'lmagan ishlarning farqlari

Parallel topshiriqlarni rejalashtirish muammosining bir misolini hisobga olgan holda, eng maqbul masofa mashinalarning tutashganligiga qarab farq qilishi mumkin. Agar ish joylari bir-biriga yaqin bo'lmagan mashinalarda rejalashtirilishi mumkin bo'lsa, eng yaxshi ishlab chiqarish vaqti qo'shni bo'lganlarga rejalashtirilgan bo'lishi kerak bo'lganidan kichikroq bo'lishi mumkin. Qo'shni va qo'shni bo'lmagan jadvallar orasidagi farq birinchi marta 1992 yilda namoyish etilgan^[16] misolida ${ displaystyle n = 8}$ vazifalar, ${ displaystyle m = 23}$ protsessorlar, ${ displaystyle C _ { max} ^ {nc} = 17}$va ${ displaystyle C _ { max} ^ {c} = 18}$.Bldek va boshq. ^[17] c / nc-tafovutlari deb ataladigan narsalarni o'rganib chiqdi va quyidagi fikrlarni isbotladi:

• C / nc-farqi paydo bo'lishi uchun kamida uchta vazifa bo'lishi kerak ${ displaystyle q_ {j}> 1.}$
• C / nc farqi paydo bo'lishi uchun kamida uchta vazifa bo'lishi kerak ${ displaystyle p_ {j}> 1.}$
• Hech bo'lmaganda c / nc-farq paydo bo'lishi uchun ${ displaystyle m = 4}$ protsessorlar talab qilinadi (va c / nc-farqli misol mavjud ${ displaystyle m = 4}$).
• C / nc-farqi paydo bo'lishi uchun, qo'shni bo'lmagan jadval uzunligi kamida bo'lishi kerak ${ displaystyle C _ { max} ^ {nc} = 4.}$
• Maksimal c / nc-farq ${ displaystyle sup _ {I} C _ { max} ^ {c} (I) / C _ { max} ^ {nc} (I)}$ hech bo'lmaganda ${ displaystyle 5/4}$ va ko'pi bilan ${ displaystyle 2.}$
• Muayyan misolda c / nc-farq mavjudligini hal qilish uchun NP tugallangan.

Bundan tashqari, ular isbotlanmagan quyidagi ikkita taxminni taklif qilishdi:

• Hech bo'lmaganda c / nc-farq paydo bo'lishi uchun ${ displaystyle n = 7}$ vazifalar talab qilinadi.
• ${ displaystyle sup _ {I} C _ { max} ^ {c} (I) / C _ { max} ^ {nc} (I) = 5/4}$

Shuningdek qarang

• Ish do'konlarini rejalashtirish
• Ochiq do'konda rejalashtirish

Adabiyotlar