JOB ASSIGNMENT
PROBLEM USING
BRANCH AND
INTRODUCTION:
• JOB ASSIGNMENT PROBLEM IS ONE OF THE FUNDAMENTAL COMBINATORIAL
OPTIMIZATION PROBLEMS. IN ITS MOST COMMON IN ITS FORM.
• EXAMPLES OF PROBLEMS HAVE A NUMBER OF PEOPLE AND A NUMBER OF
JOBS.
• EACH PERSON CAN BE ASSIGNED TO DO ANY JOB, WHICH HAS DIFFERENT
COSTS DEPENDING ON THE JOB.
• THE GOAL IS TO DO AS MANY JOBS AS POSSIBLE BY ASSIGNING ONE PERSON
TO EACH JOB AND ONE JOB PER PERSON, IN SUCH A WAY THAT THE TOTAL
COST IS MINIMIZED
ALGORITHM:
CONSIDER WE HAVE TO ASSIGN N NO OF JOBS TO N NO OF PERSONS
• STEP 1: CALCULATE THE INITIAL LOWER BOUND
LOWER BOUND= MINIMUM OF EACH ROW
• STEP 2: CONSIDER A PERSON AND ASSIGN ALL POSSIBLE JOBS
• STEP 3: CALCULATE THE LOWER BOUND OF PERSON USING
LOWER BOUND=A[PERSON][JOB]+MINIMUM OF UNASSIGNED PERSON
AND JOBS
• STEP 4: ASSIGN THE JOB WHICH HAVE MINIMUM LOWER BOUND VALUE TO THE PERSON
AND ELIMINATE THE JOB AND PERSON.
• STEP 5:REPEAT STEP 2,3,4 UNTIL ALL JOBS ARE ASSIGNED TO ALL PERSONS.
• STEP 6:FIND THE FINAL MINIMUM COST OF JOBS AND PERSONS.
PSEUDOCODE:
Define N = 4
Function findMinCost(costMatrix, worker, mask, minCost,
curCost):
If worker == N:
If curCost < minCost[0]:
minCost[0] = curCost
Return
For job = 0 to N-1:
If (mask & (1 << job)) == 0: // Job not yet assigned
Call findMinCost(costMatrix, worker + 1, mask
| (1 << job), minCost, curCost + costMatrix[worker][job])
Main Function:
Initialize costMatrix as [[9, 2, 7, 8], [6, 4, 3, 7], [5,
8, 1, 8], [7, 6, 9, 4]]
Set minCost = [INT_MAX] // Use a list to pass by
reference
Call findMinCost(costMatrix, 0, 0, minCost, 0)
Print minCost[0]
EXPLANATION:
INPUTS:
COSTMATRIX: A MATRIX REPRESENTING THE COST OF ASSIGNING JOBS TO
WORKERS.
WORKER: THE CURRENT WORKER INDEX BEING ASSIGNED A JOB.
MASK: A BITMASK INDICATING WHICH JOBS HAVE ALREADY BEEN ASSIGNED.
MINCOST: A LIST CONTAINING THE MINIMUM COST FOUND SO FAR.
CURCOST: THE CURRENT TOTAL COST OF THE ASSIGNMENT UP TO THIS POINT.
1. DEFINE N:
N = 4 (NUMBER OF WORKERS AND JOBS).
2. FUNCTION FINDMINCOST:
BASE CASE:
IF ALL WORKERS ARE ASSIGNED (WORKER == N):
UPDATE MINCOST[0] IF CURCOST IS LOWER.
RETURN.
RECURSIVE CASE:
FOR EACH JOB FROM 0 TO N-1:
IF JOB IS NOT ASSIGNED (MASK & (1 << JOB) == 0):
RECURSIVELY ASSIGN THE JOB TO THE WORKER, UPDATE MASK, AND ADD TO
CURCOST.
MAIN FUNCTION:
INITIALIZE COSTMATRIX.
SET MINCOST = [INT_MAX] TO ALLOW UPDATES WITHIN THE FUNCTION.
CALL FINDMINCOST WITH INITIAL PARAMETERS.
PRINT MINCOST.
ADVANTAGES:
• THE TIME COMPLEXITY OF THE BRANCH AND BOUND ALGORITHM IS
LESS WHEN COMPARED WITH OTHER ALGORITHMS.
• IT FINDS AN OPTIMAL SOLUTION FOR A GIVEN PROBLEM.
• THE BRANCH AND BOUND ALGORITHM FIND A MINIMAL PATH TO
REACH THE OPTIMAL SOLUTION FOR A GIVEN PROBLEM.
DISADVANTAGES:
• THE BRANCH AND BOUND ALGORITHM ARE TIME-CONSUMING.
• PARALLELIZATION IS EXTREMELY DIFFICULT IN THE BRANCH AND
BOUND ALGORITHM.
• REQUIRES SIGNIFICANT MEMORY TO STORE BRANCHES AND PARTIAL
SOLUTIONS.
