Задачи календарного планирования

       Определить  такую очередность запуска деталей  в обработку, при которой минимизируется суммарное время завершения всех работ T_ц.

       Можно показать, что в задаче трех станков  очередность выполнения первых, вторых и третьих операций в оптимальном решении может быть одинаковой (для четырех станков это свойство уже не выполняется). Поэтому достаточно определить очередность запуска только на одном станке (например, третьем).

       Обозначим s_k = (i₁, i₂ , ..., i_k) — некоторую последовательность очередности запуска длиной k (1 £ k £ п) и A (s_k), В (s_k), С (s_k) — время окончания обработки последовательности деталей s_k на первом, втором и третьем станках соответственно.

       Необходимо  найти такую последовательность s_опт, что

С(s_опт) = min С (s).

     s

      Покажем, как можно рекуррентно вычислять  A (s_k), В (s_k), С (s_k). Пусть s_k+1 = (s_k ,i_k+i), т. е. последовательность деталей s_k+1 получена из деталей s_k с добавлением еще одной детали i_k+1.

        Тогда

A (s_k+1) = A (s_k)+ , 

В (s_k+1) = max [A (s_k+1);  В (s_k)] + ,   

С (s_k+1) = max [В (s_k+1); С (s_k)] +  

Для задачи трех станков можно использовать следующее правило доминирования .

Если  s — некоторая  начальная  последовательность,   а — под последовательность образованная из s перестановкой некоторых символов, то вариант s доминирует над , когда выполняются следующие неравенства: 

А (s) £ А ( ),     В (s) £ В ( ),    С (s) £ С ( ), 

причем  хотя бы одно из них  выполняется как  строгое неравенство.

       Способ  конструирования вариантов после- 
довательностей s и вычисления оценок D(s) для каждого из них состоит в следующем.

       Пусть имеется начальная подпоследовательность s. Тогда вычисляются величины:

d_C(s) = С(s) + ,                     (1)

d_B(s) = В (s) + +  min c_j , (2)

d_A(s) = A (s) +   +  (3)

где J (s) — множество символов,  образующих последовательность s.

За оценку критерия С (s) для варианта s можно принять величину

D(s) = max {d_A(s), d_B (s), d_C (s)}.    (4)

Тогда ход решения задачи трех станков можно представить следующей формальной схемой.

Нулевой шаг. Задание множества G⁽⁰⁾, образуется всеми возможными последовательностями (s = 0).

Вычисление  оценки для множества G₀:

где   D(0) = max {d_A(0), d_B (0), б_C (0)},

;  ;  .

Первый  шаг. Образование    множеств    G₁⁽¹⁾ U G₁⁽²⁾ U... …G₁⁽ⁿ⁾.

Подмножество  G_k определяется всеми последовательностями с началом

 i_k(k — 1, ...,n ).

Вычисление  оценок. Оценку для последовательности s_k определяют из соотношения (4), т. е.

   D(s_k) = max {d_A(s_k), d_B (s_k), d_C (s_k)};  k = 1, n.

Выбор варианта для продолжения. Из всех подпоследовательностей, построенных на предыдущем шаге, выбирают наиболее перспективную последовательность s_k с наименьшей оценкой, т. е.

D(s_k⁽¹⁾)=min D(s_j⁽¹⁾).

Ветвление. Выбрав наиболее перспективный вариант последовательности s_k⁽¹⁾, развивают его построением всех возможных подпоследовательностей длиной 2 с началом  s_k⁽¹⁾ вида   s_k+1⁽²⁾= (s_k⁽¹⁾, j), где j не входит в s_k.

Вычисление  оценок производят в соответствии с  соотношениями (1), (2), (3).

k - ш а г. Допустим, что уже проведено k шагов, в результате чего построены варианты s₁^(k), s₂^(k) ,…,s_vk^(k), а именно подпоследовательности длиной k.

Выбираем  самый перспективный вариант s_S^(k) такой, что

D(s_s^(k))=min D(s_j^(k)).

Множество G_s^(k) разбиваем на (п — k) подмножеств, каждое из которых образуется добавлением к последовательности s_s^(k) некоторого элемента i_k+1 такого, что i_k+1 .

Оценка  определяется в соответствии с соотношениями (1) — (4).

В результате строим дерево вариантов следующего вида: вершина О отвечает s = 0, вершины первого уровня G₁⁽¹⁾, G₂⁽¹⁾..., G_n⁽¹⁾ соответствуют последовательностям длиной 1, т. е. s₁⁽¹⁾ = 1, s₂⁽¹⁾ = 2,..., s_n⁽¹⁾ = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины п.

Признак оптимальности. Если s_v⁽ⁿ⁾  отвечает конечной вершине дерева, причем оценка наименьшая из оценок всех вершин, то s_v⁽ⁿ⁾ — искомый вариант, иначе переходим к продолжению варианта с наименьшей оценкой. 

Пример. Рассмотрим задачу трех станков, условия которой приведены

 в  табл. 1: 

Таблица 1

 
 

Нулевой шаг. s = 0.

d_A(s = 0) = A(0) +   +   = 0 + 14 + 3 = 17;

d_B(s = 0) = В(0) + +  min c_j = 0 + 15 + 2 = 17;

d_C(s = 0) = С(0) + =14 . 

Тогда

∆ (s = 0) = max {17, 17,14} = 17. 
 
 

Первый  шаг. Конструируем все возможные последовательности длиной 1

s₁⁽¹⁾  = 1;  s₂⁽¹⁾ = 2;   s₃⁽¹⁾ = 3;   s₄⁽¹⁾ = 4;   s₅⁽¹⁾ = 5. 

Находим

    d_A⁽¹⁾  = A₁  +

  +   = 14 + 3 = 17;

    d_B⁽¹⁾(s = 0) = В₁ +

+   = 5 + 12 + 2 = 19;

d_C⁽¹⁾ = С₁ +

= 9 + 10 = 19 . 

Откуда  ∆ (1) = max {17, 19, 19} = 19.

Аналогично  определяем ∆ (2), ∆ (3), ∆ (4), ∆ (5).  

 

Второй  шаг. Среди множества подпоследовательностей длиной 1, s₁⁽¹⁾ = 1, s₂⁽¹⁾ = 2,..., s₅⁽¹⁾  = 5  выбираем наиболее перспективную s = 1, для которой величина оценки-прогноза ∆ (s) оказывается наименьшей. Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2), (1.3), (1.4), (1.5).

Для каждого  из этих вариантов вновь определяем оценки по формулам (1) — (4).

Процесс вычислений продолжаем аналогично.

Процесс построения дерева вариантов приведен на рис. 1.