www.wikidata.uk-ua.nina.az

Теорія розкладів розділ дискретної математики що вивчає проблеми впорядкування У загальному випадку проблеми формулюютьс

Теорія розкладів

Теорія розкладів — розділ дискретної математики, що вивчає проблеми впорядкування. У загальному випадку проблеми формулюються так: Дано деяку множину робіт (вимог) з певним набором характеристик: тривалість опрацювання вимоги (найпростіший випадок), вартість опрацювання вимоги, момент надходження вимоги, директивний термін закінчення опрацювання вимоги. Задано деяку множину машин (приладів) , на яких вимоги мають опрацьовуватися відповідно до деякого порядку.

Ставиться задача дискретної оптимізації: побудувати розклад, який мінімізує час виконання робіт, вартість робіт тощо. Розклад — вказівка, на яких машинах і в який час мають опрацьовуватися вимоги (виконуватися роботи).

Задачі теорії розкладів можна розділити на дві групи:

  • Задачі з перериваннями: у будь-який момент опрацювання вимоги на машині можна перервати (з можливістю завершення пізніше на тій самій або іншій машині) задля опрацювання іншої вимоги.
  • Задачі без переривань: кожна вимога на машині опрацьовується від початку до кінця без переривань.

Існують різні варіанти задач теорії розкладів, частина з них є NP-повними, частина належить до класу поліноміальних задач, для частини задач так і не вдалося довести належність до якогось із класів складності. Існує гіпотеза, що задача, яка допускає переривання, не складніша від задачі без переривань. Для більшості задач вона справджується, крім однієї, де для варіанту без переривання доведено його належність до класу поліноміальних задач, тоді як для аналогічної задачі з перериваннями не існує доведення належності до якогось із класів складності.

За дисципліною виконання робіт на машинах можна виділити чотири основні класи задач:

  1. Відкрита лінія (англ. Open shop) — для кожної вимоги задано свою підмножину машин, на кожній з яких вона має опрацьовуватися протягом певного часу. Порядок опрацювання на цих машинах довільний. Задаються різноманітні цільові функції.
  2. Робочий цех (англ. Job shop) — для кожної вимоги задано свою впорядковану підмножину машин (маршрут), на яких вона має опрацьовуватися в заданому порядку. Задаються різноманітні цільові функції.
  3. Flow shop, потокова лінія — всі машини впорядковано — і кожна вимога проходить всі машини в цьому порядку. Розклад задано перестановкою вимог. Як правило, мінімізується загальний час опрацювання вимог.
  4. Задача з директивними термінами — для кожної вимоги задано момент надходження, час опрацювання і директивний термін закінчення опрацювання. Порядок опрацювання на машинах довільний. Необхідно знайти розклад, за якого буде дотримано директивні терміни. При існуванні такого розкладу можна ставити задачу мінімізації числа переривань.

Останню задачу називають одностадійною, три перші — багатостадійними, оскільки для кожної з вимог задано кілька стадій або операцій опрацювання на різних машинах. Можливі різноманітні комбінації обмежень і дисциплін опрацювання, але поліноміальні за часом виконання алгоритми відомі тільки для найпростіших задач із цих класів.

Зокрема, для задачі «Потокова лінія» на двох машинах існує алгоритм Джонсона з часовою складністю , який будує розклад з мінімальним загальним часом опрацювання.

Для задачі з директивними термінами з довільним числом приладів і перериваннями опрацювання існує алгоритм з часовою складністю , який будує розклад з дотриманням директивних термінів.

Розв'язком задач «Відкрита лінія» і «Робочий цех» з одним приладом без переривань є деяка перестановка вимог і для довільної цільової функції ці задачі NP-повні. Але для деяких конкретних цільових функцій знайдено поліноміальні алгоритми.

Задачі теорії розкладів (календарного планування), записані в неперервному часі, мають, як правило, безліч допустимих розв'язків. Метод упорядкування дозволяє звести задачі теорії розкладів до задач оптимізації на скінченних множинах перестановок робіт. Сформульовано загальну постановку задачі теорії розкладів (календарного планування) в неперервному часі, в якій компоненти розв'язків описують за допомогою цілочисельних функцій часу і яку можна розв'язати методом упорядкування.

