37
правок
Изменения
Нет описания правки
<tex dpi ="200">F \mid p_{ij} =Описание задачи=1 \mid \sum w_iu_i</tex>{{Задача|definition=
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
}}
==Описание алгоритма==
{{Утверждение
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.
