|
Записки научных семинаров ЛОМИ, 1979, том 90, страницы 229–264
(Mi znsl3169)
|
|
|
|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
Упорядочение структурного множества работ, минимизирующее суммарный штраф
К. В. Шахбазян
Аннотация:
Решается задача составления расписания, минимизирующего суммарный штраф. Задано множество работ $Z$. Условия предшествования отсутствуют. Каждая работа $\alpha\in Z$ состоит из $V_\alpha$ элементарных операций. Прерывания работы 2 допускаются. Прерывания элементарных операций не допускается. Штраф операции работы $\alpha$, выполняющейся в момент $t$, – $\alpha(t)$. Расписание оценивается штрафом, который является суммой штрафов всех элементарных операций всех работ множества $Z$. Предполагается, что множество $Z$ – структурное. Задача заключается
в нахождении расписания с началом в заданном интервале $[T_1,T_2]$ с минимальным штрафом. Вводятся в рассмотрение структурные согласованные расписания. Класс структурных согласованных расписаний содержит решение задачи.
Предлагается алгорифм, решающий задачу со сложностью по наихудшему случаю $O(k\cdot(T_2-T_1+V))$, где $k$ – число работ в множестве $Z$, $V=\sum_{\alpha\in Z}V_\alpha$. Библ. – 5 назв., рис. 9.
Образец цитирования:
К. В. Шахбазян, “Упорядочение структурного множества работ, минимизирующее суммарный штраф”, Численные методы и вопросы организации вычислений. 3, Зап. научн. сем. ЛОМИ, 90, Изд-во «Наука», Ленинград. отд., Л., 1979, 229–264; J. Soviet Math., 20:2 (1982), 2069–2096
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl3169 https://www.mathnet.ru/rus/znsl/v90/p229
|
Статистика просмотров: |
Страница аннотации: | 112 | PDF полного текста: | 55 |
|