1pi=1wirisumwi(ci-ri)

Материал из Викиконспекты
Версия от 20:12, 18 июня 2012; Dimitrova (обсуждение | вклад) (Описание алгоритма)
Перейти к: навигация, поиск

Постановка задачи

Рассмотрим задачу:

  1. Дано [math]n[/math] работ и один станок.
  2. Для каждой работы известно её время появления [math]r_{i}[/math] и вес [math]w_{i}[/math]. Время выполнения всех работ равно [math]1[/math].

Требуется выполнить все работы, чтобы значение [math]\sum w_{i}(c_{i}-r_{i})[/math] было минимальным.

Описание алгоритма

Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последний работы, будем:

  1. Выбирать работу [math]j[/math] из множества невыполненных работ, у которой [math]r_{i} \le time[/math] и значение [math]w_{i}(time - r{i})[/math] максимально.
  2. Выполняем [math]j[/math] в момент времени [math]time[/math] и увеличиваем [math]time[/math] на один.

Доказательство корректности алгоритма