Generalized assignment problem: Difference between revisions

Revision as of 15:39, 8 April 2008

Revision as of 15:44, 8 April 2008

Line 23:

The algorithm constructs a schedule in iterations, where during iteration <math>j</math> a tentative selection of items to bin <math>b_j</math> is selected.

The selection for bin <math>b_j</math> might change as items might be reselected in a later iteration for other bins.

The residual profit of an item <math>x_i</math> for bin <math>b_j</math> is <math>p_{ij}</math> isif <math>x_i</math> is not selected for any other bin or <math> p_{ij}</math> – <math>p_{ik} </math> if <math>x_i</math> is selected for bin <math>b_k</math>.

Formally: We use a vector <math>T</math> to indicate the tentative schedule during the algorithm. Specifically, <math>T[i]=j</math> means the item <math>x_i</math> is scheduled on bin <math>b_j</math> and <math>T[i]=-1</math> means that item <math>x_i</math> is not scheduled. The residual profit in iteration <math>j</math> is denoted by <math>P_j</math>, where <math>P_j[i]=p_{ij}</math> if item <math>x_i</math> is not scheduled (i.e. <math>T[i]=-1</math>) and <math>P_j[i]=p_{ij}-p_{ik}</math> if item <math>x_i</math> is scheduled on bin <math>b_k</math> (i.e. <math>T[i]=k</math>).