1precpmtnrifmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(pre-alpha-0.01 version)
(нет различий)

Версия 00:50, 3 июня 2012

Данная задача является обобщением [math]1 \mid prec \mid f_{max}[/math] и также использует правило Лаулера для построения оптимального расписания.

Алгоритм

Идея следующая: допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем работу [math]i[/math], которую выгодно выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим [math] i [/math] в промежутки между этими блоками, до них и после них, начиная с [math] r_i [/math].