寻找最佳的在线分配算法

Question

我正在寻找一个分配问题的解决方案,其中任务来自并且需要按顺序分配,但是您可以使任务等待最多K个周期.

在形式上,让一个有序的任务序列 aabbaba ...... 和一个有序的资源序列ABBABAA ......,系统可以使用一个侧面堆栈.其目的是,以匹配最一个(相应b任务)至甲(相应乙)资源.约束条件如下:每一期我的程序获取资源我,并将其分配到的任务.资源被分配给堆栈中的任务,或者继续按顺序从任务序列中读取.读取的每个任务可以立即分配给资源i,也可以放在堆栈中,如果它将在那里等待少于K个周期并且将被分配给它的匹配(a-> A,b-> B).

如果K = 0,则必须将第i个任务分配给第i个资源,这非常糟糕.如果K> 0,那么使用贪婪算法可以做得更好.什么是最佳解决方案？

澄清:

通过置换m表示赋值,其中m(i)= j表示资源j被分配给任务i.如果没有堆栈m(i)= i.当有一个堆栈任务可以被分配出去的顺序,但如果一个任务晚于我比放在堆栈我必须分配下列操作之一ķ资源.也就是说,转让是合法的,如果所有的任务我:

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

我正在寻找能够在满足约束的所有分配中找到具有最小量的未命中分配(aB或bA)的分配的算法.

Answer 1

您可以这样表述问题：

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。
• 此外，如果 ij>K，则 xi,j =0

因为你一一跟踪资源，你可以等待 k 周期 max (ij<=K)

• 对于所有 i,j，只有一个 xi,j 可以等于 1。

然后你得到以下线性程序：

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

须遵守：

• {0,1} 中的 xi,j

• 对于所有 i，Sum(xi,j) = 1

• 对于所有 j，Sum(xi,j) = 1

• xi,j = 0 如果 ij>K

• xi,j>=0 否则

您可能需要纠正一点约束......一旦纠正，这个解决方案应该是最佳的，但我不确定贪婪算法是否还不是最佳的。

将这个公式与两种以上不同的资源一起使用会变得更有趣。

希望我理解你的问题并且有帮助

修改：

我将翻译这个约束：

m(i) <= Min{ m(i') st 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 

小于 min 相当于小于 every 。

那么新的约束集是：

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

您可以将这些约束添加到之前的约束中，然后就得到一个线性程序。

您可以使用单纯形算法来解决这个问题。