O2Cmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
Строка 37: Строка 37:
  
 
==Псевдокод==
 
==Псевдокод==
  function scheduling(a: '''int'''[n], b: '''int[n]'''): '''pair<int[n], int[n]>'''
+
  '''function''' scheduling(a: '''int'''[n], b: '''int[n]'''): '''pair<int[n], int[n]>'''
 
     <tex>I = \varnothing </tex>
 
     <tex>I = \varnothing </tex>
 
     <tex>J = \varnothing </tex>
 
     <tex>J = \varnothing </tex>
 +
    '''pair<int[n], int[n]>''' ans
 
     <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \  \sum \limits_{i = 1}^{n} b_i, \  \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>
 
     <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \  \sum \limits_{i = 1}^{n} b_i, \  \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>
 
     '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
 
     '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
Строка 48: Строка 49:
 
     Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>
 
     Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>
 
     Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>
 
     Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>
     '''if''' <tex>a_{x} < b_{y}</tex>
+
     '''if''' <tex>a_{x} \geqslant b_{y}</tex>
        Поменять местами первый и второй станок
+
        Начиная с <tex>0</tex> на первом станке расставляем расписание для <tex>I \setminus \{x\}</tex>
        Пересчитать <tex>I, J, x</tex>
+
        Начиная с <tex>0</tex> на втором станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>I \setminus \{x\}</tex><br/>
        Запомнить, что поменяли
+
        От правой границы {{---}} <tex>C_{max}</tex> на первом станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>J</tex>
 
+
        От правой границы {{---}} <tex>C_{max}</tex> на втором станке расставляем расписание для <tex>J</tex><br/>
    Начиная с <tex>0</tex> на первом станке расставляем расписание для <tex>I \setminus \{x\}</tex>
+
        ans = пара из расписания для первого станка и расписания для воторого станка
    Начиная с <tex>0</tex> на втором станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>I \setminus \{x\}</tex><br/>
+
        '''return''' ans
    От правой границы {{---}} <tex>C_{max}</tex> на первом станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>J</tex>
+
    '''else'''
    От правой границы {{---}} <tex>C_{max}</tex> на втором станке расставляем расписание для <tex>J</tex><br/>
+
        ans = scheduling(b, a)
      '''if''' станки меняли местами
+
        Меняем местами расписания для станков в ans
        поменять их обратно
+
        '''return''' ans   
  
 
==Сложность алгоритма==
 
==Сложность алгоритма==

Версия 23:15, 16 мая 2016

[math]O2 \mid \mid C_{max}[/math]

Задача:
Рассмотрим задачу:
  • дано [math]n[/math] работ и [math]2[/math] станка,
  • для каждой работы известно её время выполнения на каждом станке.
Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.


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

Пусть [math]a_{i}[/math] — время выполнения [math]i[/math]-ой работы на первом станке, а [math]b_{i}[/math] — на втором.

  1. Разобьём все работы на два множества: [math]I = \{i \mid a_{i} \leqslant b_{i}; i = 1, \dots, n\}[/math] и [math]J = \{i \mid a_{i} \gt b_{i}; i = 1, \dots, n\}[/math].
  2. Найдем такие [math] x [/math] и [math] y [/math], что [math]a_{x} = \max \limits_{i \in I} \{a_{i}\}[/math] и [math]b_{y} = \max \limits_{i \in J} \{b_{i}\}[/math].
  3. Построим оптимальное значение целевой функции: [math]C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i,\ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}[/math].
  4. Рассмотрим два случая. Первый случай, когда [math]a_{x} \gt b_{y}[/math] (он показан на рисунке ниже). Будем строить расписание с двух концов:
    • Строим расписание слева: выполняем на первом станке все работы из [math]I \setminus \{x\}[/math], а на втором выполняем первой работу [math]x[/math], затем [math]I \setminus \{x\}[/math].
    • Теперь, упираясь в правую границу, равную [math] C_{max} [/math], можно построить расписание справа: выполняем на первом станке все работы из [math]J[/math], затем [math]x[/math], а для второго выполняем работы из [math]J[/math].
