Mathematical formulation of assignment problem

Answer 1

Let there be n jobs which are to be assigned to n operators so that one job is assigned to only one operator.

i = Index for job, i = 1, 2, … n

j = Index for operators, j = 1, 2, … n

Cij = Unit cost for assigning job 'i' to operator 'j'

1 if job i is assigned to operator j

Xij = 0 Otherwise

The objective is to minimize the total cost of assignment. If job I is assigned to operator 1, the cost is (C11X11). Similarly, for job 1, operator 2 the cost is (C12X12). The objective function is:

Minimize = ∑ni=1 ∑nj=1 Cij Xij …(1)

Since one job (i) can be assigned to any one of the operators, we have following constraint set:

∑ni=1 Xij = 1; for all j;j = 1, 2, ... n …(2)

Similarly for each operator, there may be only one assignment of job. For this, the constraint set is:

∑ni=1 Xij = 1; for all i;i = 1, 2, ... n …(3)

The non-negativity constraint is:

Xij > 0 …(4)

Minimize Z = ∑ni=1 ∑nj=1 Cij Xij

Subject to ∑ni=1 Xij = 1; for all j;j = 1, 2, ... n

∑nj=1 Xij = 1; for all i;i = 1, 2, ... n

Xij > for all i and all j.

JANAK RAJ UPRETI

TIMT COLLAGE RAJOURI GARDEN New Delhi

17/41 WEST PUNJABI BAGH

S-6..

9311864681 WITH ... DINESH GARG...9899558427