Тапсырмаларды жоспарлаудың параллель проблемасы - Parallel task scheduling problem

Теориялық информатикада параллель тапсырмаларды жоспарлау проблемасы болып табылады NP-hard оңтайландыру мәселесі. Берілген жиынтығы ${ displaystyle n}$ қатарлас тапсырмаларды, сонымен қатар жұмыс деп те атайды, оларды жоспарлау керек ${ displaystyle m}$ бірдей машиналар, кейде процессорлар деп аталады, аяқталудың соңғы уақытын азайтады. Вельтман және т.б.^[1] және Дроздовский^[2], бұл проблема арқылы белгіленеді ${ displaystyle P | size_ {j} | C _ { max}}$ ішінде үш өрісті нота Грэм және басқалар енгізген ^[3]. Бұл проблеманы тұжырымдаудың бастауы 1960 жылдан бастау алады^[4]. Бұл мәселе үшін коэффициентінен кіші болатын полиномдық уақытты жуықтау алгоритмі жоқ ${ displaystyle 3/2}$ егер болмаса ${ displaystyle P = NP}$.

Анықтама

Бұл мәселеде бізге жиынтық беріледі ${ displaystyle { mathcal {J}}}$ туралы ${ displaystyle n}$ жұмыс орындары, сондай-ақ ${ displaystyle m}$ бірдей машиналар.Әр жұмыс ${ displaystyle j in { mathcal {J}}}$ өңдеу уақыты бар ${ displaystyle p_ {j} in mathbb {N}}$ және бір мезгілде қолдануды талап етеді ${ displaystyle q_ {j} in mathbb {N}}$ оны орындау кезінде машиналар. кесте әр жұмысты тағайындайды ${ displaystyle j in { mathcal {J}}}$ басталу уақытына дейін ${ displaystyle s_ {j} in mathbb {N} _ {0}}$ және жиынтық ${ displaystyle m_ {j} subseteq {1, нүктелер, m }}$ туралы ${ displaystyle | m_ {j} | = q_ {j}}$ кесте, егер әр процессор белгілі бір уақытта ең көп дегенде бір жұмысты орындайтын болса, кесте орындалуы мүмкін. ${ displaystyle P | size_ {j} | C _ { max}}$ минималды ұзындықтағы кестені табу ${ displaystyle C _ { max} = max _ {j in { mathcal {J}}} (s_ {j} + p_ {j})}$, сонымен қатар графиктің максималды деңгейі деп аталады.Кестені жүзеге асырудың жеткілікті шарты келесі болып табылады

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

Егер бұл қасиет барлық басталатын уақыттарда қанағаттандырылса, жұмыс кестесіне уақыттан бастап әр жолға ақысыз машиналар тағайындау арқылы нақты кесте құруға болады. ${ displaystyle t = 0}$.^[5][6]. Сонымен қатар, жұмыс уақытында қолданылатын машиналық аралықтардың саны және әр қадамдағы бос интервалдармен шектелуі мүмкін ${ displaystyle | { mathcal {J}} | +1}$^[5]. Мұнда машиналық интервал - бұл барлық жиынтықтағы машиналар бір жұмысты өңдейтін, максималды кардиналдығы қатарлы машиналар жиынтығы. Машина аралығы толығымен оның бірінші және соңғы машинасының индексімен анықталады. Сондықтан шығуды полиномдық өлшеммен кодтаудың ықшам әдісін алуға болады.

Қаттылық

Бұл мәселе тіпті машиналардың тұрақты саны үшін де NP қиын ${ displaystyle P2 || C _ { max}}$ сәйкес келеді бөлім мәселесі. Сонымен қатар, Ду және Леунг^[7] бұл проблема екенін көрсетті қатты NP-қатты машиналар саны кем дегенде болған кезде ${ displaystyle m = 5}$және бар екенін a жалған полиномдық уақыт алгоритм, егер машиналар саны көп болса, мәселені дәл шешеді ${ displaystyle m = 3}$. Кейінірек Хеннинг және т.б.^[8] Мәселе машиналардың саны болған кезде қатты NP-қиын болатындығын көрсетті ${ displaystyle m = 4}$. Егер машиналар саны тұрақты шамамен шектелмеген болса, жуықтау коэффициентінен кіші болатын алгоритм болуы мүмкін емес ${ displaystyle 3/2}$ егер болмаса ${ displaystyle P = NP}$ өйткені бұл мәселеде қоқыс жәшігінің ақаулығы кіші шрифт ретінде, яғни барлық жұмыстарды өңдеу уақыты болған кезде ${ displaystyle p_ {j} = 1}$.

Нұсқалар

Бұл проблеманың зерттелген бірнеше нұсқалары бар^[2]. Келесі нұсқалар бір-бірімен үйлесімде қарастырылды.

Іргелес жұмыс орындары: Бұл нұсқада машиналардың бекітілген тәртібі бар ${ displaystyle (M_ {1}, нүкте, M_ {m})}$. Жұмыстарды кез-келген ішкі жиынға тағайындаудың орнына ${ displaystyle m_ {j} subseteq {M_ {1}, нүктелер, M_ {m} }}$, жұмыс машиналардың аралықтарына тағайындалуы керек. Бұл проблема формуланың тұжырымдамасына сәйкес келеді жолақты орау ақаулығы.

