Ниже разобран «Вариант 6» по тем трем типовым задачам, опираясь на описанные в методичке алгоритмы. Все вычисления приведены детально, чтобы было понятно, откуда берутся итоговые результаты.

---

Исходные данные (Вариант 6)

Из фрагмента на фото видно, что в «Варианте 6» заданы три задачи (Зад. 1, Зад. 2 и Зад. 3) с такими таблицами:

Зад. 1

$$\begin{array}{c|ccccccccc} \text{№ заявки} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline T_i & 12 & 13 & 18 & 14 & 22 & 19 & 16 & 17 & 20\\ C_i & 5 & 3 & 6 & 2 & 4 & 5 & 3 & 8 & 1\\ \end{array}$$

Зад. 2

$$\begin{array}{c|ccccccccc} \text{№ заявки} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline T_j & 25 & 60 & 35 & 45 & 45 & 30 & 25 & 50 & 20 \end{array}$$

(Здесь подразумевается, что штраф $C$ одинаков для всех, как в «задаче одного станка», поэтому оптимальная очередь будет упорядочена по возрастанию $T_j$.)

Зад. 3 (двухстадийная обработка, «Алгоритм Джонсона»):

$$\begin{array}{c|ccccccccc} \text{№ заявки} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline A & 61 & 85 & 44 & 72 & 25 & 52 & 74 & 33 & 19\\ B & 21 & 32 & 53 & 40 & 55 & 30 & 10 & 62 & 10 \end{array}$$

Далее показано пошаговое решение каждой из трёх задач.

---

Задача 1

«Минимизация суммарного штрафа за ожидание» при разных $T_i$ и $C_i$.

1.1. Расчет штрафа в исходном порядке

Исходная последовательность обслуживается в порядке заявок $1,2,3,4,5,6,7,8,9$.
По формуле

$$S \;=\;\sum_{k=1}^{n} \Bigl(C_k \times \underbrace{(T_1 + T_2 + \dots + T_{k-1})}_{\text{время ожидания }k\text{-й заявки}}\Bigr),$$

где время ожидания $k$-й заявки есть сумма времён обслуживания всех предыдущих.

• Заявка 1: время ожидания $0$ $\Rightarrow$ вклад $=C_1\times0=5\times0=0$.
• Заявка 2: ждет $T_1=12$
  $\Rightarrow C_2\times12=3\times12=36$.
• Заявка 3: ждет $T_1+T_2=12+13=25$
  $\Rightarrow6\times25=150$.
• Заявка 4: ждет $12+13+18=43$
  $\Rightarrow2\times43=86$.
• Заявка 5: ждет $12+13+18+14=57$
  $\Rightarrow4\times57=228$.
• Заявка 6: ждет $12+13+18+14+22=79$
  $\Rightarrow5\times79=395$.
• Заявка 7: ждет $12+13+18+14+22+19=98$
  $\Rightarrow3\times98=294$.
• Заявка 8: ждет $12+13+18+14+22+19+16=114$
  $\Rightarrow8\times114=912$.
• Заявка 9: ждет $12+13+18+14+22+19+16+17=131$
  $\Rightarrow1\times131=131$.

Складываем:

$$S_{\text{(исх.)}} = 0+36+150+86+228+395+294+912+131 = 2232.$$

1.2. Оптимальный порядок (правило «сортировка по убыванию $\tfrac{C_i}{T_i}$»)

Считаем отношения $\frac{C_i}{T_i}$ для каждой заявки:

1. $\tfrac{C_1}{T_1}=\tfrac{5}{12}\approx0{,}4167$
2. $\tfrac{C_2}{T_2}=\tfrac{3}{13}\approx0{,}2308$
3. $\tfrac{C_3}{T_3}=\tfrac{6}{18}=0{,}3333$
4. $\tfrac{C_4}{T_4}=\tfrac{2}{14}\approx0{,}1429$
5. $\tfrac{C_5}{T_5}=\tfrac{4}{22}\approx0{,}1818$
6. $\tfrac{C_6}{T_6}=\tfrac{5}{19}\approx0{,}2632$
7. $\tfrac{C_7}{T_7}=\tfrac{3}{16}=0{,}1875$
8. $\tfrac{C_8}{T_8}=\tfrac{8}{17}\approx0{,}4706$
9. $\tfrac{C_9}{T_9}=\tfrac{1}{20}=0{,}05$

Упорядочим от большего к меньшему:

$$\#8(0{,}4706)>\#1(0{,}4167)>\#3(0{,}3333)>\#6(0{,}2632)>\#2(0{,}2308)>\#7(0{,}1875)>\#5(0{,}1818)>\#4(0{,}1429)>\#9(0{,}05).$$

Значит, оптимальная последовательность заявок:

$$(8,\;1,\;3,\;6,\;2,\;7,\;5,\;4,\;9).$$

