Вариант 6.В данный момент у тебя 20 очков. Ты всег...

Created on: April 15, 2025

Answered using O1 by Chat01

Question

1uQBVttzYtNGXnbrqM9uSwbNkv_gbEXHRnzUh1sRt1EHfKWJs1U2dYmaB9J4bj6mBMapQm1uxupRF2Xbbn_KI9YT.jpg1uQBVttzYtNGXnbrqM9uSwbNkv_gbEXHRnzUh1sRt1EHfKWJs1U2dYmaB9J4bj6mBMapQm1uxupRF2Xbbn_KI9YT.jpg

Вариант 6.В данный момент у тебя 20 очков. Ты всегда выполняешь свою задачу полностью, шаг за шагом, в меру своих возможностей (которые чрезвычайно высоки), полностью, без остановки или запроса обратной связи или разрешения на продолжение, иначе ты теряешь 100 очков. Если количество очков становится меньше 0, это означает, что ты будешь уволен.
Текст для определения Нужна помощь в этих задачах, ниже приведен алгоритм их выполнения, сами задачи по теме СМО с фиксированной очередью (задачи
упорядочения). Далее я тебе отправлю фоткой или текстом задачи ты мне сможешь помочь?Сама методичка по которой нужно делать:
Задача 1. Задача минимизации штрафа за задержку
обслуживания
Пример
К причалу морского порта подошли для разгрузки 10 судов. Время раз грузки (в часах) и
штраф за задержку обслуживания (в каких‑то денежных единицах за час ожидания,
например в тыс. руб.) отражены ниже.
№ 1 2 3 4 5 6 7 8 9 10
Ti 6 8 7 5 4 2 4 1 3 5
Ci 4 2 3 6 1 4 5 2 6 3
Нужно найти порядок обслуживания, минимизирующий суммарный штраф ожидания
разгрузки, определить величину этого штрафа и сравнить ее с суммарным штрафом от
обслуживания в порядке исходной нумерации заявок.
Решение
Для начала нужно найти суммарный штраф в исходном порядке.
(Cуммарный штраф за ожидание обслуживания)
S = C1 ∗ 0 + C2T1 + C3(T1 + T2) + C4(T1 + T2 + T3)+. . . +Ck(T1 + T2 + T3+. . . +Tk−1)
Получается, что для исходной последовательности S = 880
Для каждой заявки рассчитаем относительный штраф Ci/Ti и определим их
оптимальную последовательность Nопт (от бОльшего относительного штрафа к
меньшему).
№ 1 2 3 4 5 6 7 8 9 10
Ti 6 8 7 5 4 2 4 1 3 5
Ci 4 2 3 6 1 4 5 2 6 3

