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 = `{{:(1",",  "if"  "i"^"th" "job is assigned to"  "j"^"th" "machine"),(0",",  "if"  "i"^"th" "job is assigned to"  "j"^"th" "machine"):}`

		Machines
		1	2	…	n	Supply
	1	`""^((x_11))"C"_11`	`""^((x_12))"C"_12`	…	`""^((x_(1n)))("C"_(1n))`	1
	2	`""^((x_21))"C"_21`	`""^((x_22))"C"_22`	…	`""^((x_(2n)))("C"_(2n))`	1
Jobs	:		:	:	:	1
	m	`""^((x_"ij"))"C"_("n"1)`	`""^((x_(m2)))"C"_("n"1)`	…	`""^((x_"ij"))("C"_"nn")`	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 = `sum_("i" = 1)^"m", sum_("j" = 1)^"n" "C"_"ij" "X"_"ij"`

Subject to the constrains

`sum_("i" = 1)^"n" "X"_"ij"` = 1, j =  1, 2, …. n

`sum_("i" = 1)^"n" "X"_"ij"` = 1, i =  1, 2, …. n and x_ij =0 or 1 for all i, j