寻找最优的在线分配算法

Question

寻找最优的在线分配算法

algorithmvariable-assignmentcombinatorics

6

我正在寻找一个解决方案，用于任务按顺序到来并需要按顺序分配，但可以使任务等待最多K个周期。形式上，有一个有序的任务序列aabbaba...和一个有序的资源序列ABBABAA...，系统可以使用侧边栏。目标是将最多的a（或b）任务与A（或B）资源匹配。约束条件如下：每个周期i程序获取资源i并将其分配给任务。该资源被分配给堆栈中的任务，或者它继续按顺序从任务序列中读取。读取的每个任务都可以立即分配给资源i，也可以放在堆栈上，如果它将在那里等待不到K个周期，并且将被分配给它的匹配（a->A，b->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') s.t. i'>i}+K。我正在寻找一种算法，它将找到具有最小数量的错误分配（aB或bA）的分配，其中满足约束条件的所有分配中的误差最小。

- Jacob

1

如果您无法满足要求，应该发生什么？ - svick

等待是不是没有任何相关的费用呢？ - Ahmed Abdelkader

如果你不能满足要求，就必须错配任务并支付成本。任何可用的资源都必须与某些任务匹配，并且在堆栈中保持任务是零成本（如果在K个周期以内）。 - Jacob

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ricky Bobby · Accepted Answer

你可以这样表述问题：

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。

让我们写出约束条件：

如果将任务j分配给资源j，则xi，j = 1，否则为0。
此外，如果i-j>K，则xi，j = 0

因为您按顺序跟随资源，并且最多可以等待k个周期（i-j<=K）

只有一个xi，j可以等于所有i，j的一。

然后您将获得以下线性规划：

最小化：Sum(C(i,j)*xi,j)

受制于：

xi，j在{0,1}中
对于所有i，Sum(xi，j) = 1
对于所有j，Sum(xi，j) = 1
如果i-j>K，则xi，j = 0
否则，xi，j>=0

您可能需要稍微调整一下约束条件... 一旦纠正了这个问题，这个解决方案应该是最优的，但我不确定贪心算法是否已经是最优的。

使用这种表达式处理多于两种不同资源会更加有趣。

希望我理解了您的问题，并且能够为您提供帮助。

修改：

我将翻译这个约束条件：

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

注意：

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

你可以将这些约束条件添加到之前的条件中，从而得到一个线性规划问题。

你可以使用单纯形算法来解决它。