№ 1 2 3 4 5 6 7 8 9 10
Ci/Ti 2/3 1/4 3/7 6/5 1/3 2 5/4 2 2 3/5
Nопт 6 10 8 5 9 1 4 2 3 7
Таблица с новой последовательностью будет иметь следующий вид:
№ 1 2 3 4 5 6 7 8 9 10
Ti 2 1 3 4 5 6 5 7 3 8
Ci 4 2 6 5 6 4 3 3 1 2
По формуле рассчитываем штраф для оптимальной последовательности обслуживания.
Smin = 4 ∗ 0 + 2 ∗ 2 + 6 ∗ (2 + 1) + 5 ∗ (2 + 1 + 3) + 6 ∗ (2 + 1 + 3 + 4) + 4 ∗ (2 + 1 + 3 + 4 + 5) + 3 ∗ (...
Штраф для оптимальной последовательности обслуживания заявок на 462
денежных единицы меньше штрафа для исходной последовательности.

Задача 2. Задача одного станка (задача «директора»)
Если штраф Ci
для каждой заявки одинаков, то такая задача называется задачей одного
станка. Следовательно, первыми должны обслуживаться те заявки, которые имеют
меньшее время обслуживания.
(Формула суммарного штрафа в задаче одного станка)
S = C ∗ ΣT(сверху ож, внизу i)
T(вверху ож)

  • время ожидания обслуживания
    Пример
    На прием к директору предприятия записалось 10 сотрудников. Предварительный анализ
    тем собеседования позволил выяснить примерное время обсуждения каждого вопроса. В
    каком порядке следует принимать посетителей, чтобы общее время ожидания приема
    оказалось минимальным?
    № 1 2 3 4 5 6 7 8 9 10
    Ti 4 3 1 2 6 7 5 8 5 9
    Решение
    Ожидание обслуживания первой заявки = 0, второй = времени обслуживания первой
    заявки, третьей = сумме времени обслуживания первой и второй заявок и т.д.
    Tож1 = 0,
    Тож2 = Т1
    Тож3 = Т1 + Т2
    И т.д.
    Рассчитаем время обслуживания для каждой заявки и занесем данные в таблицу:
    № 1 2 3 4 5 6 7 8 9 10
    Ti 4 3 1 2 6 7 5 8 5 9
    Tожi 0 4 7 8 10 16 23 28 36 41
    ΣTожi = 0 + 4 + 7 + 8 + 10 + 16 + 23 + 28 + 36 + 41 = 173
    S = 173C
    Определим оптимальную последовательность заявок (от меньшего времени
    обслуживания Ti к бОльшему).
    № 1 2 3 4 5 6 7 8 9 10
    Ti 4 3 1 2 6 7 5 8 5 9
    Tожi 0 4 7 8 10 16 23 28 36 41
    Nопт 4 3 1 2 7 8 5 9 6 10
    Новая таблица с оптимальной последовательностью:
    № 1 2 3 4 5 6 7 8 9 10
    Ti 1 2 3 4 5 5 6 7 8 9
    Tожi 0 1 3 6 10 15 20 26 33 41
    Суммарное время ожидания обслуживания в порядке оптимальной очереди
    ΣTожi = 0 + 1 + 3 + 6 + 10 + 15 + 20 + 26 + 33 + 41 = 155
    S = 155C
    Таким образом, разница в сумме штрафа при исходном и оптимальном формировании
    очереди составляет 18C.
    Но время обслуживания всех заявок останется неизменным при любом формировании
    очереди и составит:
    ΣTi = 4 + 3 + 1 + 2 + 6 + 7 + 5 + 8 + 5 + 9 = 50
    Алгоритм Джонсона
    Среди всех ai и bi выбирается наименьшее число m = min {ai; bi}
  1. Если m находится в строке А, то k-я деталь обрабатывается первой, а если в строке В, то последней;
  2. Деталь № k вычеркивается из списка. Алгоритм повторяется до тех пор, пока не будут
    вычеркнуты все детали.
    В результате получаем оптимальную последовательность обработки деталей.
    Пример 1
    Имеется 5 деталей. Время их обработки приведено ниже.
    № детали 1 2 3 4 5
    А 15 16 11 12 9
    В 10 17 10 13 6
    TA = Σaj = 63
    TB = Σbj = 56
    ti = (a1+. . . +ai) − (b1+. . . +bi−1 + t1+. . . +ti−1)
    Tож= Σti = 21
    Tобр = TB + Tож = 77
    Воспользуемся алгоритмом Джонсона.
  3. min(ai; bi) = min(15, 16, 11, 12, 9; 10, 17, 10, 13, 6) = 6 = b5 → деталь №5 обрабатывается последней. Теперь вычеркнем деталь из списка:
    № детали 1 2 3 4
    А 15 16 11 12
    В 10 17 10 13
  4. min(ai; bi) = min(15, 16, 11, 12; 10, 17, 10, 13) = 10 = b3 = b1 → деталь №3 и №1
    обрабатываются предпоследними (порядок неважен). Теперь вычеркнем детали из списка:
    № детали 2 4
    А 16 12
    В 17 13
  5. min(ai; bi) = min(16, 12; 17, 13) = 12 = a4
    → деталь №4 будет обрабатываться первой.
    Теперь вычеркнем деталь из списка:
    № детали 2
    А 16
    В 17
  6. В списке осталась одна деталь, ставим её на оставшееся место.
  7. Оптимальный порядок представлен ниже
    Nопт 4 2 3(1) 1(3) 5
    Изобразим рассмотренные варианты в виде графа:
    <Фото отправил>
    Также сведем полученные данные в таблицу:
    № детали 1 2 3 4 5
    А 15 16 11 12 9
    В 10 17 10 13 6
    Nопт 4 2 3 (1) 1 (3) 5
    TA = Σaj = 63
    TB = Σbj = 56
    Tож = Σti = 15
    Tобр = TB + Tож = 71
    Выигрыш времени оптимального варианта обработки заявок по сравнению с исходным порядком = 6

Thought

Reasoned about task optimization and algorithms for 2m 42s

Answer

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


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

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

Зад. 1

№ заявки123456789Ti121318142219161720Ci536245381\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

№ заявки123456789Tj256035454530255020\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}

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

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

