1ripmtnsumwc

[math]1 \mid r_i, pmtn \mid \sum w_{i}C_{i}[/math]

Задача:

Дана задача на нахождение расписания: У нас есть несколько работ, которе необходимо выполнит на одном станке. У работ есть время появления [math]r_i[/math] Работы разрешается прерывать в любой момент времени. Требуется выполнить все работы, чтобы значение [math]\sum w_i C_i[/math] (суммарный вес просроченных работ, где [math]w_i[/math] — вес работы, а [math]C_i[/math] — время ее окончания) было минимальным.

Источники информации

• Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 88-93 ISBN 978-3-540-69515-8