Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань

Автор(и)

  • Олександр Анатолійович Павлов Національний технічний університет України «Київський політехнічний інститут», м. Київ, Україна
  • Олена Григорівна Жданова Національний технічний університет України «Київський політехнічний інститут», м. Київ, Україна
  • Майя Олегівна Сперкач Національний технічний університет України «Київський політехнічний інститут», м. Київ, Україна

DOI:

https://doi.org/10.32626/2308-5916.2014-10.148-158

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

календарне планування, розклад, паралельні прилади, спільний директивний термін, мінімізація максимуму відхилень від директивного терміну, ПДС-алгоритм.

Анотація

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

Завантаження

Дані завантаження ще не доступні.

Біографії авторів

Олександр Анатолійович Павлов, Національний технічний університет України «Київський політехнічний інститут», м. Київ

доктор технічних наук, професор, завідувач кафедри автоматизованих систем обробки інформації та управління, декан факультету інформатики та обчислювальної техніки

Олена Григорівна Жданова, Національний технічний університет України «Київський політехнічний інститут», м. Київ

кандидат технічних наук, доцент, доцент кафедри автоматизованих систем обробки інформації та управління

Посилання

Згуровский М. З. Принятие решений в сетевых системах с ограниченными ресурсами : монография / М. З. Згуровский, А. А. Павлов. — К. : Наукова думка, 2010. — 573 с.

Павлов А. А. Исследование свойств задачи календарного планирования выполнения заданий с общим директивным сроком параллельными при-борами по разным критериям оптимальности / А. А. Павлов, Е. Б. Мисю-ра, М.О. Сперкач // Вісник НТУУ «КПІ». Серія «Інформатика, управління та обчислювальна техніка». — К. : ВЕК+, 2012. — №57. — С. 15–17.

Pavlov A. A. About one subclass of polynomially solvable problems from class «Sequencing jobs to minimize total weighted completion time subject to precedence constraints» / A. A. Pavlov, L. A. Pavlova. — Uzhhorod : Karpat-skij region, 1998. — № 15. — 320 p.

Павлов А. А. Субоптимальный полиномиальный алгоритм решения одно-го класса многоэтапных сетевых задач календарного планирования / А. А. Пав¬лов, М. О. Сперкач, Е. А. Халус // Вісник НТУУ «КПІ». Серія «Інформатика, уп¬равління та обчислювальна техніка». — К. : ВЕК+, 2012. — № 57. — С. 51–55.

Поліноміальна складова ПДС-алгоритму розв’язання однієї задачі теорії розкладів / О. А. Павлов, О. Г. Жданова, О. Б. Місюра, М. О. Сперкач // Технологический аудит и резервы производства. — 2013. — №6/3 (14). — С. 47–52.

Павлов А. А. Признаки оптимальности допустимых решений трудноре-шаемых задач комбинаторной оптимизации / А. А. Павлов // Вісник НТУУ «КПІ». Серія «Інформатика, управління та обчислювальна техніка». — К. : ВЕК+, 2013. — № 59. — (подано до друку).

##submission.downloads##

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

2014-02-26

Номер

2014: Математичне та комп'ютерне моделювання. Серія: Технічні науки. Випуск 10

Розділ

Статті

Ліцензія

Автори, які публікуються в цьому журналі, погоджуються з наступними умовами:

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