Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням
Стаття присвячена розробцi класифiкацiї задач Z = (P,R,W, F) знаходження розкладу
 роботи одного приладу iз заданими параметрами. Кожне з завдань має додатну вагу
 wi ∈ W, час обробки pi ∈ P та час очiкування ri ∈ R, коли воно недоступне для обслуговування, а також заданий критерiй...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2016 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| 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| _version_ | 1862625984683966464 |
|---|---|
| author | Ємець, О.О. Леонова, М.В. |
| author_facet | Ємець, О.О. Леонова, М.В. |
| citation_txt | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням / О.О. Ємець, М.В. Леонова // Доповiдi Нацiональної академiї наук України. — 2016. — № 3. — С. 26-31. — Бібліогр.: 9 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| 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.
|
| first_indexed | 2025-12-07T13:36:18Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-99078 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T13:36:18Z |
| publishDate | 2016 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| 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 |
| spellingShingle | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням Ємець, О.О. Леонова, М.В. Інформатика та кібернетика |
| title | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_alt | Полиномиальные алгоритмы решения некоторых задач о построении разложений для прибора для заявок с ожиданием Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting |
| title_full | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_fullStr | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_full_unstemmed | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_short | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| title_sort | полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/99078 |
| 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 |