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} \ge b_{y}[/math], тогда
   • Выполняем все работы на первом станке в следующем порядке: сперва все работы из [math]I \setminus \{x\}[/math], затем из [math]J[/math] и последней работу [math]x[/math]
   • На втором станке выполняем первой работу [math]x[/math]
   • Остальные работы выполняем на втором станке в порядке их завершения на первом тогда, когда второй станок свободен, а работа на первом уже выполнена

   Второй случай рассматривается аналогично: первый и второй станок меняются местами, и вместо [math]x[/math] — работа [math]y[/math]