Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням

• Published in: Доповіді НАН України
• Date: 2016
• Main Authors: Ємець, О.О., Леонова, М.В.
• Format: Article
• Language: Ukrainian
• Published: Видавничий дім "Академперіодика" НАН України 2016
• Subjects: Інформатика та кібернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/99078
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням / О.О. Ємець, М.В. Леонова // Доповiдi Нацiональної академiї наук України. — 2016. — № 3. — С. 26-31. — Бібліогр.: 9 назв. — укр.

Стаття присвячена розробцi класифiкацiї задач Z = (P,R,W, F) знаходження розкладу роботи одного приладу iз заданими параметрами. Кожне з завдань має додатну вагу wi ∈ W, час обробки pi ∈ P та час очiкування ri ∈ R, коли воно недоступне для обслуговування, а також заданий критерiй F оптимальностi розкладу. Показана можливiсть полiномiального за часом знаходження розкладiв цих задач. Доведено, що оптимальним розв’язком задач знаходження розкладу роботи одного приладу є упорядкування σ = (i₁, . . . ., ik) завдань згiдно з упорядкуванням по неспаданню елементiв перестановок X = (ri₁, . . . ., rik ) ∈ Ekn(R), де R— мультимножина часiв очiкування завдань. Статья посвящена разработке классификации задач Z = (P,R,W, F) нахождения расписания работы одного прибора с заданными параметрами. Каждое из заданий имеет положительный вес wi ∈ W, время обработки pi ∈ P и время ri ∈ R ожидания, когда оно недоступно для обслуживания, а также заданный критерий F оптимальности расписания. Показана возможность полиномиального по времени нахождения расписаний этих задач. Доказано, что оптимальным решением задач нахождения расписания работы одного прибора является упорядочение σ = (i₁, . . . ., ik) заданий по упорядочению по неубыванию элементов перестановок X = (ri₁, . . . ., rik ) ∈ Ekn(R), R— мультимножество времен ожидания заданий. The article is devoted to the development of a classification of tasks Z = (P,R,W, F) of finding the timetable of one device with the given parameters. Each of the tasks has a positive weight wi ∈ W, processing time pi ∈ P, and waiting time ri ∈ R, if it is not available for the service, and a given criterion F of optimal schedule. The possibility of a scheduling polynomial in the time for these tasks is shown. It is proved that the optimal solution of the tasks of scheduling a device is the nondecreasing ordering σ = (i₁, . . . ., ik) of the elements of permutations X = (ri₁, . . . ., rik ) ∈ Ekn(R), R is a multiset of waiting times of tasks.