Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням
Стаття присвячена розробцi класифiкацiї задач Z = (P,R,W, F) знаходження розкладу роботи одного приладу iз заданими параметрами. Кожне з завдань має додатну вагу wi ∈ W, час обробки pi ∈ P та час очiкування ri ∈ R, коли воно недоступне для обслуговування, а також заданий критерiй F оптимальностi...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2016 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2016
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/99078 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням / О.О. Ємець, М.В. Леонова // Доповiдi Нацiональної академiї наук України. — 2016. — № 3. — С. 26-31. — Бібліогр.: 9 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-99078 |
|---|---|
| record_format |
dspace |
| spelling |
Ємець, О.О. Леонова, М.В. 2016-04-22T18:43:30Z 2016-04-22T18:43:30Z 2016 Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням / О.О. Ємець, М.В. Леонова // Доповiдi Нацiональної академiї наук України. — 2016. — № 3. — С. 26-31. — Бібліогр.: 9 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/99078 519.8 Стаття присвячена розробц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. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням Полиномиальные алгоритмы решения некоторых задач о построении разложений для прибора для заявок с ожиданием Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| spellingShingle |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням Ємець, О.О. Леонова, М.В. Інформатика та кібернетика |
| title_short |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_full |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_fullStr |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_full_unstemmed |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_sort |
полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| author |
Ємець, О.О. Леонова, М.В. |
| author_facet |
Ємець, О.О. Леонова, М.В. |
| topic |
Інформатика та кібернетика |
| topic_facet |
Інформатика та кібернетика |
| publishDate |
2016 |
| language |
Ukrainian |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Полиномиальные алгоритмы решения некоторых задач о построении разложений для прибора для заявок с ожиданием Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting |
| 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.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/99078 |
| citation_txt |
Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням / О.О. Ємець, М.В. Леонова // Доповiдi Нацiональної академiї наук України. — 2016. — № 3. — С. 26-31. — Бібліогр.: 9 назв. — укр. |
| work_keys_str_mv |
AT êmecʹoo polinomialʹnialgoritmirozvâzuvannâdeâkihzadačpobudovirozkladivpriladudlâzaâvokzočikuvannâm AT leonovamv polinomialʹnialgoritmirozvâzuvannâdeâkihzadačpobudovirozkladivpriladudlâzaâvokzočikuvannâm AT êmecʹoo polinomialʹnyealgoritmyrešeniânekotoryhzadačopostroeniirazloženiidlâpriboradlâzaâvoksožidaniem AT leonovamv polinomialʹnyealgoritmyrešeniânekotoryhzadačopostroeniirazloženiidlâpriboradlâzaâvoksožidaniem AT êmecʹoo polynomialalgorithmsofsolutionforsomeproblemsofconstructionofthetimetablesofadevicefordemandswithwaiting AT leonovamv polynomialalgorithmsofsolutionforsomeproblemsofconstructionofthetimetablesofadevicefordemandswithwaiting |
| first_indexed |
2025-12-07T13:36:18Z |
| last_indexed |
2025-12-07T13:36:18Z |
| _version_ |
1850856784112123904 |