Question

Give mathematical form of Assignment problem

Answer 1

Consider the problem of assigning n jobs to n machines (one job to one machine).

Let C_ij be the cost of assigning i^th job to the j^th machine and x_ij represents the assignment of i^th job to the j^th machine.

Then, xij = ${\displaystyle \{\begin{array}{ll}1\text{,}& \text{if} {\text{i}}^{\text{th}}\text{job is assigned to} {\text{j}}^{\text{th}}\text{machine}\\ 0\text{,}& \text{if} {\text{i}}^{\text{th}}\text{job is assigned to} {\text{j}}^{\text{th}}\text{machine}\end{array}}$

		Machines
		1	2	…	n	Supply
	1	${\displaystyle {}^{\left(x_{11}\right)}{\text{C}}_{11}}$	${\displaystyle {}^{\left(x_{12}\right)}{\text{C}}_{12}}$	…	${\displaystyle {}^{\left(x_{1n}\right)}\left({\text{C}}_{1n}\right)}$	1
	2	${\displaystyle {}^{\left(x_{21}\right)}{\text{C}}_{21}}$	${\displaystyle {}^{\left(x_{22}\right)}{\text{C}}_{22}}$	…	${\displaystyle {}^{\left(x_{2n}\right)}\left({\text{C}}_{2n}\right)}$	1
Jobs	:		:	:	:	1
	m	${\displaystyle {}^{\left(x_{\text{ij}}\right)}{\text{C}}_{\text{n}1}}$	${\displaystyle {}^{\left(x_{m2}\right)}{\text{C}}_{\text{n}1}}$	…	${\displaystyle {}^{\left(x_{\text{ij}}\right)}\left({\text{C}}_{\text{nn}}\right)}$	1
Demand		b1	b2	…	bn

x_ij is missing in any cell means that no assignment is made between the pair of job and machine.

i.e x_ij = 0.

x_ij is presents in any cell means that an assignment is made their.

In such cases x_ij = 1

The assignment model can written in LPP as follows:

Minimize Z = ${\displaystyle \sum _{\text{i}=1}^{\text{m}},\sum _{\text{j}=1}^{\text{n}}{\text{C}}_{\text{ij}}{\text{X}}_{\text{ij}}}$

Subject to the constrains

${\displaystyle \sum _{\text{i}=1}^{\text{n}}{\text{X}}_{\text{ij}}}$ = 1, j =  1, 2, …. n

${\displaystyle \sum _{\text{i}=1}^{\text{n}}{\text{X}}_{\text{ij}}}$ = 1, i =  1, 2, …. n and x_ij =0 or 1 for all i, j