Scribd
Upload
41 views2 pages

Assignment Problem

Assignment Problem

Uploaded by

Vishal More
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
41 views2 pages

Assignment Problem

Assignment Problem

Uploaded by

Vishal More
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Assignment Problem: Problem statement - There are n-people and a-jobs are to be assigned. Each job cost is represented using rows. In this n-jobs one person can’t do two jobs and two persons can’t select same jobs. Fine the lower bond cost from n»a matrix. Example 1: Solve the following assignment problem using branch and bound method. Job1 | Job2 | Job2 | Job4 Person A | 10 2 7 8 PersonB| 6 4 3 7 PesonC | 5 8 1 8 PersonD | 7 6 10 4 Solution Select lower bound value 76 0G LB=2+3+1+4=10 Start LB= 10 Solution Lower Bound value is 13 Example 2: Solve the following assignment problem using branch aud bound method. Job1 | Job2 | Job2 | Job4 Person A | 9 2 7 8 PesonB| 6 4 3 7 PersonC | 5 8 1 8 PersonD | 7 6 9 4 Solution Select lower bound value 9 Q@) 7 8 6 4 G) 7 8 8 7 6 9 @ LB=2+3+1+4=10 Start LB=10 A=9 A=2 A=7 A=8 LB-9+3H1-+4=17 LB=2+3+1+4=10 LB=7+445+4=20 LB-8+3+H1+6=18 B=6 B=3 B=7 LB=24+6HH=13 LB=243+5H4=14 LB=2+7+147=17 c=l c=8 LB=2+-64174=13 LB=2+6+8+9=25 LowegBound value is 13, solution

You might also like