Looking for an optimal online assignment algorithm

Question

I'm looking for a solution to an assignment problem where tasks come and need to be assigned sequentially, but you can make tasks wait for up to K periods.

Formally, let there be an ordered sequence of tasks aabbaba... and an ordered sequence of resources ABBABAA..., and the system can use a side stack. The aim is to match the most a (resp b) tasks to A (resp B) resources. The constraints are as following: each period i the program gets the resource i and assigns it to a task. The resource is assigned either to a task from the stack, or it continues to read from the sequence of tasks in order. Each task that is read can either be immediately assigned to resource i, or can be put on the stack IF it will wait there less than K periods and will be assigned to it's match (a->A,b->B).

If K=0 than the i-th task must be assigned to the i-th resource, which is pretty bad. If K>0 than you can do better with a greedy algorithm. What is the optimal solution?

Clarification:

Denote the assignment by a permutation m where m(i)=j means that resource j was assigned to task i. If there is no stack m(i)=i . When there is a stack tasks can be assigned out of order, but if a task later than i is put in the stack than i must be assigned one of the following K resources. That is, the assignment is legal if for all tasks i:

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

I am looking for the algorithm that will find the assignment that has the minimal amount of miss assignments (aB or bA) out of all the assignments satisfying the constraints.

Answer 1

You can formulate the problem this way:

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

We can define a cost function of assigning task j to ressource i:

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

I choose 1000 >> 1 in the case you're unable to meet the requirements.

Let's write the constraint:

• xi,j =1 if you assign task j to ressource j, and 0 otherwise.
• moreover, xi,j =0 if i-j>K

since you follow the ressources one by one and you can wait k period max (i-j<=K)

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

Then you get the following linear program:

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

Subject to:

• xi,j in {0,1}

• Sum(xi,j) = 1 for all i

• Sum(xi,j) = 1 for all j

• xi,j = 0 if i-j>K

• xi,j>=0 otherwise

You may need to correct a little bit the constraints...once corrected this solution should be optimal but I am not sure the greedy algorithm is not already optimal.

It gets more interesting to use this formulation with more than 2 different ressources.

Hope I understood your question and it helps

---

Modifications:

I will translate this constraint :

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

Note:

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

"translation":

with the previous notations:

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

< = > j <= Min{j' s.t 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'

Therefore :

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 

and less than min is equivalent to less than each .

Then the new set of constraints is:

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

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

You can solve this with a simplex algorithm.