Жадный алгоритм для задачи календарного планирования с ограниченными ресурсами. Full article
| Journal |
Дискретный анализ и исследование операций
ISSN: 1560-7542 |
||
|---|---|---|---|
| Output data | Year: 2024, Volume: 31, Number: 4, Pages: 27–39 Pages count : 12 DOI: 10.33048/daio.2024.31.796 | ||
| Tags | Задача календарного планирования с ограниченными ресурсами, возобновимые ресурсы, жадный алгоритм, PSPLIB | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
Abstract:
Задача календарного планирования с ограниченными ресурсами --- это общая задача теории расписаний, которая включает в себя ограничения предшествования работ и ресурсные ограничения. Все ресурсы являются возобновимыми, прерывания работ запрещены. Эта задача является NP-трудной с сильном смысле. Предложен новый детерминированный жадный алгоритм. Он основан на эвристике, использующей информацию, полученную в результате решения релаксированной задачи с кумулятивными ресурсами. Алгоритм протестирован со стандартными наборами данных, предоставленными библиотекой PSPLIB для J60, J90 и J120, и показана его эффективность.
Cite:
Гончаров Е.Н.
Жадный алгоритм для задачи календарного планирования с ограниченными ресурсами.
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.27–39. DOI: 10.33048/daio.2024.31.796
Жадный алгоритм для задачи календарного планирования с ограниченными ресурсами.
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.27–39. DOI: 10.33048/daio.2024.31.796
Dates:
| Submitted: | Feb 21, 2024 |
| Accepted: | Jun 22, 2024 |
| Published print: | Dec 30, 2024 |
| Published online: | Dec 30, 2024 |
Identifiers:
No identifiers
Citing:
Пока нет цитирований