Методы решения задач теории расписаний

Сведение к другой задаче

При сведении текущей задачи теории расписаний [math] S [/math] к какой-то другой [math] S' [/math] необходимо доказать два пункта:

1. Допустимость расписания, построенного с помощью задачи [math] P [/math], или существование способа его трансформации в допустимое.
2. Следствие того, что если мы оптимизируем [math] S' [/math], мы также оптимизируем ответ для [math] S [/math] (обратное в общем случае неверно).

Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.

Примеры

1 | intree | Sum(w_i C_i)

Предположим, что мы уже умеем решать задачу [math] S' = 1 \mid outtree \mid \sum w_i C_i [/math]. Сведем нашу задачу [math] S [/math] к ней следующим образом:

• Развернем все ребра, теперь если работа [math] i [/math] зависела от работы [math] j [/math], работа [math] j [/math] будет зависеть от [math] i [/math].
• Заменим все стоимости [math] w_i [/math] на противоположные [math] w'_i = - w_i[/math].

Утверждается, что решив соответствующую задачу [math] S' [/math] и развернув полученное расписание, мы получим ответ для текущей задачи.

1. Полученное расписание будет допустимым, так как расписание для [math] S' [/math] было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для [math] S' [/math] из-за того, что расписание было развернуто, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.
2. Пусть с помощью задачи [math] S' [/math] мы получили последовательность работ [math] 1 \dots n [/math] (не теряя общности, занумеруем их от 1 до n). Распишем по определению значение целевой функции для [math] S [/math]:

   [math]\sum -w_i C_i = \sum \limits_{i=1}^n ( -w_i \sum \limits_{j=1}^i p_j ) = \\ \sum\limits_{i=1}^n ( w_i \sum\limits_{j=i+1}^n p_j ) - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\ \sum\limits_{i=1}^n ( w_i \sum\limits_{j=i}^n p_j ) - \sum\limits_{i=1}^n w_i p_i - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i [/math]

   Заметим, что первое слагаемое соответствует целевой функции [math] \sum w_i C_i [/math] для последовательности [math] n \dots 1 [/math], а второе и третье слагаемые — константы, зависящие только от начальных данных и не зависящие от перестановки работ. Таким образом, оптимальное

значение для [math] S' [/math] также минимизирует [math] S [/math], ч.т.д.