Looking for the best online distribution algorithm

Question

I’m looking for a solution to the assignment problem when tasks come and they need to be assigned sequentially, but you can make tasks wait until periods K.

Formally, let there be an ordered sequence of tasks aabbaba ... and an ordered sequence of resources ABBABAA ..., and the system can use the side stack. The goal is to map most tasks a (b) to resources A (resp B). Limitations are as follows: every period I program receives a resource I and assigns it to a task. A resource is assigned either to a task from the stack or continues to read from the sequence of tasks in order. Each read task can be immediately assigned to resource I or can be pushed onto the stack if it waits there for less than K periods and match is assigned to it (a-> A, b-> B).

If K = 0 should be assigned for the ith resource, then the ith task should be assigned, which is pretty bad. If K> 0, than you can do better with a greedy algorithm. What is the best solution?

Clarification:

We denote the assignment by the permutation m, where m (i) = j means that resource j has been assigned to task i. If there is no stack m (i) = i. When the tasks of the stack can be assigned out of order, but if the task set later than me is pushed onto the stack, then I need to assign one of the following resources K. That is, the assignment is legal if for all tasks i:

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

I am looking for an algorithm that will find a destination that has a minimum number of skip assignments (aB or bA) from all destinations that satisfy the constraints.

Answer 1

You can formulate the problem as follows:

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

We can define a cost function to assign task j to output i:

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

I choose 1000 → 1 in case you cannot fulfill the requirements.

Let the restriction be written:

• xi, j = 1 if you assigned task j ressource j and 0 otherwise.
• In addition, xi, j = 0 if ij> K

since you follow resources sequentially and you can wait k period max (ij <= K)

• Only one xi, j can be equal to one for all i, j.

Then you will get the following linear program:

Collapse: Sum (C (i, j) * xi, j)

Topic:

• xi, j in {0,1}

• The sum (xi, j) = 1 for all i

• The sum (xi, j) = 1 for all j

• xi, j = 0 if ij> K

• xi, j> = 0 otherwise

You may need to fix the restrictions a bit ... after fixing this solution should be optimal, but I'm not sure if the greedy algorithm is not optimal yet.

It is more interesting to use this formulation with more than two different resources.

I hope I understand your question and it helps

---

Modifications:

I will translate this restriction:

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

Note:

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

"transfer":

with previous notation:

 _m(i) <= Min{ m(i') st i'> i } + K_ < = > j <= Min{j' st i'>i and xi',j' =1 } + K_ (OK ?) 

New linear constraint:

we have:

 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' 

Consequently:

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

and less than min, equivalently less than each.

Then a new set of restrictions:

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

You can add these restrictions to the previous ones, and you will get a linear program .

You can solve this with a simplex algorithm .