Два способи зведення початкових задач до задач упорядкування ґрунтуються на поняттях компактних (англ. active) і квазікомпактних (англ. semiactive) розв'язків. У зазначеному вище препринті В. В. Шмельова[ru] поняття компактних і квазікомпактних розв'язків узагальнено і на цій основі запропоновано нове поняття монотонних розв'язків. Кожен монотонний розв'язок є і компактним, і квазікомпактним одночасно, тому таких розв'язків, як правило, менше. Це спрощує розв'язування задач упорядкування.

Для опису динамічних задач розподілу ресурсів зі складними запізненнями, зокрема з векторними і розподіленими, до яких належать і задачі теорії розкладів (календарного планування), Шмельов В. В. 1983 року вперше використав у неявному вигляді і в неперервному часі операцію згортки. Надалі він використовував цю операцію в явному вигляді і для дискретного часу і сформулював загальну постановку задачі теорії розкладів (календарного планування) у вигляді задачі лінійного динамічного програмування зі згортками. Ця постановка дозволяє просто і компактно описувати багато динамічних задач, зокрема і з цілочисельними змінними. Шмельов В. В. поширив свої результати щодо методу точних штрафних функцій на цю постановку.

Примітки Редагувати

  1. S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954) 61-68.
  2. Танаев В. С., Гордон В. С., Шафранский Я. М. Теория расписаний. Одностадийные системы.- М.: Наука, 1984.
  3. The scheduling zoo. Архів оригіналу за 28 квітня 2013. Процитовано 27 квітня 2013. 
  4. CiteSeerX — Single Machine Scheduling Subject to Precedence Delays. Архів оригіналу за 28 квітня 2013. Процитовано 27 квітня 2013. 
  5. Complexity results for scheduling problems. Архів оригіналу за 28 квітня 2013. Процитовано 27 квітня 2013. 
  6. ↑ В. В. Шмелёв. Метод упорядочения в задачах календарного планирования. Препринт. М.: ВНИИСИ[ru]. 1983. Препринт доступний на сайті Наукової електронної бібліотеки eLIBRARY.RU у списку публікацій Шмельова В. В.
  7. Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний.— М.: «Наука», 1975, раздел 6.5.
  8. Шмелёв В. В. Динамические задачи календарного планирования. Автоматика и телемеханика, 1997, № 1, 121—125.
  9. Шмелёв В. В. Метод точных штрафных функций для линейных смешанных целочисленных задач оптимизации. Диссертация на соискание учёной степени доктора физико-математических наук, М.: ИСА РАН, 2000, глава 6. Дисертація та її автореферат доступні на сайті Наукової електронної бібліотеки eLIBRARY.RU в списку публикацій Шмельова В. В.

