Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань
Vernadsky National Library of Ukraine
Переглянути архів ІнформаціяПоле | Співвідношення | |
Title |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань
|
|
Creator |
Павлов, О.А.
Жданова, О.Г. Сперкач, М.О. |
|
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. |
|
Date |
2015-09-17T06:55:16Z
2015-09-17T06:55:16Z 2014 |
|
Type |
Article
|
|
Identifier |
Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань / О.А. Павлов, О.Г. Жданова, М.О. Сперкач // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2014. — Вип. 10. — С. 148-158. — Бібліогр.: 6 назв. — укр.
2308-5916 http://dspace.nbuv.gov.ua/handle/123456789/86427 519.854.2 |
|
Language |
uk
|
|
Relation |
Математичне та комп'ютерне моделювання. Серія: Технічні науки
|
|
Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|