J2ni2Cmax

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

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

1. Дано [math]n[/math] работ и [math]2[/math] станка.
2. Для каждой работы известно её время выполнения на каждом станке.
3. Для каждой работы известна последовательность станков - порядок, в котором нужно выполнить работу. [math]1[/math].
4. Длина любой последовательности [math]\lt =2[/math].

Требуется минимизировать время окончания выполнения всех работ.

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

[math]M_{1}[/math] - первый станок. [math]M_{2}[/math] - второй станок.

Разобьем все работы на четыре множества:

1. [math]I_{1}[/math] - множество всех работ, которые должны выполнится только на [math]M_{1}[/math].
2. [math]I_{2}[/math] - множество всех работ, которые должны выполнится только на [math]M_{2}[/math].
3. [math]I_{12}[/math] - множество всех работ, которые должны выполнится сначала на [math]M_{1}[/math] затем на [math]M_{2}[/math].
4. [math]I_{21}[/math] - множество всех работ, которые должны выполнится сначала на [math]M_{2}[/math] затем на [math]M_{1}[/math].

Решим задачу [math]F2 \mid \mid C_{max}[/math] для [math]I_{12}[/math] и для [math]I_{21}[/math]. Получим расписание [math]S_{12}[/math] и [math]S_{21}[/math].

Тогда оптимальное расписание для нашей задачи будет следующим:

1. Расписание [math]M1[/math] : сначала [math]I_{12}[/math] в соответсвии с расписанием [math]S_{12}[/math]. Затем [math]I_{1}[/math] в произвольном порядке. Затем [math]I_{21}[/math] в соответсвии с [math]S_{21}[/math].
2. Расписание [math]M_{2}[/math] : сначала [math]I_{21}[/math] в соответсвии с расписанием [math]S_{21}[/math]. Затем [math]I_{2}[/math] в произвольном порядке. Затем [math]I_{12}[/math] в соответсвии с [math]S_{12}[/math].

Примечание: во время выполнения [math]I_{21}[/math] на [math]M_{1}[/math] или [math]I_{12}[/math] на [math]M_{2}[/math] могут возникнуть простои из-за того, что работа ещё не выполнилась на предыдущем станке.

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

[math]T_{i}(x)[/math] - время выполнения множества работ [math]x[/math] на станке [math]i[/math].

Лемма:

Расписание, построенное данным алгоритмом, обладает следующим свойством : один из станков работает без простоев.

Доказательство:

[math]\triangleright[/math]

Рассмотрим 2 варианта: [math]T_{1}(I_{12}) + T_{1}(I_{1}) \gt = T_{2}(I_{21}) [/math]. Тогда [math]M_{1}[/math] работает без прерываний, т.к к тому моменту завершения выполнения [math]I_{1}[/math] на [math] M_{1} [/math] все работы [math]I_{21}[/math] выполнены на [math]M_{2}[/math]. Иначе [math]T_{1}(I_{12}) + T_{1}(I_{1}) \lt T_{2}(I_{21}) [/math]. Тогда [math]M_{2}[/math] работает без прерываний, т.к к тому моменту завершения выполнения [math]I_{2}[/math] на [math] M_{2} [/math] все работы [math]I_{12}[/math] выполнены на [math]M_{1}[/math].

[math]\triangleleft[/math]

Теорема:

Расписание, построенное данным алгоритмом, является корректным и оптимальным.

Доказательство:

[math]\triangleright[/math]

Доказательство будем вести от противного. Рассмотрим расписание [math]S_{1}[/math], полученное после выполнения нашего алгоритма, и оптимальное расписание [math]S_{2}[/math]. Возьмём первый момент времени [math]t_{1}[/math], когда расписания различаются. Пусть в этот момент времени в [math]S_{1}[/math], будет выполняться работа с весом [math]w_{1}[/math], а в [math]S_{2}[/math] — работа с весом [math]w_{2}[/math]. Это первый момент, в котором расписания отличаются, значит в [math]S_{2}[/math] работа с весом [math]w_{1}[/math] выполнится в момент времени [math]t_{2} \gt t_{1}[/math]. Поменяем местами работы с весами [math]w_{1}[/math] и [math]w_{2}[/math] в [math]S_{2}[/math] и полуим расписание [math]S_{3}[/math]. Это возможно, потому что время появления этих работ не меньше [math]t_{1}[/math]. При такой перестановке ответы на задачу для [math]S_{2}[/math] и [math]S_{3}[/math] будут отличаться на [math]t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})[/math] Первая скобка отрицательная: [math]t_{1} \lt t_{2}[/math]. Вторая скобка тоже отрицательная из того, что в [math]S_{1}[/math] работа с весом [math]w_1[/math] выполняется раньше, значит её вес должен быть больше [math]w_2[/math]. Итого имеем, что ответ для [math]S_{2}[/math] больше, чем ответ для [math]S_{3}[/math]. Следовательно расписание [math]S_2[/math] неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание [math]S_{1}[/math] отличается от оптимального. Следовательно мы доказали, что оно оптимальное.

[math]\triangleleft[/math]

Псевдокод

  [math] S \leftarrow \{1 \dots n\}[/math]
  [math] time \leftarrow 0[/math]
  [math] answer \leftarrow 0[/math]
  while [math] S \neq \varnothing [/math]
     [math] j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})[/math]
     if [math]j \neq null [/math]
        [math] S \leftarrow S \setminus j[/math]
        [math] Answer \leftarrow Answer + time \cdot w_{j}[/math]
     [math] time++[/math]

Сложность алгоритма

Время работы алгоритма равно времени работы алгоритма [math]F2 \mid \mid C_{max}[/math].

Сложность алгоритма [math]O(n\log n)[/math].