O2Cmax

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

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

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

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

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

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

1. Разобьём все работы на два множества: [math]I = \{i \mid a_{i} \le b_{i}; i = 1, \dots, n\}[/math] и [math]J = \{i \mid a_{i} \gt b_{i}; i = 1, \dots, n\}[/math]
2. Найдем [math]a_{x} = \max \{a_{i} \mid i \in I\}[/math] и [math]b_{y} = \max \{b_{i} \mid i \in J\}[/math]
3. Рассмотрим 2 случая. Первый случай, когда [math]a_{x} \le b_{y}[/math]. Будем строить расписание с двух концов:
   • Строим расписание слева: выполняем на первом станке все работы из [math]I \setminus \{x\}[/math], а на втором выполняем первой работу [math]x[/math], затем [math]I \setminus \{x\}[/math].
   • Теперь, упираясь в левую границу, можно построить расписание справа: выполняем на первом станке все работы из [math]J[/math], затем [math]x[/math], а для второго выполняем работы из [math]J[/math]

   Второй случай рассматривается аналогично: все работы и станки меняются местами.

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

Теорема:

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

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

[math]\triangleright[/math]

Для доказательства оптимальности полученного расписания рассмотрим только первый случай. Второй доказывается аналогично. Рассмотрим 3 последовательности выполнения работы, начиная с нулевого времени: все работы на первом станке, все работы на втором станке и первая работа на втором станке плюс последняя - на первом. Докажем, что время окончания одной из этих трёх последовательностей максимальное из всех возможных окончаний. Пронумеруем работы в порядке выполнения их на первом станке и рассмотрим последовательность [math]0 \rightarrow a_{1} \rightarrow \dots \rightarrow a_{i} \rightarrow b_{i} \rightarrow \dots \rightarrow b_{n-1}[/math] Если [math]i \in I[/math], то [math]\sum \limits _{j = 1}^{i}a_{j} + \sum\limits_{j = i}^{n -1}b_{j} \le \sum\limits_{j = 1}^{i-1}b_{j} +a_{i}+ \sum\limits_{j = i}^{n -1}b_{j}[/math] Это неравенство получаем из первого случая и того, что [math]i \in I \Rightarrow \ \forall j \lt i, j \in I \Rightarrow \forall j \lt i, a_{j} \le b_{j}[/math] [math]\sum \limits_{j = 1}^{i-1}b_{j} +a_{i}+ \sum\limits_{j = i}^{n -1}b_{j} \le \sum \limits_{j = 1}^{n} b_{j}[/math] Это неравенство получено из того, что [math]a_{i} \le a_{n} \le b_{n}[/math], где [math]n = x[/math] Если [math]i \in J[/math], то [math]\sum \limits _{j = 1}^{i}a_{j} + \sum\limits_{j = i}^{n -1}b_{j} \le \sum\limits_{j = 1}^{i}a_{j} +b_{i}+ \sum\limits_{j = i+1}^{n -1}a_{j}[/math] Это неравенство получаем из первого случая и того, что [math]i \in J \Rightarrow \ \forall j \gt i, j \in I \Rightarrow \forall j \gt i, b_{j} \le a_{j}[/math] [math]\sum \limits_{j = 1}^{i}a_{j} +b_{i}+ \sum\limits_{j = i+1}^{n -1}a_{j} \le \sum \limits_{j = 1}^{n} a_{j}[/math] Это неравенство получено из того, что [math]b_{i} \le a_{i} \le a_{n}[/math], где [math]n = x[/math] Три последовательности выполнения работ, которые мы рассмотрели вначале, являются нижней оценкой для OpenShop problem, следовательно они и дают оптимальное решение.

[math]\triangleleft[/math]

Псевдокод

  [math]I \leftarrow \varnothing [/math]
  [math]J \leftarrow \varnothing [/math]
  for [math]i = 1 \dots n[/math]
     if [math]a_{i} \le b{i}[/math]
        [math] I \leftarrow I \cup \{i\} [/math]
     else
        [math] J \leftarrow 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} \lt  b_{y}[/math]
     Поменять местами первый и второй станок
     Пересчитать [math]I, J, x[/math]
     Запомнить, что поменяли
  
  [math]time1 \leftarrow 0[/math]
  shed2[x] [math]\leftarrow 0[/math]
  [math]time2 \leftarrow b_{x}[/math]
  
  Для всех [math]i \in I \setminus \{x\}[/math]
     sched1[i] [math]\leftarrow time1[/math]
     [math]time1 \leftarrow time1 + a_{i}[/math]
     [math]time2 \leftarrow \max\{time1, time2\}[/math]
     sched2[i] [math]\leftarrow time2[/math]
     [math]time2 \leftarrow time2 + b_{i}[/math]
  
  Для всех [math]i \in J[/math]
     sched1[i] [math]\leftarrow time1[/math]
     [math]time1 \leftarrow time1 + a_{i}[/math]
     [math]time2 \leftarrow \max\{time1, time2\}[/math]
     sched2[i] [math]\leftarrow time2[/math]
     [math]time2 \leftarrow time2 + b_{i}[/math]
  
  [math]time1 \leftarrow \max\{time1, b_{x}\}[/math]
  sched1[x] [math]\leftarrow time1[/math]
  [math]time1 \leftarrow time1 + a_{x}[/math]
  
  [math]C_{max} \leftarrow \max\{time1, time2\}[/math]
  if станки меняли местами
     поменять их обратно

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

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