Рассматривается одноприборная задача теории расписаний с заданным частичным порядком выполнения работ. Имеются подмножества работ, именуемые курсами. Необходимо построить расписание работ, при котором суммарное взвешенное время обработки всех курсов минимально. Рассматривается случай, когда начальная и конечная работы каждого курса определены однозначно. Доказана NP-трудность рассматриваемой задачи. Предложен алгоритм решения задачи, трудоемкость которого полиномиально зависит от общего числа работ, но экспоненционально - от количества курсов, что позволяет эффективно его использовать при фиксированном небольшом количестве курсов и произвольном числе работ.
Индексирование
Scopus
Crossref
Higher Attestation Commission
At the Ministry of Education and Science of the Russian Federation