Второй случай сводится к первому: все работы и станки меняются местами, и решается задача для первого случая.
Picture2.gif

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

Теорема:
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
Доказательство:
[math]\triangleright[/math]

Чтобы доказать корректность, надо доказать, что на каждом станке в любой момент времени выполняется не более одной работы, и что каждая работа в каждый момент времени выполняется не более, чем на одном станке.
Первое утверждение вытекает из того, что мы строили расписание, опираясь на [math]C_{max}[/math]. Из построения [math]C_{max} \geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}[/math], следовательно на каждом станке в любой момент времени выполняется не более одной работы.
Докажем теперь второе утверждение. У нас имеется 3 блока работ: [math] I \setminus \{x\}, \{x\}, J[/math].

  1. Для блока [math] \{x\}[/math] это следует из того, что [math] C_{max} \geqslant a_{x}+b_{x}[/math], а работа [math] x [/math] выполняется с разных концов станков. Получили, что отрезки выполнения работы [math] x [/math] на разных станках не пересекаются.
  2. Покажем, что любая работа из [math] I \setminus \{x\}[/math] начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
    [math]\sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}[/math], где [math]1 \dots k[/math] — это работы, выполняемые на первом станке во время данного блока.
    Это неравенство следует из выбора [math]I[/math] и из того, что [math]b_{x} \geqslant a_{x} \geqslant a_{i}, \forall i \in I[/math].
    Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.
  3. Покажем, что любая работа из [math]J[/math] начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
    [math]\sum \limits_{i = 1}^k b_{i} \leqslant \sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}[/math], где [math]1 \dots k[/math] — это работы, выполняемые на втором станке во время данного блока.

Это неравенство следует из выбора [math]J[/math] и из того, что [math]a_{x} \geqslant a_{i}, \forall i \in I[/math]. Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.

Итого мы доказали корректность.

Оптимальность вытекает из того, что [math]C_{max}[/math] не может быть меньше [math]\sum \limits_{i = 1}^{n} a_i,\ \sum \limits_{i = 1}^{n} b_i, \ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}[/math], а из построения оно равно максимуму из этих значений.
[math]\triangleleft[/math]

Псевдокод

function scheduling(a: int[n], b: int[n]): pair<int[n], int[n]>
    [math]I = \varnothing [/math]
    [math]J = \varnothing [/math]
    pair<int[n], int[n]> ans
    [math]C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \  \sum \limits_{i = 1}^{n} b_i, \  \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}[/math]
    for [math]i = 1[/math] to [math]n[/math]
       if [math]a_{i} \leqslant b_{i}[/math]
          [math] I = I \cup \{i\} [/math]
       else
          [math] J = J \cup \{i\} [/math]
    Найти [math]x[/math], где [math]a_{x} = \max \limits_{i \in I} \{a_{i}\}[/math]
    Найти [math]y[/math], где [math]b_{y} = \max \limits_{i \in J} \{b_{i}\}[/math]
    if [math]a_{x} \geqslant b_{y}[/math]
        Начиная с [math]0[/math] на первом станке расставляем расписание для [math]I \setminus \{x\}[/math]
        Начиная с [math]0[/math] на втором станке расставляем расписание для [math]\{x\}[/math], затем для [math]I \setminus \{x\}[/math]
От правой границы — [math]C_{max}[/math] на первом станке расставляем расписание для [math]\{x\}[/math], затем для [math]J[/math] От правой границы — [math]C_{max}[/math] на втором станке расставляем расписание для [math]J[/math]
ans = пара из расписания для первого станка и расписания для воторого станка return ans else ans = scheduling(b, a) Меняем местами расписания для станков в ans return ans

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

Каждое из множеств в сумме содержит [math]n[/math] элементов. Следовательно, чтобы найти максимум в каждом из множеств нам потребуется [math]O(n)[/math] операций, чтобы составить расписание для каждой работы из множества нам потребуется так же [math]O(n)[/math] операций. Получаем сложность алгоритма [math]O(n)[/math].

См. также

Источники информации

  • Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 158-160 ISBN 978-3-540-69515-8