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

Автор(и)

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

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

Розділ

Статті

Ліцензія

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).