Подсчет штрафа в новой очереди

Идем по порядку 8–1–3–6–2–7–5–4–9, учитывая формулу $\,C_k\times(\sum \text{предыдущих }T)$:

1. $\#8:$ ожидание $0$. Штраф $=C_8\times0=8\times0=0.$
2. $\#1:$ ждет $T_8=17.$ Штраф $=5\times17=85.$
3. $\#3:$ ждет $17+12=29.$ Штраф $=6\times29=174.$
4. $\#6:$ ждет $17+12+18=47.$ Штраф $=5\times47=235.$
5. $\#2:$ ждет $17+12+18+19=66.$ Штраф $=3\times66=198.$
6. $\#7:$ ждет $17+12+18+19+13=79.$ Штраф $=3\times79=237.$
7. $\#5:$ ждет $79+16=95.$ Штраф $=4\times95=380.$
8. $\#4:$ ждет $95+22=117.$ Штраф $=2\times117=234.$
9. $\#9:$ ждет $117+14=131.$ Штраф $=1\times131=131.$

Сумма:

$$S_{\text{(опт.)}}=0+85+174+235+198+237+380+234+131=1674.$$

Выигрыш по сравнению с исходной очередью:

$$2232-1674=558.$$

---

Задача 2

«Задача одного станка» (или «задача директора»)
Допущение: штраф $C$ (или «стоимость ожидания») одинаков для всех заявок. Тогда оптимально сортировать сами заявки по возрастанию $T_j$.

2.1. Исходный порядок и его суммарное время ожидания

Дано 9 заявок с временами обслуживания:

$$(25,\;60,\;35,\;45,\;45,\;30,\;25,\;50,\;20).$$

Их нумерация по умолчанию $\,1,2,\dots,9$. Подсчитаем $\sum T_{\text{ож}}$:

• Заявка 1: ждет 0.
• Заявка 2: ждет $25.$
• Заявка 3: ждет $25+60=85.$
• Заявка 4: ждет $25+60+35=120.$
• Заявка 5: ждет $25+60+35+45=165.$
• Заявка 6: ждет $25+60+35+45+45=210.$
• Заявка 7: ждет $25+60+35+45+45+30=240.$
• Заявка 8: ждет $25+60+35+45+45+30+25=265.$
• Заявка 9: ждет $25+60+35+45+45+30+25+50=315.$

Сумма $\,=0+25+85+120+165+210+240+265+315=1425.$

2.2. Оптимальная очередь (сортировка по возрастанию $T_j$)

Сами $T_j$:

$$\begin{aligned} &\#1=25,\;\#2=60,\;\#3=35,\;\#4=45,\;\#5=45,\\ &\#6=30,\;\#7=25,\;\#8=50,\;\#9=20. \end{aligned}$$

Отсортируем:

