Scribd
Upload
141 views10 pages

Job Assignment with Branch and Bound

The document discusses the Job Assignment Problem, where N workers are assigned to N jobs with the goal of minimizing total assignment costs. It outlines the use of the Branch and Bound method to explore possible assignments and compute lower bounds at each level of a state space tree. The process involves sequentially assigning jobs to workers while calculating costs and optimizing the assignment.

Uploaded by

mudit6565
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
141 views10 pages

Job Assignment with Branch and Bound

The document discusses the Job Assignment Problem, where N workers are assigned to N jobs with the goal of minimizing total assignment costs. It outlines the use of the Branch and Bound method to explore possible assignments and compute lower bounds at each level of a state space tree. The process involves sequentially assigning jobs to workers while calculating costs and optimizing the assignment.

Uploaded by

mudit6565
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Job Assignment Problem using

Branch And Bound

Slide 1
Job Assignment Problem using Branch And
Bound
• Let there be N workers and N jobs.
• Any worker can be assigned to perform any job, incurring some cost
that may vary depending on the work-job assignment.
• It is required to perform all jobs by assigning exactly one worker to
each job and exactly one job to each agent in such a way that the
total cost of the assignment is minimized.

Slide 2
Job Assignment Problem using Branch And Bound

Slide 3
Initial lower bound

Slide 4
Consider person a

Slide 5
Level 0 and level 1 state space tree

• Assign Job 2 to person a with cost=2

Slide 6
Consider person b

• Assign various jobs to person b by leaving job 2 which is


assigned to person a and compute lower bound

Slide 7
Level 0,1 and Level 2 State Space Tree

Slide 8
Consider Person c

• Assign various jobs to person c by leaving job 2 and job 1 which


is assigned to person a and person b and compute the lower
bound.

Slide 9
Level 0,1 , 2 and Level 3 State Space Tree

• Optimal solution

Slide 10

You might also like