ASSIGNMENT

Definition

Problems relating to assigning workers should do one jobs so that one worker should one job and only one job, so that the overall timetable is minimum are called assignment problem

Problems are classified into

1. Balanced assignment problem
2. Unbalanced assignment problem

TYPES of problem

1. Minimization of problems
2. Maximization of problems

Minimization of problems

1. An assignment problem with cost, time, distance etc is given then it can be solved by a set of rules known as “ KONIG ALGORITHEM” OR HUNGARIAN METHOD
2. Steps
   1. verify the given entries are in minimizing nature and object is minimization
   2. Verify the given problem is balanced, if not make it balanced with the help of dummy row/column suitably
   3. Examine the first row and identify the least entry and deduct it from the entries in the first row and repeat the approache for other rows. The resulting entries are called “ROW PENALTIES”
   4. Examine the first column of row subtraction entries. Identify the least and deduct it from the first column. Similarly do it for the remaining column , the resulting entries are called “COLUMN PENALTIES”
   5. Draw minimum no. of lines (horizontal) vertical in order to crosses all the zeroes in column subtraction entries.
   6. If the minimum no. lines drawn equals to the type of the matrix then apply “BOX CROSS RULE”
   7. Other wise apply STAGE B FORMALITIES

• BOX CROSS RULE: steps

  1. Examine each rows and select the rows having exactly one zero. Put a box cover that zero and cross out zero, lying in that column
  2. After examining all the rows, examine each column and select the column having exactly one zero. Put a box cover that zero and cross out zero, lying in that column
  3. Repeat the above two steps until all zeros are marked. The zeroes shown in the the boxes represent “OPTIMAL ASSIGNMENT”

• STAGE B FORMALITIES: steps

1. Examine the entries that are not covered by straight line select the least uncovered entry call it as ‘x”
2. Perform the following
   1. Deduct ‘x’ from each uncovered entry
   2. Add ‘x’ with the entries lying at the intersection of horizontal and vertical lines (keep the elements lying on the straight lines as it is).
3. Draw minimum nos. of lines to cover the zeros. If it is equal to the type of the matrix then apply BOX CROSS RULE, if not then repeat the stage B formalities until it matches.

• Keep in mind:

  1. If dummy column is attached then row subtraction need not be performed
  2. Whenever dummy row is attached then column subtraction need not be done
  3. If nil entries are given, then it should be replaced by “infinity”
  4. The behavior of infinity is infinity
  5. The no. of rows & no. of column represents the type of matrix.

• MULTIPLE optimal solution:

  1. While applying box cross rule, there are situation where we cannot get row with single “0” or column with single “0”. In this situation select the row having exactly two ‘0s”
  2. Put a box to any one of the two zeros and cross out the other zero
  3. After doing this we may get row with single “0” or column with single “0’; which should be taken box cross rule.

MAXIMISATION PROBLEMS: steps

1. Examine all the given entries and select the highest entry
2. Deduct all the given entries from the highest entry selected. The resulting entries are called opportunity loss (OL). Thereby objective of the problem is automatically reduced to minimization.
3. Apply the same procedure as said in type 1 problems.