|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Задача минимизации суммарной взвешенной длительности курсов для одного прибора с ограничениями предшествованиястатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 июля 2024 г.
- Авторы: Мусатова Е.Г., Лазарев А.А.
- Журнал: Автоматика и телемеханика
- Номер: 9
- Год издания: 2023
- Первая страница: 153
- Последняя страница: 168
- DOI: 10.31857/S000523102309009X
- Аннотация: Рассматривается одноприборная задача теории расписаний с заданным частичным порядком выполнения работ. Имеются подмножества работ, именуемые курсами. Необходимо построить расписание работ, при кото- ром суммарное взвешенное время обработки всех курсов минимально. Рассматривается случай, когда начальная и конечная работы каждого курса определены однозначно. Доказана NP-трудность рассматриваемой задачи. Предложен алгоритм решения задачи, трудоемкость которого полиномиально зависит от общего числа работ, но экспоненционально — от количества курсов, что позволяет эффективно его использовать при фиксированном небольшом количестве курсов и произвольном числе работ.
- Добавил в систему: Лазарев Александр Алексеевич