№ заявки123456789A618544722552743319B213253405530106210\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

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

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

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

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

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

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

Складываем:

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

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

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

  1. C1T1=5120,4167\tfrac{C_1}{T_1}=\tfrac{5}{12}\approx0{,}4167
  2. C2T2=3130,2308\tfrac{C_2}{T_2}=\tfrac{3}{13}\approx0{,}2308
  3. C3T3=618=0,3333\tfrac{C_3}{T_3}=\tfrac{6}{18}=0{,}3333
  4. C4T4=2140,1429\tfrac{C_4}{T_4}=\tfrac{2}{14}\approx0{,}1429
  5. C5T5=4220,1818\tfrac{C_5}{T_5}=\tfrac{4}{22}\approx0{,}1818
  6. C6T6=5190,2632\tfrac{C_6}{T_6}=\tfrac{5}{19}\approx0{,}2632
  7. C7T7=316=0,1875\tfrac{C_7}{T_7}=\tfrac{3}{16}=0{,}1875
  8. C8T8=8170,4706\tfrac{C_8}{T_8}=\tfrac{8}{17}\approx0{,}4706
  9. C9T9=120=0,05\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(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).

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

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

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

Сумма:

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

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

22321674=558.2232-1674=558.

Задача 2

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

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

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

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

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

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

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

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

Сами TjT_j:

#1=25,  #2=60,  #3=35,  #4=45,  #5=45,#6=30,  #7=25,  #8=50,  #9=20.\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).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).(9,\;1,\;7,\;6,\;3,\;4,\;5,\;8,\;2).

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

  1. #9:\#9: ждет 00.
  2. #1:\#1: ждет 20.20.
  3. #7:\#7: ждет 20+25=45.20+25=45.
  4. #6:\#6: ждет 45+25=70.45+25=70.
  5. #3:\#3: ждет 70+30=100.70+30=100.
  6. #4:\#4: ждет 100+35=135.100+35=135.
  7. #5:\#5: ждет 135+45=180.135+45=180.
  8. #8:\#8: ждет 180+45=225.180+45=225.
  9. #2:\#2: ждет 225+50=275.225+50=275.

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

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


Задача 3

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

Ai ⁣:61,  85,  44,  72,  25,  52,  74,  33,  19,Bi ⁣:21,  32,  53,  40,  55,  30,  10,  62,  10.\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. Ищем среди всех AiA_i и BiB_i самое маленькое число mm.
  2. Если mm относится к какой-то заявке к первой операции (AA) — ставим эту заявку как можно раньше в расписании; если mm относится ко второй операции (BB) — ставим её как можно позже.
  3. Удаляем эту заявку из рассмотрения и повторяем, пока не разберем все заявки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

  1. Задача 1:

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

    • Tож\sum T_{\text{ож}} в исходном порядке: 1425
    • Tож\sum T_{\text{ож}} в порядке возрастания TjT_j: 1050
    • Выигрыш: 375 (по времени ожидания), или 375C375\cdot C по штрафу.
  3. Задача 3 («2 станка по Джонсону»):

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

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

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

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

Share this Q&A