Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань
Розглянута задача теорії розкладів, в якій необхідно скласти розклад виконання завдань із загальним директивним терміном ідентичними паралельними приладами за критерієм мінімізації максимального відхилення від директивного терміну моментів завершення приладами усіх завдань. Застосовуючи методологію...
Збережено в:
| Опубліковано в: : | Математичне та комп'ютерне моделювання. Серія: Технічні науки |
|---|---|
| Дата: | 2014 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/86427 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань / О.А. Павлов, О.Г. Жданова, М.О. Сперкач // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2014. — Вип. 10. — С. 148-158. — Бібліогр.: 6 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-86427 |
|---|---|
| record_format |
dspace |
| spelling |
Павлов, О.А. Жданова, О.Г. Сперкач, М.О. 2015-09-17T06:55:16Z 2015-09-17T06:55:16Z 2014 Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань / О.А. Павлов, О.Г. Жданова, М.О. Сперкач // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2014. — Вип. 10. — С. 148-158. — Бібліогр.: 6 назв. — укр. 2308-5916 https://nasplib.isofts.kiev.ua/handle/123456789/86427 519.854.2 Розглянута задача теорії розкладів, в якій необхідно скласти розклад виконання завдань із загальним директивним терміном ідентичними паралельними приладами за критерієм мінімізації максимального відхилення від директивного терміну моментів завершення приладами усіх завдань. Застосовуючи методологію побудови ПДС-алгоритмів, розроблено ознаки оптимальності розкладів та на їх основі визначена множина перестановок, які дозволяють послідовно покращувати значення критерію. Розроблено ПДС-алгоритм розв’язання задачі, який має наступні властивості: поліноміальна складова алгоритму (ознаки оптимальності і поліноміальний алгоритм, що їх перевіряє) одночасно є поліноміальною апроксимацією експоненціальної складової ПДС-алгоритму. The scheduling problem is considered in which is necessary to schedule the jobs with a common due date on identical parallel machines with the criterion of minimizing the maximum deviation of the times when the machines complete all the jobs from the due date. Applying the methodology of the PDCalgorithms on their basis a set of permutations is defined that allows to consistently improve the criterion value. The PDC-algorithm for the problem solution is developed that has the following properties: the polynomial component of the algorithm (the signs of optimality and the polynomial algorithm that is checking them) is in the same time the polynomial approximation of the exponential component of the PDC-algorithm. uk Інститут кібернетики ім. В.М. Глушкова НАН України Математичне та комп'ютерне моделювання. Серія: Технічні науки Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань |
| spellingShingle |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань Павлов, О.А. Жданова, О.Г. Сперкач, М.О. |
| title_short |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань |
| title_full |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань |
| title_fullStr |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань |
| title_full_unstemmed |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань |
| title_sort |
задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань |
| author |
Павлов, О.А. Жданова, О.Г. Сперкач, М.О. |
| author_facet |
Павлов, О.А. Жданова, О.Г. Сперкач, М.О. |
| publishDate |
2014 |
| language |
Ukrainian |
| container_title |
Математичне та комп'ютерне моделювання. Серія: Технічні науки |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| description |
Розглянута задача теорії розкладів, в якій необхідно скласти розклад виконання завдань із загальним директивним терміном ідентичними паралельними приладами за критерієм мінімізації максимального відхилення від директивного терміну моментів завершення приладами усіх завдань. Застосовуючи методологію побудови ПДС-алгоритмів, розроблено ознаки оптимальності розкладів та на їх основі визначена множина перестановок, які дозволяють послідовно покращувати значення критерію. Розроблено ПДС-алгоритм розв’язання задачі, який має наступні властивості: поліноміальна складова алгоритму (ознаки оптимальності і поліноміальний алгоритм, що їх перевіряє) одночасно є поліноміальною апроксимацією експоненціальної складової ПДС-алгоритму.
The scheduling problem is considered in which is necessary to schedule the jobs with a common due date on identical parallel machines with the criterion of minimizing the maximum deviation of the times when the machines complete all the jobs from the due date. Applying the methodology of the PDCalgorithms on their basis a set of permutations is defined that allows to consistently improve the criterion value. The PDC-algorithm for the problem solution is developed that has the following properties: the polynomial component of the algorithm (the signs of optimality and the polynomial algorithm that is checking them) is in the same time the polynomial approximation of the exponential component of the PDC-algorithm.
|
| issn |
2308-5916 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/86427 |
| citation_txt |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань / О.А. Павлов, О.Г. Жданова, М.О. Сперкач // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2014. — Вип. 10. — С. 148-158. — Бібліогр.: 6 назв. — укр. |
| work_keys_str_mv |
AT pavlovoa zadačaskladannârozkladuvikonannâzavdanʹparalelʹnimipriladamizmetoûmínímízacíímaksimumuvídhilennâvíddirektivnogotermínumomentívzaveršennâpriladamiusíhzavdanʹ AT ždanovaog zadačaskladannârozkladuvikonannâzavdanʹparalelʹnimipriladamizmetoûmínímízacíímaksimumuvídhilennâvíddirektivnogotermínumomentívzaveršennâpriladamiusíhzavdanʹ AT sperkačmo zadačaskladannârozkladuvikonannâzavdanʹparalelʹnimipriladamizmetoûmínímízacíímaksimumuvídhilennâvíddirektivnogotermínumomentívzaveršennâpriladamiusíhzavdanʹ |
| first_indexed |
2025-12-07T20:05:07Z |
| last_indexed |
2025-12-07T20:05:07Z |
| _version_ |
1850881246943510528 |