By this author

Minimizing the Total Weighted Duration of Courses in a Single Machine Problem with Precedence Constraints

Issue number 9 from 15.09.2023

Рассматривается одноприборная задача теории расписаний с заданным частичным порядком выполнения работ. Имеются подмножества работ, именуемые курсами. Необходимо построить расписание работ, при котором суммарное взвешенное время обработки всех курсов минимально. Рассматривается случай, когда начальная и конечная работы каждого курса определены однозначно. Доказана NP-трудность рассматриваемой задачи. Предложен алгоритм решения задачи, трудоемкость которого полиномиально зависит от общего числа работ, но экспоненционально - от количества курсов, что позволяет эффективно его использовать при фиксированном небольшом количестве курсов и произвольном числе работ.

7 0