Қалыптастырылатын жұмыс орындары: Бұл нұсқада әр жұмыс ${ displaystyle j in { mathcal {J}}}$ машинаның мүмкін болатын нөмірлер жиынтығы бар ${ displaystyle D subseteq {1, нүкте m }}$ және осы сандардың әрқайсысы үшін ${ displaystyle d in D}$ оның өңдеу уақыты бар ${ displaystyle p_ {j, d}}$. Жұмысты жоспарлау үшін ${ displaystyle j in { mathcal {J}}}$, алгоритмге машина нөмірін таңдау керек ${ displaystyle d in D}$ және оны басталатын уақытқа тағайындаңыз ${ displaystyle s_ {j}}$ және дейін ${ displaystyle d}$ уақыт аралығы кезінде машиналар ${ displaystyle [s_ {j}, s_ {j} + p_ {j, d}).}$ Мәселенің осы түріне арналған әдеттегі болжам - бұл жұмыстың жұмысы ретінде анықталады ${ displaystyle d cdot p_ {j, d}}$ көбейіп келе жатқан машиналар саны артпайды.

Бірнеше платформа: Бұл нұсқада машиналар жиынтығы тәуелсіз платформаларға бөлінеді. Жоспарланған жұмыс тек бір платформаның машиналарын қолдана алады және өңделген кезде бірнеше платформаларға таралуына жол берілмейді.

Алгоритмдер

Гарей мен Грэмнің тізімін жоспарлау алгоритмі^[9] абсолютті қатынасқа ие ${ displaystyle 2}$, Турек және басқалар көрсеткендей.^[10] және Людвиг пен Тивари^[11]. Фельдманн, Сгалл және Тенг^[12] тізімнің жоспарлау алгоритмімен жасалған алдын-ала емес кестенің ұзақтығы ең көп дегенде болатынын байқады ${ displaystyle (2-1 / м)}$ оңтайлы алдын-ала есептік көрсеткіштен бірнеше есе көп. Аталған жағдайға арналған полиномды уақытқа жуықтау схемасы (PTAS) ${ displaystyle m}$ процессорлар тұрақты, деп белгіленеді ${ displaystyle Pm | size_ {j} | C _ { max}}$, Амура және басқалар ұсынды.^[13] және Янсен және т.б.^[14]Кейінірек, Янсен мен Толь ^[6] процессорлардың саны жұмыс орындарының санында көпмүшелікпен шектелген жағдайға PTAS тапты. Бұл алгоритмде машиналар саны алгоритмнің уақыттық күрделілігінде полиномдық түрде пайда болады. Жалпы алғанда, машиналар саны тек дананың өлшемінде логарифмдік түрде кездесетіндіктен, бұл алгоритм псевдо-полиномдық уақытқа жуықтау схемасы болып табылады. A ${ displaystyle (3/2 + varepsilon)}$- жуықтауды Янсен берген^[15], бұл аралықты төменгі шекарасына дейін жабады ${ displaystyle 3/2}$ ерікті түрде кішігірім ${ displaystyle varepsilon}$.

Іргелес және сабақтас емес жұмыс арасындағы айырмашылықтар

Тапсырмаларды жоспарлаудың параллель проблемасының данасын ескере отырып, машиналардың үйлесімділігіне байланысты оңтайлы аралық әр түрлі болуы мүмкін. Егер тапсырмаларды шектес емес машиналарда жоспарлауға болатын болса, онда олар ең жақын көрсеткіштермен шектесуге жоспарланғаннан аз болуы мүмкін. Іргелес және шектес емес графиктер арасындағы айырмашылық алғаш рет 1992 жылы көрсетілген^[16] данасында ${ displaystyle n = 8}$ тапсырмалар, ${ displaystyle m = 23}$ өңдеушілер, ${ displaystyle C _ { max} ^ {nc} = 17}$, және ${ displaystyle C _ { max} ^ {c} = 18}$.Błądek және басқалар ^[17] c / nc-айырмашылықтары деп аталатындарды зерттеп, келесі жағдайларды дәлелдеді:

• C / nc-айырмашылықтың пайда болуы үшін кемінде үш тапсырма болуы керек ${ displaystyle q_ {j}> 1.}$
• C / nc-айырмашылықтың пайда болуы үшін кемінде үш тапсырма болуы керек ${ displaystyle p_ {j}> 1.}$
• C / nc-айырмашылық пайда болуы үшін, кем дегенде ${ displaystyle m = 4}$ процессорлар қажет (және c / nc-айырмашылығы бар данасы бар ${ displaystyle m = 4}$).
• C / nc-айырмашылықтың пайда болуы үшін, шектес емес кесте ұзақтығы кем дегенде болуы керек ${ displaystyle C _ { max} ^ {nc} = 4.}$
• Максималды c / nc-айырмашылық ${ displaystyle sup _ {I} C _ { max} ^ {c} (I) / C _ { max} ^ {nc} (I)}$ ең болмағанда ${ displaystyle 5/4}$ және ең көп дегенде ${ displaystyle 2.}$
• Берілген данада c / nc-айырмашылық бар-жоғын шешу NP-аяқталған болып табылады.

Сонымен қатар, олар дәлелденбеген келесі екі болжамды ұсынды:

• C / nc-айырмашылық пайда болуы үшін, кем дегенде ${ displaystyle n = 7}$ тапсырмалар қажет.
• ${ displaystyle sup _ {I} C _ { max} ^ {c} (I) / C _ { max} ^ {nc} (I) = 5/4}$

Сондай-ақ қараңыз

• Жұмыс дүкендерін жоспарлау
• Ашық дүкен кестесі

Әдебиеттер тізімі