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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»)
 
(Постановка задачи)
Строка 9: Строка 9:
 
</ol>
 
</ol>
 
Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.
 
Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.
 +
 +
== Описание алгоритма ==
 +
Пусть <tex>a_{i}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>b_{i}</tex> {{---}} на втором.<br/>
 +
<ol>
 +
<li>Разобьём все работы на два множества: <tex>I = \{i \mid a_{i} \le b_{i}; i = 1, \dots, n\}</tex> и <tex>J = \{i \mid a_{i} > b_{i}; i = 1, \dots, n\}</tex></li>
 +
<li>Найдем <tex>a_{x} = max \{a_{i} \mid i \in I\}</tex> и <tex>b_{y} = max \{b_{i} \mid i \in J\}</tex> </li>
 +
<li> Рассмотрим 2 случая. Первый случай, когда <tex>a_{x} \ge b_{y}</tex>, тогда
 +
<ul>
 +
<li>Выполняем все работы на первом станке в следующем порядке: сперва все работы из <tex>I \setminus \{x\}</tex>, затем из <tex>J</tex> и последней работу <tex>x</tex></li>
 +
<li>На втором станке выполняем первой работу <tex>x</tex></li>
 +
<li>Остальные работы выполняем на втором станке в порядке их завершения на первом тогда, когда второй станок свободен, а работа на первом уже выполнена</li>
 +
</ul>
 +
Второй случай рассматривается аналогично: первый и второй станок меняются местами, и вместо <tex>x</tex> {{---}} работа <tex>y</tex>
 +
</li>
 +
</ol>

Версия 01:08, 9 июня 2012

Эта статья находится в разработке!


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

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

  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]