Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням
|
|
| Creator |
Ємець, О.О.
Леонова, М.В. |
|
| Subject |
Iнформатика та кiбернетика
|
|
| Description |
Стаття присвячена розробц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. |
|
| Date |
2016-04-22T18:43:30Z
2016-04-22T18:43:30Z 2016 |
|
| Type |
Article
|
|
| Identifier |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням / О.О. Ємець, М.В. Леонова // Доповiдi Нацiональної академiї наук України. — 2016. — № 3. — С. 26-31. — Бібліогр.: 9 назв. — укр.
1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/99078 519.8 |
|
| Language |
uk
|
|
| Relation |
Доповіді НАН України
|
|
| Publisher |
Видавничий дім "Академперіодика" НАН України
|
|