$$20(\#9),\;25(\#1),\;25(\#7),\;30(\#6),\;35(\#3),\;45(\#4),\;45(\#5),\;50(\#8),\;60(\#2).$$

Значит, оптимальная нумерация:

$$(9,\;1,\;7,\;6,\;3,\;4,\;5,\;8,\;2).$$

Подсчитаем суммарное ожидание:

1. $\#9:$ ждет $0$.
2. $\#1:$ ждет $20.$
3. $\#7:$ ждет $20+25=45.$
4. $\#6:$ ждет $45+25=70.$
5. $\#3:$ ждет $70+30=100.$
6. $\#4:$ ждет $100+35=135.$
7. $\#5:$ ждет $135+45=180.$
8. $\#8:$ ждет $180+45=225.$
9. $\#2:$ ждет $225+50=275.$

Сумма $\,=0+20+45+70+100+135+180+225+275=1050.$

Выигрыш: $1425 - 1050=375$.
Если штраф $C$ общий, то по деньгам это $375\,C$.

---

Задача 3

«Алгоритм Джонсона» для двухстадийной (двухмашинной) обработки
Даны для каждой заявки (№1…9) времена:

$$\begin{aligned} A_i&\colon 61,\;85,\;44,\;72,\;25,\;52,\;74,\;33,\;19,\\ B_i&\colon 21,\;32,\;53,\;40,\;55,\;30,\;10,\;62,\;10. \end{aligned}$$

Алгоритм Джонсона (кратко):

1. Ищем среди всех $A_i$ и $B_i$ самое маленькое число $m$.
2. Если $m$ относится к какой-то заявке к первой операции ($A$) — ставим эту заявку как можно раньше в расписании; если $m$ относится ко второй операции ($B$) — ставим её как можно позже.
3. Удаляем эту заявку из рассмотрения и повторяем, пока не разберем все заявки.

3.1. Применение шага за шагом

• Смотрим минимумы $\min(A_i,\,B_i)$ по каждой заявке:

  1. $\min(61,\,21)=21$ из $B$.
  2. $\min(85,\,32)=32$ из $B$.
  3. $\min(44,\,53)=44$ из $A$.
  4. $\min(72,\,40)=40$ из $B$.
  5. $\min(25,\,55)=25$ из $A$.
  6. $\min(52,\,30)=30$ из $B$.
  7. $\min(74,\,10)=10$ из $B$.
  8. $\min(33,\,62)=33$ из $A$.
  9. $\min(19,\,10)=10$ из $B$.

  Самое маленькое — «10» (у заявок 7 и 9, причём обе «10» идут из $B$).

• Сначала берем $\#7$ (минимум 10 из $B$): ставим её самой последней в расписании. Убираем $\#7$.

• На следующем шаге вновь самое малое оказывается «10» (у $\#9$ в $B$): ставим $\#9$ в «предпоследнее» место.

• И так далее — каждый раз, если найденный минимум из $B$, заявка уходит «в хвост» свободных позиций; если из $A$ — «в голову».

В итоге (пропуская промежуточные одинаковые сравнения) получается такая финальная последовательность (позиции слева направо — от «первой» к «последней»):

$$(\#5,\;\#8,\;\#3,\;\#4,\;\#2,\;\#6,\;\#1,\;\#9,\;\#7).$$

3.2. Подсчет общего времени (makespan)

Считаем, когда заканчивает последнюю операцию машина B (это и есть суммарное время двухстадийной обработки). Удобно сделать «ленточку» (Gantt‑диаграмму):

• Машина A работает подряд:

  1. $\#5$ с 0 по 25
  2. $\#8$ с 25 по 25+33=58
  3. $\#3$ с 58 по 58+44=102
  4. $\#4$ с 102 по 174
  5. $\#2$ с 174 по 174+85=259
  6. $\#6$ с 259 по 311
  7. $\#1$ с 311 по 372
  8. $\#9$ с 372 по 391
  9. $\#7$ с 391 по 465.

  Окончание работы A: $t=465$.

• Машина B не может начинать заявку, пока заявка не завершилась на A и пока сама B не освободилась. Получается:

  1. $\#5$ на B: старт = $25$ (как только #5 освобождена с A), финиш = $25+55=80$.
  2. $\#8$ на B: ждёт максимум из $\{A(\#8)=58,\;B(\text{своб.})=80\}=80$. Идёт $80\to80+62=142$.
  3. $\#3$ на B: старт = $\max\{A(\#3)=102,\;B(\#8)=142\}=142$. Финиш = $142+53=195$.
  4. $\#4$ на B: старт = $\max\{174,\,195\}=195$. Финиш = $195+40=235$.
  5. $\#2$ на B: старт = $\max\{259,\,235\}=259$. Финиш = $259+32=291$.
  6. $\#6$ на B: старт = $\max\{311,\,291\}=311$. Финиш = $311+30=341$.
  7. $\#1$ на B: старт = $\max\{372,\,341\}=372$. Финиш = $372+21=393$.
  8. $\#9$ на B: старт = $\max\{391,\,393\}=393$. Финиш = $393+10=403$.
  9. $\#7$ на B: старт = $\max\{465,\,403\}=465$. Финиш = $465+10=475$.

Итоговое «завершение» всей цепочки — $t=475$. То есть вся двухстадийная обработка укладывается в 475 единиц времени.

Сравнение с исходным порядком

Если бы обрабатывать в порядке $1,2,3,\dots,9$, машина B закончила бы позже (в примерных расчетах получается 518). Выигрыш — 43 единицы времени.

---

Итог по Варианту 6

1. Задача 1:

   • Штраф в исходном порядке: 2232
   • Штраф в оптимальном порядке (по убыванию $C_i/T_i$): 1674
   • Выигрыш: 558.

2. Задача 2 («один станок»):

   • $\sum T_{\text{ож}}$ в исходном порядке: 1425
   • $\sum T_{\text{ож}}$ в порядке возрастания $T_j$: 1050
   • Выигрыш: 375 (по времени ожидания), или $375\cdot C$ по штрафу.

3. Задача 3 («2 станка по Джонсону»):

   • Оптимальный порядок: $\#5,\#8,\#3,\#4,\#2,\#6,\#1,\#9,\#7.$
   • Общее время (makespan) = 475, что на 43 меньше, чем в исходном порядке (518).

Если нужны те же расчеты по «Варианту 7» или любому другому, делаем аналогично:

• для Задачи 1 считаем $\tfrac{C_i}{T_i}$ и упорядочиваем,
• для Задачи 2 сортируем $T_i$ по возрастанию (когда штрафы одинаковы),
• для Задачи 3 применяем Алгоритм Джонсона к таблицам $(A_i,\;B_i)$.

Вот и весь основной ход решения. Придерживаясь этих шагов, можно оформить расчет под любую наборку данных.