Задача одного станка

На одном станке нужно обработать n деталей. Время обработки k-той детали T_k. Штраф за простой детали в очереди  a_k. Требуется установить очередность обработки деталей такую, чтобы  общий штраф был минимален.

Т=S_k T_k

Величина штрафа зависит от очередности t_k(S_n)-время ожидания обработки детали номер k при очередности заданной перестановкой S_n.

S_n=<[1],[2],...,[k],...,[n]>

[k]-число стоящее на k-м месте перестановки.

S_n=<3,1,4,2>   [1]=3  [2]=1  [3]=4  [4]=2

t_k(S_n)=t_k-1(S_n)+T[k-1]

T₁(S_n)=0, T[k-1]- продолжительность обработки k-1 детали Т.о. задача состоит в определении перестановки S_n, при которой

     f(S_n)=Sa_kt_k(S_n)  будет min.

Вместо прямого перебора используют т.н. решающие правила, которые позволяют найти оптимальное решение без перебора. Для задачи одного станка оно гласит:

Перестановка S_n=<[1],...[r],...[n]> является оптимальной, если выполнено условие

   a[1]/T[1]>=a[2]/T[2]>=...a[n]/T[n]

1.Вычисляем для каждой детали а[k]/T[k]

2.Упорядочиваем элементы линейной последовательности в порядке убывания a[k]/T[k]

3. Печатаем номера деталей [1],[2],...

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

проводим методом перестановки соседних элементов. Пусть S_n=<[1],[2],...[i],[j],... [n]>- оптимальное решение. Поменяем местами  i и j , это дает S_n=<[1]<[2],...[j],[i],...n>.

Для оптимального решения f(S_n)<=f(S_n). Пусть t- время начала обработки i-то детали в перестановке i-той детали в S_n, j-той детали в S_n. Тогда

  f(S_n)=C+a_it+a_j(t-T_i)

f(S_n)=C+a_jt+a_i(t+T_j)

Подставляя это в неравенство, получаем

a_it+a_j(t+T_i)<=a_jt+a_i(t+T_j), отсюда следует ,что a_jT_i<=a_iT_j.

Так как T_k>0 для всех к, то можно поделить на Т. Получаем

a_i/T_i>=a_j/T_i-оптимальная последовательность.