АЛГОРИТМ ПОШУКУ ОПТИМАЛЬНОГО ПО КІЛЬКОСТІ ПРИЛАДІВ РОЗВ’ЯЗКУ ОДНІЄЇ ЗАДАЧІ ТЕОРІЇ РОЗКЛАДІВ

Автор(и)

  • Т. Б. Шпеник Ужгородський національний університет, Україна

DOI:

https://doi.org/10.24144/2415-8038.2013.33.91-95

Ключові слова:

Алгоритм пошуку, Лексикографічна послідовність, Теорія розкладів

Анотація

Розглядається задача, в якій в систему паралельних приладів M={1,2,…,m} в момент часу d=0 надходить множина N робіт. Кожна робота i є N повинна бути без переривань виконана протягом ti ≤ D одиниць часу деяким приладом. Задано час ti , необхідний для виконання роботи i є N приладом з продуктивністю α = 1, а також продуктивність αj кожного з приладів j є M. Запропоновано алгоритм, який будує лексикографічно зростаючу послідовність розкладів π0, π1,….(довжина розкладу πj (j=1,2,…) не перевищує D), в якій кожний наступний розклад використовує меншу кількість приладів, ніж попередній.

Посилання

Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. – М.: МГУ, 2011. – 222 с.

Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений. – М.:МФТИ, 2007. – 326 с.

Joseph Y.-T. Leung (Ed.) Handbook of Scheduling. Algorithms, Models, and Performance Analysis. Boca Raton, FL, USA: Chapman & Hall / CRC, 2004. – 1216 c.

Сервах В.В. Анализ сложности и разработка алгоритмов решения задач календарного планирования и теории расписаний: дис. ... доктора физ.-мат. наук / Сервах В.В. – Новосибирск, 2010. – 221 с.

Лазарев А.А. Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации: дис. ... доктора физ.-мат. наук / Лазарев А.А. – Москва, 2007. – 426 с.

Садыков Р.Р. Алгоритмы решения задач теории расписаний для одного прибора с критериями Lmax и ∑wjUj: дис. ... кандидата физ.-мат. наук / Садыков Р.Р. – Казань, 2006. – 131 с.

Кузка О.І., Шпеник Т.Б. Мінімізація кількості приладів при виконанні робіт в системах ідентичних паралельних приладів // Науковий вісник Ужгородського ун-ту. Серія математика. – 1998. – вип. 3. – С. 147–150.

Кузка А.И., Шпеник Т.Б. Алгоритм последовательного анализа вариантов для минимизации числа приборов в задаче составления расписания, удовлетворяющего директивным срокам // Кибернетика и системный анализ. – 2000. - №5. – С. 118–123.

##submission.downloads##

Опубліковано

2013-07-04

Номер

Том 33 (2013)

Розділ

Статті

Ліцензія

Авторське право (c) 2013 Науковий вісник Ужгородського університету. Серія Фізика

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
    1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
    2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
    3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).