J2ni2Cmax

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

  1. Дано [math]n[/math] работ и [math]2[/math] станка.
  2. Для каждой работы известно её время выполнения на каждом станке [math]p_{i}[/math].
  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]M_{1}[/math] работает без прерываний. Рассмотрим станок на котором достигается [math]C_{max}[/math] . Если это [math]M_{1}[/math], то оптимальность очевидна([math]C_{max} \gt = \sum\limits_{i \in I_{1} \cup I_{12} \cup I_{21}} p_i [/math]) Иначе [math]C_{max}[/math] достигается на [math]M_{2}[/math].

    Тогда ответ равен решению задачи f2cmax для работ [math]I_{21}[/math], который оптимален.
    [math]\triangleleft[/math]

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

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

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