Література Редагувати

  • Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1975.
  • Танаев В.С.[ru], Шкурба В. В. Введение в теорию расписаний. (серия «Экономико-математическая библиотека»), Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1975.
  • Richard W. Conway, William L. Maxwell, Louis W. Miller. Theory of scheduling
  • Левин В. И. Структурно-логические методы в теории расписаний. Пенза: Изд-во Пенз. гос. технол. акад., 2006.
  • Peter Brucker Scheduling Algorithms [ 21 лютого 2016 у Wayback Machine.]. Heidelberg, Springer. Fifth ed. ISBN 978-3-540-24804-0
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Teoriya rozkladiv rozdil diskretnoyi matematiki sho vivchaye problemi vporyadkuvannya U zagalnomu vipadku problemi formulyuyutsya tak Dano deyaku mnozhinu robit vimog J J 1 J 2 J n displaystyle J J 1 J 2 dots J n z pevnim naborom harakteristik trivalist opracyuvannya vimogi najprostishij vipadok vartist opracyuvannya vimogi moment nadhodzhennya vimogi direktivnij termin zakinchennya opracyuvannya vimogi Zadano deyaku mnozhinu mashin priladiv M M 1 M 2 M m displaystyle M M 1 M 2 dots M m na yakih vimogi mayut opracovuvatisya vidpovidno do deyakogo poryadku Stavitsya zadacha diskretnoyi optimizaciyi pobuduvati rozklad yakij minimizuye chas vikonannya robit vartist robit tosho Rozklad vkazivka na yakih mashinah i v yakij chas mayut opracovuvatisya vimogi vikonuvatisya roboti Zadachi teoriyi rozkladiv mozhna rozdiliti na dvi grupi Zadachi z pererivannyami u bud yakij moment opracyuvannya vimogi na mashini mozhna perervati z mozhlivistyu zavershennya piznishe na tij samij abo inshij mashini zadlya opracyuvannya inshoyi vimogi Zadachi bez pererivan kozhna vimoga na mashini opracovuyetsya vid pochatku do kincya bez pererivan Isnuyut rizni varianti zadach teoriyi rozkladiv chastina z nih ye NP povnimi chastina nalezhit do klasu polinomialnih zadach dlya chastini zadach tak i ne vdalosya dovesti nalezhnist do yakogos iz klasiv skladnosti Isnuye gipoteza sho zadacha yaka dopuskaye pererivannya ne skladnisha vid zadachi bez pererivan Dlya bilshosti zadach vona spravdzhuyetsya krim odniyeyi de dlya variantu bez pererivannya dovedeno jogo nalezhnist do klasu polinomialnih zadach todi yak dlya analogichnoyi zadachi z pererivannyami ne isnuye dovedennya nalezhnosti do yakogos iz klasiv skladnosti Za disciplinoyu vikonannya robit na mashinah mozhna vidiliti chotiri osnovni klasi zadach Vidkrita liniya angl Open shop dlya kozhnoyi vimogi zadano svoyu pidmnozhinu mashin na kozhnij z yakih vona maye opracovuvatisya protyagom pevnogo chasu Poryadok opracyuvannya na cih mashinah dovilnij Zadayutsya riznomanitni cilovi funkciyi Robochij ceh angl Job shop dlya kozhnoyi vimogi zadano svoyu vporyadkovanu pidmnozhinu mashin marshrut na yakih vona maye opracovuvatisya v zadanomu poryadku Zadayutsya riznomanitni cilovi funkciyi Flow shop potokova liniya vsi mashini vporyadkovano M 1 M 2 M m displaystyle M 1 M 2 dots M m i kozhna vimoga prohodit vsi mashini v comu poryadku Rozklad zadano perestanovkoyu vimog Yak pravilo minimizuyetsya zagalnij chas opracyuvannya vimog Zadacha z direktivnimi terminami dlya kozhnoyi vimogi zadano moment nadhodzhennya chas opracyuvannya i direktivnij termin zakinchennya opracyuvannya Poryadok opracyuvannya na mashinah dovilnij Neobhidno znajti rozklad za yakogo bude dotrimano direktivni termini Pri isnuvanni takogo rozkladu mozhna staviti zadachu minimizaciyi chisla pererivan Ostannyu zadachu nazivayut odnostadijnoyu tri pershi bagatostadijnimi oskilki dlya kozhnoyi z vimog zadano kilka stadij abo operacij opracyuvannya na riznih mashinah Mozhlivi riznomanitni kombinaciyi obmezhen i disciplin opracyuvannya ale polinomialni za chasom vikonannya algoritmi vidomi tilki dlya najprostishih zadach iz cih klasiv Zokrema dlya zadachi Potokova liniya na dvoh mashinah isnuye algoritm Dzhonsona 1 z chasovoyu skladnistyu O n log n displaystyle O n log n yakij buduye rozklad z minimalnim zagalnim chasom opracyuvannya Dlya zadachi z direktivnimi terminami z dovilnim chislom priladiv i pererivannyami opracyuvannya isnuye algoritm z chasovoyu skladnistyu O n 3 displaystyle O n 3 yakij buduye rozklad z dotrimannyam direktivnih terminiv 2 Rozv yazkom zadach Vidkrita liniya i Robochij ceh z odnim priladom bez pererivan ye deyaka perestanovka vimog i dlya dovilnoyi cilovoyi funkciyi ci zadachi NP povni Ale dlya deyakih konkretnih cilovih funkcij znajdeno polinomialni algoritmi 3 4 5 Zadachi teoriyi rozkladiv kalendarnogo planuvannya zapisani v neperervnomu chasi mayut yak pravilo bezlich dopustimih rozv yazkiv Metod uporyadkuvannya dozvolyaye zvesti zadachi teoriyi rozkladiv do zadach optimizaciyi na skinchennih mnozhinah perestanovok robit Sformulovano zagalnu postanovku zadachi teoriyi rozkladiv kalendarnogo planuvannya v neperervnomu chasi v yakij komponenti rozv yazkiv opisuyut za dopomogoyu cilochiselnih funkcij chasu i yaku mozhna rozv yazati metodom uporyadkuvannya 6 Dva sposobi zvedennya pochatkovih zadach do zadach uporyadkuvannya gruntuyutsya na ponyattyah kompaktnih angl active i kvazikompaktnih angl semiactive rozv yazkiv 7 U zaznachenomu vishe preprinti V V Shmelova ru 6 ponyattya kompaktnih i kvazikompaktnih rozv yazkiv uzagalneno i na cij osnovi zaproponovano nove ponyattya monotonnih rozv yazkiv Kozhen monotonnij rozv yazok ye i kompaktnim i kvazikompaktnim odnochasno tomu takih rozv yazkiv yak pravilo menshe Ce sproshuye rozv yazuvannya zadach uporyadkuvannya Dlya opisu dinamichnih zadach rozpodilu resursiv zi skladnimi zapiznennyami zokrema z vektornimi i rozpodilenimi do yakih nalezhat i zadachi teoriyi rozkladiv kalendarnogo planuvannya Shmelov V V 1983 roku 6 vpershe vikoristav u neyavnomu viglyadi i v neperervnomu chasi operaciyu zgortki Nadali vin vikoristovuvav cyu operaciyu v yavnomu viglyadi i dlya diskretnogo chasu i sformulyuvav zagalnu postanovku zadachi teoriyi rozkladiv kalendarnogo planuvannya u viglyadi zadachi linijnogo dinamichnogo programuvannya zi zgortkami 8 9 Cya postanovka dozvolyaye prosto i kompaktno opisuvati bagato dinamichnih zadach zokrema i z cilochiselnimi zminnimi Shmelov V V poshiriv svoyi rezultati shodo metodu tochnih shtrafnih funkcij na cyu postanovku Primitki Redaguvati S M Johnson Optimal two and three stage production schedules with setup times included Naval Res Log Quart I 1954 61 68 Tanaev V S Gordon V S Shafranskij Ya M Teoriya raspisanij Odnostadijnye sistemy M Nauka 1984 The scheduling zoo Arhiv originalu za 28 kvitnya 2013 Procitovano 27 kvitnya 2013 CiteSeerX Single Machine Scheduling Subject to Precedence Delays Arhiv originalu za 28 kvitnya 2013 Procitovano 27 kvitnya 2013 Complexity results for scheduling problems Arhiv originalu za 28 kvitnya 2013 Procitovano 27 kvitnya 2013 a b v V V Shmelyov Metod uporyadocheniya v zadachah kalendarnogo planirovaniya Preprint M VNIISI ru 1983 Preprint dostupnij na sajti Naukovoyi elektronnoyi biblioteki eLIBRARY RU u spisku publikacij Shmelova V V Konvej R V Maksvell V L Miller L V Teoriya raspisanij M Nauka 1975 razdel 6 5 Shmelyov V V Dinamicheskie zadachi kalendarnogo planirovaniya Avtomatika i telemehanika 1997 1 121 125 Shmelyov V V Metod tochnyh shtrafnyh funkcij dlya linejnyh smeshannyh celochislennyh zadach optimizacii Dissertaciya na soiskanie uchyonoj stepeni doktora fiziko matematicheskih nauk M ISA RAN 2000 glava 6 Disertaciya ta yiyi avtoreferat dostupni na sajti Naukovoyi elektronnoyi biblioteki eLIBRARY RU v spisku publikacij Shmelova V V Literatura RedaguvatiKonvej R V Maksvell V L Miller L V Teoriya raspisanij Moskva Glavnaya redakciya fiziko matematicheskoj literatury izd va Nauka 1975 Tanaev V S ru Shkurba V V Vvedenie v teoriyu raspisanij seriya Ekonomiko matematicheskaya biblioteka Moskva Glavnaya redakciya fiziko matematicheskoj literatury izd va Nauka 1975 Richard W Conway William L Maxwell Louis W Miller Theory of scheduling Levin V I Strukturno logicheskie metody v teorii raspisanij Penza Izd vo Penz gos tehnol akad 2006 Peter Brucker Scheduling Algorithms Arhivovano 21 lyutogo 2016 u Wayback Machine Heidelberg Springer Fifth ed ISBN 978 3 540 24804 0Naukovo populyarni vidannyaShkurba V V Zadacha tryoh stankov Arhivovano 18 travnya 2021 u Wayback Machine M Nauka 1976 96 s ill Otrimano z https uk wikipedia org w index php title Teoriya rozkladiv amp oldid 35082022