Блог пользователя Cyber.1

Эвристические задачи
Автор Cyber.1, 11 лет назад, По-русски

Есть 2 задачи, которые нужно решить с помощью эвристических алгоритмов, может хоть что-то подскажите))

1)Есть процессов и один исполнитель, для каждого процессора известны время исполнения и срок сдачи, нужно разместить их в порядке, при котором штрафных баллов было минимальным.

2)Есть n процессов и m процессоров. Для каждого процесса есть время его выполнения на каждом процессоре. Нужно распределить процессы между процессами чтобы суммарное время выполнение было минимальное.

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    если штрафные баллы — это часть роботы , которую процессор не успел выполнить. то на тест 3 4 3 4 6 4 9 где первое число пары — кол времени для выполнения этого процесса, а второе — срок сдачи. то програма выдаст 1 2 3, штрафа при этом будет — 6, а в порядке 2 3 1 штрафа будет 4

    → Ответить
»
11 лет назад, # |
← Rev. 6   Проголосовать: нравится +8 Проголосовать: не нравится

Первая случайно не эта ? Если у штрафов есть вес, то эта

Я нашёл вторую задачу в книге Scheduling_Peter_Brucker за m*n^3 Но только она на английском.

R || SUM(Ci)
We reduce this problem to an assignment problem. Again, if i1, i2, . . . , ir
is the sequence of jobs processed at machine Mj , then the contribution
of these jobs in the objective function i

rpi1j + (r ? 1)pi2j + . . . + 1pirj .

We define a position of a job on a machine by considering the job processed
last on the first position, the job processed second from last on
the second position, etc. To solve problem R || Sum(Ci) we have to assign
the jobs i to positions k on machines j. The cost of assigning job i to
(k, j) is kpij . Note that an optimal solution of this assignment problem
has the following property: if some job i is assigned to position k > 1
on machine j, then there is also a job assigned to position k ? 1 on machine
j. Otherwise, scheduling job i in position k ?1 would improve the
total assignment cost (provided that pij > 0). Thus, a solution of the
assignment problem always yields an optimal solution of our scheduling
problem.

Похожа на эту задачу

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Спасибо большое) очень благодарен за информацию)

    → Ответить