USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Introduction and Mathematical Formulation

Consider n machines M1, M2, ... , Mn and n different jobs J1, J2, .... , Jn. These jobs to be processed by the machines one to one basis i.e., each machine will process exactly one job and e ach job will be assigned to only one machine. For each job the processing cost depends on t he machine to which it is assigned. Now we have to determine the assignment of the jobs to the machines one to one basis such that the total processing cost is minimum. This is called an assignment problem.

 

If the number of machines is equal to the number of jobs then the above problem is called

balanced or standard assignment problem. Otherwise, the problem is called unbalanced or non standard assignment problem. Let us consider a balanced assignment problem.

 

For linear programming problem formulation, l et us define the decision variables as

 

Xij = {1, if job j is assigned t o machine i

0, otherwise

 

and the cost of processing job j on machine i as cij. Then we can formulate the assignment problem as follows :

subject to,

Σxij = 1,           i = 1, 2, ... , n

 

(E ach job is assigned exactly t o one machine)

 

Σxij = 0 or 1 for all i and j

In matrix form,           Minimize z = Cx

subject to, Ax = 1,

xij = 0 or 1, i, j = 1, 2, .... , n.

 

where A is a 2n * n2 matrix and total unimodular i.e., the determinant of every sub square matrix formed from it has value 0 or 1. This property permits us to replace the constraint xij = 0 or 1 by the constraint xij ≥ 0. Thus we obtain

 

Minimize z = Cx

subject to, Ax = 1, x ≥ 0

The dual of (1) with the non-negativity restrictions replacing the 0-1 constraints can be written as follows :

subject to, ui + vj ≤ cij,                       i, j = 1, 2, . ... , n.

ui, vj unrestricted in signs                  i, j = 1, 2, . ... , n.

 

Example 1. A company is facing the problem of assigning four operators to four machines. The assignment cost in rupees in given below :

In the above, operators I and III cannot be assigned to the machines M3 and M4 respectively. Formulate the above problem as a LP model.

 

Solution.

 

Let       xij = { 1, if the ith operator is assigned to jth machine

0, otherwise

i, j = 1, 2, 3, 4.

be the decision variables.

 

By the problem,  x13 = 0 and x34 = 0.

The LP model is given below :

 

Minimize z = Sx11 + 7x12 + 4x14 + 7x21 + Sx22 + 3x23 + 2x24

+ 9x31 + 4x32 + 6x33 + 7x41 + 2x42 + 7x43 + 6x44

subject to,

(Operator assignment constraints)

 

X11+ X12 + X14 =1

X21 + X22 + X23 + X24 =1

X31 + X32 + X33 = 1

X41 + X42 + X43 + X44 = 1

 

(Machine assignment constraints)

X11 + x21 + x3l + x41 = 1

X12 + X22 + X32 + X42 =1

X23 + X33 + X43 =1

X14 + X24 + X44 =1

Xij ≥ 0 for all i and j.