Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням
Стаття присвячена розробцi класифiкацiї задач Z = (P,R,W, F) знаходження розкладу роботи одного приладу iз заданими параметрами. Кожне з завдань має додатну вагу wi ∈ W, час обробки pi ∈ P та час очiкування ri ∈ R, коли воно недоступне для обслуговування, а також заданий критерiй F оптимальностi...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2016 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/99078 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням / О.О. Ємець, М.В. Леонова // Доповiдi Нацiональної академiї наук України. — 2016. — № 3. — С. 26-31. — Бібліогр.: 9 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859653038476623872 |
|---|---|
| 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 |
оповiдi
НАЦIОНАЛЬНОЇ
АКАДЕМIЇ НАУК
УКРАЇНИ
3 • 2016
IНФОРМАТИКА ТА КIБЕРНЕТИКА
УДК 519.8 http://dx.doi.org/dopovidi2016.03.026
О.О. Ємець, М. В. Леонова
Полтавський нацiональний педагогiчний унiверситет iм. В. Г. Короленка
E-mail: yemetsli@ukr.net
Полiномiальнi алгоритми розв’язування деяких задач
побудови розкладiв приладу для заявок з очiкуванням
(Представлено академiком НАН України I. В. Сергiєнком)
Стаття присвячена розробцi класифiкацiї задач Z = (P,R,W,F ) знаходження розкладу
роботи одного приладу iз заданими параметрами. Кожне з завдань має додатну вагу
wi ∈ W , час обробки pi ∈ P та час очiкування ri ∈ R, коли воно недоступне для обслуго-
вування, а також заданий критерiй F оптимальностi розкладу. Показана можливiсть
полiномiального за часом знаходження розкладiв цих задач. Доведено, що оптималь-
ним розв’язком задач знаходження розкладу роботи одного приладу є упорядкування
σ = (i1, . . . , ik) завдань згiдно з упорядкуванням по неспаданню елементiв перестановок
X = (ri1 , . . . , rik) ∈ Ekn(R), де R— мультимножина часiв очiкування завдань.
Ключовi слова: задача розкладу для одного приладу, полiномiальний алгоритм.
Задачi вибору черговостi обслуговування, якi вивчаються в теорiї розкладiв, мають загаль-
ний характер i виникають при рiзних видах цiлеспрямованої дiяльностi, наприклад, при
календарному плануваннi виробництва, будiвництва, транспортних перевезень, навчання,
iнформацiйно-обчислювальних процесiв [1–4]. У загальнiй постановцi вони являють собою
процес розподiлу деякого скiнченного набору подiй у часi за умови ресурсних та iнших
обмежень. Часто задача складання розкладу є складною. Така ситуацiя виникає через за-
лученiсть в розклад великої кiлькостi завдань за умови виконання певної системи обмежень.
Тому актуальним є дослiдження таких задач та розробка методiв складання розкладу, осо-
бливо пошук полiномiально розв’язних випадкiв.
Однiєю з найбiльш важливих задач такого типу є задача розкладу для одного i декiлькох
приладiв. Вона розглядається зокрема у працях Е. Г. Коффмана , Е. Г. Танаєва, В. В. Шкур-
би, М. З. Згуровського, О. А. Павлова та iн. [1–4]. Мета розв’язання задачi полягає в тому,
щоб при заданих властивостях завдань та ресурсiв i накладених на них обмеженнях знайти
ефективний алгоритм упорядкування завдань, який оптимiзує бажану мiру ефективностi.
Як основнi мiри ефективностi часто визначаються довжина розкладу i середнiй час вико-
нання завдань.
© О.О. Ємець, М. В. Леонова, 2016
26 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №3
Стаття присвячена обгрунтуванню полiномiального способу розв’язування деяких задач
знаходження розкладу для одного приладу. Це є актуальним, оскiльки такi задачi в загаль-
нiй постановцi належить до класу NP-важких задач i реалiзацiя пошуку їх оптимального
розв’язку потребує неполiномiальних витрат часу. Полiномiальнi алгоритми для певних
часткових випадкiв розглянутi у роботах Е. Г. Коффмана [2], А.А. Лазарева [8] та iн.
Розглянемо одну задачу побудови розкладу для приладу в постановцi [5, 6]. Задано
множину Jk = {1, 2, . . . , k} номерiв завдань. Кожне завдання має додатну вагу wi, час
обробки pi i час очiкування ri, коли воно недоступне для обслуговування. Заданi критерiї
оптимальностi розкладу F . В роботi приладу допускаються переривання. Позначимо за-
гальну задачу пошуку розкладу для одного приладу Z = (P,R,W,F ), як упорядковану
четвiрку, де P = {p1, . . . , pk}, R = {r1, . . . , rk}, W = {w1, . . . , wk} — мультимножини часу
обробки, часу очiкування та ваги завдань вiдповiдно. В [5, 6] необхiдно мiнiмiзувати су-
марно зважений час завершення обслуговування всiх завдань, якщо час обробки є сталим
для всiх завдань pi = p.
Класифiкацiя модифiкацiй задач розкладу для одного приладу. На основi роз-
глянутої задачi з [5, 6] введемо до розгляду деякi задачi побудови розкладу для одного
приладу. Видiлимо такi задачi:
1. Задача Z1 = (P1, R,W1, F1) за умови pi = 1, wi = 1 ∀i ∈ Jk, тобтоP = P1 = {1, . . . , 1},
W = W1 = {1, . . . , 1}. Цiльова функцiяF = F1 — мiнiмiзацiя часу завершення останнього
завдання.
2. Задача Z2 = (P1, R,W1, F2). Цiльова функцiя F2 — мiнiмiзацiя часу простою приладу.
3. Задача розкладу для одного викладача Z3 = (P1, R,W1, F2). Цiльова функцiя F2 —
мiнiмiзацiя часу простою.
4. Задача Z4 = (P,R,W1, F1). Цiльова функцiя F1 — мiнiмiзацiя часу завершення остан-
нього завдання.
5. Задача Z5 = (P1, R,W1, F3). Цiльова функцiя F3 — мiнiмiзацiя сумарного часу завер-
шення всiх завдань.
Поставимо мету — дослiдити можливiсть побудови полiномiального алгоритму для роз-
в’язування цих задач.
Задача Z1 = (P1, R,W1, F1). Нехай маємо множину завдань з номерами Jk. Завдання
з номером i має час очiкування ri, коли воно не доступне для обробки, ri > 0. Тобто цi
величини утворюють мультимножину R = {r1, . . . , rk}. Оскiльки p = p1 = 1, то час pi
обробки завдання з номером i є однаковим для всiх завдань. Маємо w = w1, вага всiх
завдань теж є однаковою одиничною — wi = 1. Цiльова функцiя F1 означає, що необхiдно
визначити розклад, на якому буде досягатися мiнiмальний час обслуговування всiх завдань.
Розглянемо допустимий розв’язок — порядок виконання завдань. Тодi, очевидно, кожен
допустимий розв’язок такої задачi є впорядкованою k-вибiркою з номерiв величин ri згiдно
з їх розташуванням в перестановцi X з загальної множини перестановок Ekn(R) [7]:
x ∈ (x1, . . . , xk) ∈ Ekn(R),
де n — кiлькiсть рiзних елементiв в R; а xi — час очiкування завдання, що виконується i-м.
Часом початку виконання завдання, що виконується першим, є y1 = x1, часом його
завершення — y1 + 1.
Часом початку виконання завдання, що виконується другим, є максимальне значення
iз x2 та y1 + 1, тобто y2 = max{x2, y1 + 1}, а часом закiнчення — y2 + 1.
ISSN 1025-6415 Доп. НАН України, 2016, №3 27
Аналогiчно часом початку виконання завдання, що виконується k-м, є yk = max{xk,
yk−1 + 1}, часом завершення — yk + 1.
Маємо цiльову функцiю, що мiнiмiзує час завершення обслуговування yk + 1, що рiвно-
сильне мiнiмiзацiї часу початку останнього завдання:
F1 = yk = max{xk, yk−1 + 1} → min
за умови виконання наступних спiввiдношень:
y1 = x1; yi = max{xi, yi−1 + 1}; ∀i ∈ Jk \ {1}
та за умови
x ∈ (x1, . . . , xk) ∈ Ekn(R).
Розглянемо умови задачi
y1 = x1; y2 = max{x2, y1 + 1} = max{x2, x1 + 1};
y3 = max{x3, y2 + 1} = max{x3,max{x2, x1 + 1}+ 1} = max{x3, x2 + 1, x1 + 2}
i так далi.
Загальна формула: yj = max{xj , xj−1 + 1, xj−2 + 2, . . . , x1 + (j − 1)} ∀j ∈ Jk \ {1}. Тобто
ми довели таке твердження.
Лема. Умови на допустимий розв’язок (порядок виконання завдань) в задачi Z1 вигляду
y1 = x1; yi = max{xi, yi−1 + 1} ∀i ∈ Jk \ {1}
еквiвалентнi таким:
y1 = x1; yi = max{xi, xi−1 + 1, xi−2 + 2, . . . , x1 + (i− 1)}.
Покажемо, що задачу Z1 можна розв’язати полiномiальним алгоритмом.
Алгоритм одержання одного iз можливих оптимальних розв’язкiв задачi визначає таке
твердження.
Твердження 1. Оптимальним розв’язком задачi Z1 знаходження розкладу роботи
одного приладу з мiнiмiзацiєю часу завершення виконання останнього завдання є упоряд-
кування σ = (i1, . . . , ik) завдань згiдно з упорядкуванням по неспаданню елементiв пере-
становок X = (ri1 , . . . , rik) ∈ Ekn(R),
ri1 6 ri2 6 . . . 6 rik , (1)
де R = {r1, . . . , rk} — мультимножина часiв очiкування завдань.
Зауваження 1. Оскiльки впорядкування елементiв, як вiдомо [9], може бути здiйснено
полiномiальним алгоритмом, а розв’язок задачi Z1 до цього зводиться, то твердження 1
доводить полiномiальну розв’язнiсть задачi.
Задача Z2 = (P1, R,W1, F2). Цiльова функцiя мiнiмiзує суму перiодiв часу, коли жодне
завдання не виконується
F2 =
k∑
j=1
(yj+1 − (yj + 1)) → min,
де yj — час початку завдання з номером j, j ∈ Jk.
28 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №3
Оскiльки задача мiнiмiзацiї часу простою приладу є рiвносильною до мiнiмiзацiї часу
завершення останнього завдання, то оптимальний розв’язок задачi Z2 також можна знайти
згiдно з твердженням 1.
Задача Z3 = (P,R,W1, F1). Нехай час piобробки завдання з номером i не є однаковим
для всiх завдань — P = (p1, . . . , pk), pi > 0, ∀i ∈ Jk. Задача: визначити розклад, на якому
буде досягатися мiнiмальний час обслуговування всiх завдань.
Часом початку виконання завдання, яке виконується першим, є y1 = x1, часом його
завершення — y1 + pi1 , x = (x1, . . . , xk) ∈ Ek(R), R = {r1, . . . , rk}, ri > 0, ∀i ∈ Jk.
Часом початку виконання завдання, яке виконується другим, є максимальне значення
iз x2 та y1 + pi1 , тобто y2 = max{x2, y1 + pi1}, а часом закiнчення — y2 + pi2 .
Аналогiчно часом початку виконання завдання, яке виконується k-м, є yk = max{xk,
yk−1 + pik−1
}, часом завершення — yk + pik .
Маємо цiльову функцiю, яка мiнiмiзує час завершення обслуговування yk + pik , що рiв-
носильне мiнiмiзацiї часу початку останнього завдання:
F1 = yk = max{xk, yk−1 + pik−1
} → min .
З iншого боку в задачi Z3 час завершення останнього завдання (або цiльову функцiю)
можна розглядати у такому виглядi:
F1 = r1 +
k∑
i=1
pi +
k−1∑
j=1
zj , (2)
де r1 — час початку виконання першого завдання розв’язку;
k∑
i=1
pi — сума всiх p;
∑
zj —
сума усiх простоїв пристрою.
Простої розраховуються за формулами:
z1 = max{0; r2 − p1 − r1};
z2 = max
{
0; r3 −
2∑
i=1
pi − r1 − z1
}
;
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
zk−1 = max
{
0; rk −
k−1∑
i=1
pi − r1 −
k−2∑
j=1
zj
}
.
Твердження 2. Якщо у розв’язку X = (r1, . . . , rk−1, rk) простiй zk−1 > 0, то значення
цiльової функцiї обчислюється за формулою F1 = rk + pk.
Твердження 3. Оптимальним розв’язком задачi Z3 знаходження розкладу роботи
одного приладу з мiнiмiзацiєю часу завершення виконання останнього завдання є упоряд-
кування σ = (1, . . . , k) завдань згiдно з упорядкуванням по неспаданню елементiв переста-
новок X = (r1, . . . , rk) ∈ Ekn(R),
r1 6 r2 6 . . . 6 rk, (3)
де R = {r1, . . . , rk} — мультимножина часу очiкування завдань.
ISSN 1025-6415 Доп. НАН України, 2016, №3 29
Задача Z4 = (P1, R,W1, F3). Нехай задача полягає у тому, що потрiбно мiнiмiзувати
не час початку останнього завдання, а суму часу завершення всiх завдань. Оскiльки час
завершення на 1 бiльше часу початку, то це еквiвалентно мiнiмiзацiї суми часу початку.
Тобто цiльова функцiя має вигляд
F3 = x1 +
k−1∑
j=1
max(xj+1; yj + 1) → min, (4)
де x1 — час початку виконання завдання, що виконується першим, max{xj+1; yj +1} — час
початку виконання j-го завдання.
X ∈ Ekn(R).
Твердження 4 . Оптимальним розв’язком задачi Z4 знаходження розкладу роботи
одного приладу з мiнiмiзацiєю сумарного часу завершення всiх завдань є упорядкування
σ = (i1, . . . , ik) завдань згiдно з упорядкуванням по неспаданню елементiв перестановок
X = (ri1 , . . . , rik) ∈ Ekn(R), ri1 6 ri2 6 . . . 6 rik .
Таким чином, в статтi показано, що упорядкування часу очiкування дає оптимальний
розклад в розглянутих задачах Z1 − Z4, а отже це — ефективний спосiб розв’язування
таких задач полiномiальним алгоритмом.
Цитована лiтература
1. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – Москва: Наука, 1975. – 360 с.
2. Коффман Э. Г. Теория расписаний и вычислительные машины. – Москва: Наука, 1984. – 336 с.
3. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. – Москва: Наука, 1975. – 257 с.
4. Згуровский М. З., Павлов А.А. Принятие решений в сетевых системах с ограниченными ресурсами. –
Киев: Наук. думка, 2010. – 573 с.
5. Шерешик Н.Ю. Полиэдральные свойства задачи обслуживания различных требований одним при-
бором “Тезисы докл. XVI Байкальской Междунар. школы-семинара “Методы оптимизации и их при-
ложения”. – Иркутск, ИСЭМ СО РАН, 2014. – С. 96.
6. Brucker P., Knust S. Complexity Results for Scheduling Problems. Режим доступу: www // mathematik.
uni-osnabrueck. de/research/OR/class.
7. Стоян Ю.Г., Ємець О.О. Теорiя i методи евклiдової комбiнаторної оптимiзацiї. – Київ: Iнститут сис-
тем дослiджень освiти, 1993. – 188 с. – Режим доступу http://dspace.uccu.org.ua/handle/123456789/487.
8. Лазарев А.А. Решение NP-трудной задачи теории расписаний минимизации суммарного запаздыва-
ния // Журн. вычислит. математики и мат. физики. – 2007. – 47, № 6. – С. 1087–1098.
9. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск. – Москва: ИД “Вильямс”, 2000. –
824 с.
References
1. Konvey R.V., Maksvell V. L., Miller L.V. Scheduling theory. Moscow, Nauka, 1975 (in Russian).
2. Koffman E.G. Computers and job-shop scheduling theory. Moscow, Nauka, 1984 (in Russian).
3. Tanaev V. S., Shkurba V.V. Introduction to the theory of schedules, Moscow, Nauka, 1975 (in Russian).
4. Zgurovskiy M. Z., Pavlov A.A. Decision making in network systems with limited resources: Monograph.
Кiev, Nauk. dumka, 2010 (in Russian).
5. Shereshik N.Yu. Polyhedral properties maintenance task of different requirements with one device. (Theses
of reports XVI Baikal International School-Seminar “Optimization methods and their applications”). Ir-
kutsk, ISEM SO RAN, 2014 (in Russian).
30 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №3
6. Brucker P., Knust S. Complexity Results for Scheduling Problems. Available at: www//mathematik.uni-
osnabrueck.de/research/OR/class.
7. Stoyan Yu.G., Emets O.O. Theory and methods of Euclidean combinatorial optimization. Kiev, Research
Institute of Education, 1993 (in Ukrainian).
8. Lazarev А.А. J. of Numerical Math. and Math. Phys., 2007: 1087–1098 (in Russian).
9. Knut D. Art of Computer Programming, Volume 3: Sorting and searching, Moscow, “Vilyams”, 2000 (in
Russian).
Надiйшло до редакцiї 30.06.2015
О.А. Емец, М.В. Леонова
Полтавский национальный педагогический университет им. В. Г. Короленко
E-mail: yemetsli@ukr.net
Полиномиальные алгоритмы решения некоторых задач о
построении разложений для прибора для заявок с ожиданием
Статья посвящена разработке классификации задач Z = (P,R,W,F ) нахождения распи-
сания работы одного прибора с заданными параметрами. Каждое из заданий имеет поло-
жительный вес wi ∈ W , время обработки pi ∈ P и время ri ∈ R ожидания, когда оно не-
доступно для обслуживания, а также заданный критерий F оптимальности расписания.
Показана возможность полиномиального по времени нахождения расписаний этих задач.
Доказано, что оптимальным решением задач нахождения расписания работы одного при-
бора является упорядочение σ = (i1, . . . , ik) заданий по упорядочению по неубыванию элемен-
тов перестановок X = (ri1 , . . . , rik) ∈ Ekn(R), R— мультимножество времен ожидания
заданий.
Ключевые слова: задача расписания для одного прибора, полиномиальный алгоритм.
O.O. Iemets, M.V. Leonova
V.G. Korolenko Poltava National Pedagogical University
E-mail: yemetsli@ukr.net
Polynomial algorithms of solution for some problems of construction of
the timetables of a device for demands with waiting
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 σ = (i1, . . . , ik) of the elements of permutations X = (ri1 , . . . , rik) ∈
∈ Ekn(R), R is a multiset of waiting times of tasks.
Keywords: task of scheduling for a single device, polynomial algorithm.
ISSN 1025-6415 Доп. НАН України, 2016, №3 31
|
| 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 |