Ищем оптимальный онлайн алгоритм назначения - PullRequest
Новая
       1

Ищем оптимальный онлайн алгоритм назначения

6 голосов
/ 19 июня 2011

Я ищу решение проблемы назначения, когда задачи приходят и должны назначаться последовательно, но вы можете заставить задачи ждать до K периодов.

Формально, пусть будет упорядоченная последовательность задач aabbaba ... и упорядоченная последовательность ресурсов ABBABAA ... , и система может использовать сторонустек.Цель состоит в том, чтобы сопоставить большинство a (соответственно b ) задач с A (соответственно B ) ресурсами.Ограничения следующие: каждый период i программа получает ресурс i и назначает его задаче.Ресурс назначается либо задаче из стека, либо он продолжает читать последовательность задач по порядку.Каждое читаемое задание может быть либо сразу назначено ресурсу i , либо помещено в стек, ЕСЛИ оно будет ждать там менее чем K периодов и будет назначено на его совпадение (а-> А, b-> В).

Если K = 0 , то задача i должна быть назначена ресурсу i , что довольно плохо.Если K> 0 , то вы можете добиться большего успеха с жадным алгоритмом.Какое оптимальное решение?

Уточнение:

Обозначение присвоения перестановкой m , где m (i) = j означает, что ресурс j было назначено задание i .Если нет стека m (i) = i .При наличии стека задачи могут быть назначены не по порядку, но если в стек помещено задание, которое позже i , то i должно быть назначено одно из следующих K ресурсов.То есть назначение является законным, если для всех задач i :

m (i) <= Min {m (i ') st i'> i} + K

Я ищу алгоритм, который найдет назначение, имеющее минимальное количество пропусков (aB или bA) из всех назначений, удовлетворяющих ограничениям.

1 Ответ

3 голосов
/ 20 июня 2011

Вы можете сформулировать проблему следующим образом: 

ressources=[a,b,b,a,b,a,a,...]
tasks=[a,a,b,b,a,b,a,...]

Мы можем определить стоимостную функцию назначения задачи j для ресурса i: 

C(i,j)= (ressources[i]==tasks[j])*1+(ressources[i]!=tasks[j])*1000

Я выбираю 1000 >> 1, если вы не можете выполнить требования.

Давайте напишем ограничение:

  • xi, j = 1, если вы назначаете задачу j Ресурс j и 0 в противном случае.
  • кроме того, xi, j = 0, если i-j> K

так как вы следите за ресурсами один за другим и вы можете ждать k период макс (i-j <= K) </p>

  • Только один xi, j может быть равен одному для все, я.

Тогда вы получите следующую линейную программу:

Свернуть: Сумма (C (i, j) * xi, j)

Подлежит:

  • xi, j в {0,1}

  • Сумма (xi, j) = 1 для всех i

  • Сумма (xi, j) = 1 для всех j

  • xi, j = 0, если i-j> K

  • xi, j> = 0 в противном случае

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

Становится интереснее использовать эту формулировку с более чем 2 различными источниками.

Надеюсь, я понял ваш вопрос, и это помогает

Модификация:

Я переведу это ограничение:

m (i) <= Min {m (i ') s.t. я> я} + К

Примечание: 

if xi,j =1 then Sum(j*xi,j on i) = j since only one xi,j = 1

"перевод":

с предыдущими обозначениями: 

_m(i) <= Min{ m(i') s.t.  i'> i } + K_ 

< = > j <= Min{j' s.t i'>i and xi',j' =1 } + K_  (OK ?)

Новое линейное ограничение:

у нас есть: 

xi,j=1  < = > Sum(j*xi,j on j) = j for i

and 

xi',j'=1  < = > Sum(j'*xi',j' on j') = j'  for all i'

Следовательно: 

j <= Min{j' s.t i'>i and xi',j' =1 } + K_ 

< = >

Sum(j*xi,j on j)  <= Min { Sum(j'*xi',j' on j') , i'>i} + K

и меньше, чем мин, эквивалентно меньше, чем каждый.

Тогда новый набор ограничений: 

Sum(j*xi,j on j)  <=  Sum(j'*xi',j' on j') + K  for all i' > i

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

Вы можете решить это с помощью симплексного алгоритма .

...