3622
правки
Изменения
добавлен заголовок в нотации Грэхема
{{Задача
|definition = Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Работа может начаться только после выполнения некоторых других работ, эта зависимость дана в виде ациклического графа. Необходимо составить такое расписание, чтобы значение <tex>L_{max} = \max\limits_{i=1..n} (C_i - d_i)</tex> было минимальным.
==Источники информации==
* Peter Brucker[http://math. «Scheduling Algorithms» {{mit.edu/~goemans/18438/lec13.pdf Minmax criteria. A polynomial---}} «Springer», 2006 гtime algorithm for jobs of equal length. {{---}} 84 13 стр. {{---}} ISBN 978-3-540-69515]* [http://community.stern.nyu.edu/om/faculty/pinedo/scheduling/shakhlevich/handout04.pdf Basic Scheduling Algorithms for Single Machine Problems: Due-8Date Scheduling]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
