job assignment problem

Index     Assignment problem     Hungarian algorithm     Solve online    

The assignment problem

The assignment problem deals with assigning machines to tasks, workers to jobs, soccer players to positions, and so on. The goal is to determine the optimum assignment that, for example, minimizes the total cost or maximizes the team effectiveness. The assignment problem is a fundamental problem in the area of combinatorial optimization.

Assume for example that we have four jobs that need to be executed by four workers. Because each worker has different skills, the time required to perform a job depends on the worker who is assigned to it.

The matrix below shows the time required (in minutes) for each combination of a worker and a job. The jobs are denoted by J1, J2, J3, and J4, the workers by W1, W2, W3, and W4.

Each worker should perform exactly one job and the objective is to minimize the total time required to perform all jobs.

It turns out to be optimal to assign worker 1 to job 3, worker 2 to job 2, worker 3 to job 1 and worker 4 to job 4. The total time required is then 69 + 37 + 11 + 23 = 140 minutes. All other assignments lead to a larger amount of time required.

The Hungarian algorithm can be used to find this optimal assignment. The steps of the Hungarian algorithm can be found here , and an explanation of the Hungarian algorithm based on the example above can be found here .

HungarianAlgorithm.com © 2013-2023

HungarianAlgorithm.com uses cookies to provide you with an optimal user experience.

Yes, I accept cookies.

Assignment problem branch and bound.pptx

Recommended

More Related Content

What's hot.

What's hot ( 20 )

Similar to Assignment problem branch and bound.pptx

Similar to Assignment problem branch and bound.pptx ( 20 )

Recently uploaded

Recently uploaded ( 20 )

• 1. 1 ASSIGNMENT PROBLEM BRANCH AND BOUND
• 2. 2 Branch & Bound  The Branch & Bound algorithm is a method commonly used to solve optimization problems. Many problems can be solved using these two methods. Some examples of problems that the Branch & Bound algorithm can solve are Knapsack Problems, Traveling Salesman Problems, Scheduling Problems and many other optimization problems.  The Branch and Bound algorithm is an algorithm that uses a state space tree to solve a problem, in this case it is similar to the backtracking algorithm.
• 3. 3 The way the B&B algorithm works is based on the following two principles.  1. Recursively divide the status space into smaller spaces and minimize “costs” on these spaces. This process is called branching.  2. Branching will be equivalent to brute-force enumeration. To improve performance, bound is used to limit the space in the status that is generated, eliminating candidate solutions that are proven to not contain optimal solutions. As the name implies, this algorithm has a bound or limiting function. This constraint function is useful for delimiting paths that are considered not leading to a solution node. WORKING OF B&B
• 4. 4 Job Assignment Problem o Job Assignment Problem is one of the fundamental combinatorial optimization problems in its most common 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. o There are many methods that can be used to solve Job Assignment Problems.
• 5. 5 Example  The job assignment problem testing will be carried out in one example of the following cases, namely there are 4 jobs and 4 people, each of which has a cost as in table 1.  Table 1 Job Assignment Problem matrix (4 jobs and 4 people) Job 1 Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6
• 6. 6 The assignment problem Solving Job Assignment Problems using Branch and Bound is done by determining the lower limit by adding the minimum cost of each row Minimum Cost of each Row Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6 So that Lower Bound (LB) = 4+5+3+6 = 18
• 7. 7 The assignment problem There are 4 possibilities, namely A doing Job 1, A doing Job 2, A doing Job 3 and A doing Job 4. Calculate the LB of each of these possibilities. Possibility 1: Person 1 (A) does Job 1 Person 1 (A) does Job 1 Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6 Then LB for probability 1 is : 11+5+3+6 = 25
• 8. 8 The assignment problem Possibility 2: Person 1 (A) does Job 2 Person 1 (A) does Job 2 Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6 Then LB for probability 2 is : 4+5+3+6 = 18
• 9. 9 The assignment problem Possibility 3: Person 1 (A) does Job 3 Person 1 (A) does Job 3 Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6 Then LB for probability 3 is : 9+6+7+6 = 28
• 10. 10 The assignment problem Possibility 4: Person 1 (A) does Job 4 Person 1 (A) does Job 4 Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6 Then LB for probability 4 is : 10+5+3+8 = 26
• 11. 11 The assignment problem the node with the minimum value to be expanded is selected, namely A2 with LB = 18. Then the second person (B) is chosen to do the job or assignment.
• 12. 12 The assignment problem There are 3 possibilities, namely B doing job 1, Job 3 or Job 4 (Job 2 is done by A) Possibility 1: Person 2 (A) does Job 1 Person 2 (B) does Job 1 Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6 Then LB for probability 1 is :4+8+3+6 = 21
• 13. 13 The assignment problem Possibility 2: Person 2 (A) does Job 3 Person 2 (B) does Job 3 Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6 Then LB for probability 2 is :4+5+7+6 = 22
• 14. 14 The assignment problem Possibility 3: Person 2 (A) does Job 4 Person 2 (B) does Job 4 Job 1 Job 2 Job 3 Job 4 Person 1 (A) 11 4 9 10 Person 2 (B) 8 6 5 9 Person 3 (C) 7 10 3 10 Person 4 (D) 9 8 11 6 Then LB for probability 3 is :4+9+3+9 = 25
• 15. 15 The assignment problem Next, select the node with the minimum cost to expand, namely B→1
• 16. 16 The assignment problem Next 2 possibilities:  Possibility 1: A does Job 2, B does Job 1, C does Job 3 and D does Job 4 with the cost is 4 + 8 + 3 + 6 = 21.  Possibility 2: A does Job 2, B does Job 1, C does Job 4 and D does Job 3 with the cost is 4 + 8 + 10 + 11 = 33. Then the possibility of 1 is chosen with cost = 21, compared to all the remaining nodes, this cost is the minimum cost so that it is chosen as the solution.
• 17. 17 The assignment problem
• 18. 18 The assignment problem SOLUTION: A2 B1 C3 D4
• 19. 19 The assignment problem Conclusion The use of branch and bound results in a shorter solution because the branch and bound algorithm performs calculations recursively, while still calculating the best value, that is what is known as branching. In addition, the best value is recorded for each calculation, so that it can improve the performance of the algorithm, what is known as bounding.

• Implementation

Job Assignment Problem Algorithm

• September 17, 2023 September 27, 2023

Pseudo code for the Branch and Bound algorithm to solve the Job Assignment Problem:

Implementing the job assignment problem using c++:, implementation of the job assignment problem using javascript:, python code implementation of the job assignment problem:, implementation of the job assignment problem using java:, advantages:, disadvantages:, key points to consider:, interview questions:, real life use cases.

The Branch and Bound algorithm is an optimization technique that systematically divides the problem into smaller subproblems and uses bounds to determine whether a subproblem needs to be further explored. It proceeds by creating a search tree, where each node represents a partial assignment of agents to tasks. The algorithm uses a lower bound to prune branches that cannot lead to an optimal solution and continuously updates an upper bound based on the best solution found so far.

The Job Assignment Problem is a combinatorial optimization problem that aims to assign a set of agents to a set of tasks in a way that minimizes the total cost or maximizes the total profit. It is commonly used in various fields, such as scheduling, resource allocation, and production planning

The Job Assignment Problem is a mathematical problem where we need to assign jobs to workers in the most efficient way. Each worker has some skills and each job requires certain skills. The goal is to find the best assignment that minimizes the total cost or maximizes the total profit.

To solve this problem using the Branch and Bound Algorithm, we follow these steps:

• Generate all possible assignments: Generate all possible combinations of jobs and workers. This creates a tree-like structure where each node represents a potential assignment.
• Calculate the cost of each assignment: For each assignment, calculate the total cost or profit based on the specific conditions. For example, if a worker requires training for a particular job, consider the cost of training.
• Prune inefficient assignments: If we find an assignment with a higher cost than the best assignment found so far, we prune it. This means we ignore that branch of the tree because it cannot lead to an optimal solution.
• Keep track of the best assignment: While exploring the assignment tree, keep track of the best assignment found so far. Update it whenever we find a better assignment with a lower cost or higher profit.
• Continue exploring until all nodes are explored: Explore the assignment tree using a depth-first search approach. Keep exploring until we have checked all possible assignments.
• Output the best assignment: Once we finish exploring the entire tree, output the best assignment found, which will be the optimal solution to the Job Assignment Problem.

In summary, the Branch and Bound Algorithm for the Job Assignment Problem involves generating all possible assignments, calculating their costs or profits, pruning inefficient assignments, and keeping track of the best assignment found so far. By exploring the assignment tree and finding the optimal solution, we can assign jobs to workers in the most efficient way possible.

Let’s understand it through an example:

Suppose there are three workers (W1, W2, W3) and three jobs (J1, J2, J3). The cost matrix for the jobs is as follows:

The goal is to assign each worker to a job in a way that minimizes the total cost.

• Branching: Initially, each worker can be assigned to any job, so we have three possible assignments as branches: (W1-J1, W2-J2, W3-J3), (W1-J1, W2-J3, W3-J2), (W1-J2, W2-J1, W3-J3).
• Evaluation: For each branch, we calculate the total cost by summing up the costs of assigned jobs. For example, for the first branch (W1-J1, W2-J2, W3-J3), the total cost is 10+7+6=23.
• Pruning: If, at any point, the partial solution has exceeded the minimum cost found so far, we can prune that branch as it cannot lead to an optimal solution. For instance, if the total cost of a branch is already greater than or equal to the minimum cost found so far (let’s say it is 30), we can prune that branch.
• Backtracking: The algorithm backtracks to the previous node and explores the next possible assignment for the worker, following the same process of branching, evaluation, and pruning.
• Completion: The algorithm continues exploring various assignments until all possible branches have been evaluated. The minimum cost obtained from all the feasible assignments is the optimal solution for the Job Assignment Problem.

In this example, the Branch and Bound algorithm would explore all possible assignments and calculate the total cost for each assignment, pruning suboptimal branches along the way. It would ultimately find the assignment that minimizes the total cost, giving the optimal solution to the Job Assignment Problem.

The time complexity of the Branch and Bound algorithm heavily depends on the number of nodes explored in the search tree. In the worst case, it can be exponential, but the use of bounds can greatly reduce the search space. The average time complexity is often much lower than the worst case, especially with effective pruning strategies.

Let’s consider two arrays of size M and N, where array of size M represents the applicants, and N represents the Jobs. Then, The  time complexity  of this algorithm is O(M*N). This is because the algorithm uses a double for loop to iterate through the M x N matrix.  The  space complexity  of this algorithm is O(M+N). This is because it uses two arrays of size M and N to track the applicants and jobs.

First have a look on the main components of the code:

• Node structure : This structure represents a node in the search tree. It includes the cost for the worker to do the job ( pathCost ), the total cost ( cost ), the IDs for the worker and job ( workerID  and  jobID ), and a list of jobs already assigned ( assigned ).
• newNode function : This function creates a new node, copies the jobs already assigned from the parent node, assigns the new job to the worker, and returns the new node.
• calculateCost function : This function calculates the cost for a worker to do a job. It finds the minimum cost job that has not been assigned yet for each worker (after worker x).
• comp structure : This is a comparison function for the priority queue. It orders the nodes by their cost in ascending order.
• printAssignments function : This function prints the worker-job assignments from the root to the input node.
• findMinCost function : This is the main function that implements the branch and bound method. It uses a priority queue to store the live nodes. It starts by creating a dummy root node and adding it to the queue. Then, it enters a loop that continues until the queue is empty. In each iteration of the loop, it takes out the node with the minimum cost, generates its children (i.e., the nodes obtained by assigning the next worker to one of the remaining jobs), updates their costs, and adds them to the queue. When a node representing a complete assignment (i.e., all workers are assigned a job) is chosen from the queue, it prints the assignments and returns the cost.
• main function : This function sets up the cost matrix and calls the  findMinCost  function to solve the problem. It then prints the optimal cost.

Now let’s implement the code:

Certainly! Let’s break down and explain the JavaScript code for solving the job assignment problem using the branch and bound approach.

Problem Description: The job assignment problem involves assigning a set of workers to a set of jobs in such a way that the total cost is minimized. Each worker can be assigned to only one job, and each job must be assigned to exactly one worker.

Here’s the step-by-step explanation of the code:

Node Class :

• We define a Node class to represent a node in the search tree. Each node contains information about the current state of the assignment, including the worker and job IDs, the assignment status, the path cost, and the total cost.

calculateCost Function :

• The calculateCost function calculates the cost of assigning a worker to a job. It takes into account the remaining unassigned jobs and chooses the one with the minimum cost.

printAssignments Function :

• The printAssignments function traces back from the final node to the root node, printing the assignments made along the way. It avoids printing assignments where the worker and job IDs are both -1 (indicating an unassigned job).

findMinCost Function :

• The findMinCost function implements the branch and bound algorithm to find the minimum cost assignment.
• We maintain a priority queue ( pq ) to explore nodes with the lowest estimated cost first.
• We start with an empty assignment (root node) and iteratively explore child nodes, adding them to the priority queue.
• We calculate the estimated cost for each child node, considering the path cost and the cost of the remaining unassigned jobs.
• The algorithm terminates when all worker assignments have been made (i.e., i === N ).
• It keeps track of the minimum cost and the corresponding node that achieved it.
• Once the search is complete, it calls printAssignments to print the optimal assignments.

Main Section :

• In the main section, we define the cost matrix, which represents the cost of assigning each worker to each job.
• We call the findMinCost function to find the optimal assignment and print the minimum cost.
• The code prints the optimal assignments and the minimum cost.

This code effectively solves the job assignment problem using a branch and bound approach. It explores the solution space efficiently, considering the cost of assignments and finding the optimal assignment that minimizes the total cost.

The provided Python code implements an algorithm to solve the Assignment Problem using a branch and bound approach. The Assignment Problem involves finding the most cost-efficient way to assign a set of workers to a set of jobs, such that each worker is assigned to exactly one job and each job is assigned to exactly one worker, while minimizing the total cost. Here’s a step-by-step explanation of the code:

Importing the heapq module:

• The code starts by importing the heapq module, which is used to create and manage a priority queue (min-heap).

Define the number of workers and jobs:

• N is set to 4, indicating there are 4 workers and 4 jobs to be assigned.

Define a Node class:

• The Node class is used to represent nodes in the search tree. Each node contains information about the current state of the assignment problem.
• parent : A reference to the parent node in the search tree.
• pathCost : The cumulative cost of assignments from the root to this node.
• cost : An estimate of the total cost (pathCost + estimated future cost) of this node.
• workerID : The ID of the worker currently being assigned.
• jobID : The ID of the job currently being assigned.
• assigned : A boolean list representing which jobs are already assigned to workers.

Define a function calculateCost :

• This function calculates the cost of assigning a worker to a job, taking into account the remaining unassigned jobs and workers. It uses a greedy approach to find the minimum cost for each remaining worker.

Define a function printAssignments :

• This function traces back the assignment path from the final node to the root node and prints the assignments made in the optimal solution.

Define a function findMinCost :

• This is the main function that performs the branch and bound search to find the optimal assignment.
• It initializes a priority queue ( pq ) and starts with a root node representing no assignments.
• The algorithm repeatedly explores nodes in the search tree, considering all possible assignments while maintaining a priority queue sorted by the estimated cost.
• The minimum cost and the corresponding node ( minNode ) are updated whenever a better assignment is found.
• The function eventually returns the optimal cost and prints the optimal assignments.

Define the cost matrix costMatrix :

• The costMatrix represents the cost of assigning each worker to each job.

Call findMinCost to solve the Assignment Problem:

• The findMinCost function is called with the costMatrix , and it returns the optimal cost.
• The optimal cost is then printed.

Example cost matrix costMatrix :

• In this example, the cost matrix is provided with arbitrary costs for illustration purposes.

The code uses a branch and bound technique to efficiently explore the solution space, reducing the number of nodes explored and finding the optimal solution to the Assignment Problem. The optimal assignments and their associated costs are printed as the output.

Explanation of Steps:

• Define the number of jobs and the cost matrix in the jobs and costMatrix variables, respectively.
• Create a class Node to represent a node in the branch and bound tree. Each node keeps track of the current assignment, assigned worker, assigned job, level, and cost.
• Implement the calculateCost function to calculate the cost of a given assignment. It iterates through the assigned jobs and determines the total cost.
• Implement the findMinCost function to find the minimum cost for a given job based on the assigned workers.
• Implement the branchAndBound function, which performs the actual branch and bound algorithm. It initializes the root node and a minimum cost variable. Then it starts a loop until the current node level reaches the last job.
• In each iteration, the current node’s level is incremented. For each unassigned worker, it creates a new node with an updated assignment, assigned worker, assigned job, and cost. If the new node represents a complete assignment, it checks if the cost is lower than the current minimum cost and updates the minimum cost and assignment accordingly. If not, it calculates a bound based on the current cost and checks if it is lower than the minimum cost. If so, it updates the current node to the new node.
• Finally, the minimum cost and optimal assignment are printed.
• In the main method, the branchAndBound function is called to solve the job assignment problem.

Note: This implementation assumes that the number of workers is the same as the number of jobs, and the cost matrix is provided. Feel free to modify the code based on your specific problem requirements.

• Efficient solution: The Branch and Bound algorithm guarantees an optimal solution to the job assignment problem by exploring only a subset of the possible solutions and disregarding unpromising branches.
• Improved performance: Compared to brute force algorithms, the Branch and Bound approach significantly reduces the time and computational resources required to find the optimal assignment.
• Flexibility: The algorithm can be customized to incorporate additional constraints or preferences in the job assignment problem, making it adaptable to various real-life scenarios.
• Reduced complexity: The algorithm can handle a large number of job and worker combinations without exponentially increasing the computation time.
• Complexity in implementation: Implementing the Branch and Bound algorithm for the job assignment problem requires a good understanding of the problem and algorithmic concepts, making it challenging for beginners or those not well-versed in programming.
• Algorithmic limitations: In some cases, the job assignment problem may have continuous or floating-point variables, which can pose challenges for the Branch and Bound algorithm, as it is primarily designed for discrete optimization problems.
• Suboptimality in subproblem solutions: The Branch and Bound algorithm may produce suboptimal solutions at intermediate steps, which could lead to an overall suboptimal assignment if not properly addressed.
• Increasing memory requirements: As the number of job and worker combinations increases, the memory requirements of the algorithm can grow significantly, potentially exceeding the available resources on the system. This can limit the scalability of the solution. Some key takeaways when using the Branch and Bound algorithm approach for the Job Assignment Problem are:
• Job Assignment Problem: The Job Assignment Problem refers to the task of assigning a set of workers to a set of jobs, with each worker having a specific skill set and each job requiring a certain skill set.
• Branch and Bound Algorithm: The Branch and Bound algorithm is used to solve combinatorial optimization problems by systematically enumerating all possible combinations of solutions and pruning the branches that cannot lead to better solutions.
• Define the objective function: Before implementing the Branch and Bound algorithm, it is important to define the objective function, which determines the value associated with each job-worker assignment.
• Create an initial upper bound: A good initial upper bound estimate can be obtained by assigning each job to the best available worker based on the objective function.
• Define the bounds: Branch and Bound algorithm involves branching the problem into subproblems and evaluating their bounds. The bounds should be defined such that they are higher than the optimal value but lower than any other feasible assignment.
• Branching strategy: Efficient branching strategies help in reducing the number of subproblems to be explored. One common branching strategy is to split the problem based on the remaining unassigned workers or jobs.
• Pruning conditions: To optimize the algorithm, it is crucial to define pruning conditions to avoid exploring subproblems that cannot provide better solutions than the current best solution.
• Implement the backtracking mechanism: The backtracking mechanism helps in tracking the best solution found so far and updating it whenever a better solution is encountered.
• Explore the subproblems: The Branch and Bound algorithm explores the generated subproblems, evaluates their bounds, and recursively continues to explore the subproblems with the highest potential for better solutions.

By considering these key aspects and implementing the Branch and Bound algorithm, the Job Assignment Problem can be efficiently solved by finding the optimal worker-job assignments.

• What is the job assignment problem and how does it relate to the branch and bound algorithm?
• Explain the steps involved in the branch and bound algorithm for solving the job assignment problem.
• How do you define the objective function in the job assignment problem?
• Describe the process of creating the initial state for the branch and bound algorithm.
• What is the role of the bounding function in the branch and bound algorithm for the job assignment problem?
• How do you determine the search space in the branch and bound algorithm?
• Discuss the concept of pruning in the branch and bound algorithm for the job assignment problem.
• What are the advantages and limitations of using the branch and bound algorithm for solving the job assignment problem?
• How would you handle tie-breaking situations in the branch and bound algorithm for the job assignment problem?
• Can you provide an example of how the branch and bound algorithm can be applied to solve a specific job assignment problem?
• How would you handle constraints such as availability, skills, or preferences of individuals in the job assignment problem using the branch and bound algorithm?
• How would you deal with large-scale job assignment problems in terms of computational complexity and scalability while using the branch and bound algorithm?
• Discuss any optimizations or heuristics that can be used in conjunction with the branch and bound algorithm for the job assignment problem.
• In your opinion, what are the main challenges in solving the job assignment problem using the branch and bound algorithm, and how would you approach them?
• Can you explain any alternative algorithms or techniques that can be used to solve the job assignment problem, and how they compare to the branch and bound algorithm in terms of efficiency and accuracy?
• Production planning: In manufacturing industries, the job assignment problem can be used to optimize the assignment of tasks to machines or workers, considering different factors such as skill levels, availability of resources, and production capacities. The branch and bound algorithm can help find the optimal assignment that minimizes costs or maximizes productivity.
• Resource allocation in healthcare: In hospitals or healthcare facilities, the job assignment problem can be applied to optimize the allocation of medical staff, such as doctors or nurses, to different tasks or patients. The branch and bound algorithm can be used to maximize the efficiency of resource utilization and minimize waiting times or patient dissatisfaction.
• Transportation planning: In logistics and transportation industries, the job assignment problem can be used to optimize the allocation of vehicles or drivers to different delivery routes or tasks. The branch and bound algorithm can help find the optimal assignment that minimizes travel costs, maximizes delivery efficiency, or ensures timely delivery.
• Team formation in project management: In project management, the job assignment problem can be used to optimize the formation of project teams by assigning appropriate tasks to different team members based on their expertise, availability, and workload. The branch and bound algorithm can help find the optimal assignment that maximizes team productivity and minimizes completion time.
• Shift scheduling in workforce management: In industries with shift-based work, such as call centers or manufacturing plants, the job assignment problem can be used to optimize shift scheduling by assigning suitable employees to different shifts or time slots. The branch and bound algorithm can help find the optimal assignment that satisfies workload requirements, minimizes overtime, and maximizes employee satisfaction.
• Allocation of computing resources in cloud computing: In cloud computing environments, the job assignment problem can be used to optimize the allocation of computing resources, such as virtual machines or containers, to different tasks or applications. The branch and bound algorithm can help find the optimal assignment that minimizes resource wastage, maximizes resource utilization, and meets performance or deadline requirements.
• Classroom scheduling in educational institutions: In schools or universities, the job assignment problem can be used to optimize the allocation of classrooms or venues to different academic activities, such as lectures, exams, or practical sessions. The branch and bound algorithm can help find the optimal assignment that minimizes clashes, maximizes room utilization, and satisfies various constraints such as room capacities or equipment requirements.

Q1: What is the Job Assignment Problem?

A1: The Job Assignment Problem is a mathematical problem that seeks to assign a set of jobs to a set of workers in the most efficient manner possible, considering the skills and capacities of the workers and the requirements of the jobs.

Q2: What is the Branch and Bound Algorithm approach?

A2: The Branch and Bound Algorithm approach is a technique used to solve optimization problems by systematically exploring the solution space through branching and bounding techniques. It involves dividing the problem into smaller subproblems, searching for feasible solutions, and eliminating branches that cannot lead to an optimal solution.

Q3: How does the Branch and Bound Algorithm solve the Job Assignment Problem?

A3: The Branch and Bound Algorithm solves the Job Assignment Problem by generating and exploring a search tree of possible assignments. It uses bounds and heuristics to prune unnecessary branches, reducing the search space and improving efficiency. It continues until all possible assignments have been examined, identifying the optimal assignment with the minimum cost.

Q4: What are the advantages of using the Branch and Bound Algorithm for the Job Assignment Problem?

A4: The advantages of using the Branch and Bound Algorithm for the Job Assignment Problem include:

• Ability to find the optimal solution by systematically exploring all possible assignments.
• Efficiency in reducing the search space through pruning, resulting in improved performance.
• Flexibility to incorporate various constraints and objective functions.

Q5: What are the limitations of using the Branch and Bound Algorithm for the Job Assignment Problem?

A5: Some limitations of using the Branch and Bound Algorithm for the Job Assignment Problem include:

• The computational complexity can increase exponentially with the problem size, making it infeasible for very large instances.
• The algorithm may require additional techniques or heuristics to handle specific constraints or variations of the problem.
• The time required to find the optimal solution may be significant for complex problems.

Q6: Are there any alternative approaches or algorithms for solving the Job Assignment Problem?

A6: Yes, apart from the Branch and Bound Algorithm, there are other approaches and algorithms available for solving the Job Assignment Problem, such as the Hungarian Algorithm, the Genetic Algorithm, and Linear Programming techniques. The choice of the algorithm depends on the problem size, constraints, and specific requirements.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

International Conference on Innovative Techniques and Applications of Artificial Intelligence

SGAI-AI 2022: Artificial Intelligence XXXIX pp 19–33 Cite as

Job Assignment Problem and Traveling Salesman Problem: A Linked Optimisation Problem

• Akinola Ogunsemi 9 ,
• John McCall 9 ,
• Mathias Kern 11 ,
• Benjamin Lacroix 9 ,
• David Corsar 10 &
• Gilbert Owusu 11  
• Conference paper
• First Online: 05 December 2022

526 Accesses

Part of the Lecture Notes in Computer Science book series (LNAI,volume 13652)

Linked decision-making in service management systems has attracted strong adoption of optimisation algorithms. However, most of these algorithms do not incorporate the complexity associated with interacting decision-making systems. This paper, therefore, investigates the linkages between two classical problems: job assignment problem and travelling salesman problem (JAPTSP) of a service chain system where service personnel perform tasks at different locations. We formulate a novel mathematical model from a linked optimisation perspective with objectives to minimise job cost and total travel distance simultaneously. We present three algorithmic approaches to tackling the JAPTSP: Nondominated Sorting Genetic Algorithm for Linked Problem (NSGALP), Multi-Criteria Ranking Genetic Algorithm for Linked Problem (MCRGALP), and Sequential approach. We evaluate the performance of the three algorithmic approaches on a combination of JAP and TSP benchmark instances. Results show that selecting an appropriate algorithmic approach is highly driven by specific considerations, including multi-objective base performance metrics, computation time, problem correlation and qualitative analysis from a service chain perspective.

• Service chain optimisation
• Linked optimisation problem
• Multi-criteria decision making
• Multi-objective optimisation

Supported by BT and The DataLab.

This is a preview of subscription content, access via your institution .

Buying options

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Ibrahimov, M., Mohais, A., Schellenberg, S., Michalewicz, Z.: Evolutionary approaches for supply chain optimisation: part i: single and two-component supply chains. IJICC 5 (4), 444–472 (2012)

CrossRef   MathSciNet   Google Scholar  

Bonyadi, M.R., Michalewicz, Z., Barone, L.: The travelling thief problem: The first step in the transition from theoretical problems to realistic problems. In: IEEE CEC. IEEE 2013 , 1037–1044 (2013)

Google Scholar  

Vieira, D.K.S., Soares, G.L., Vasconcelos, J.A., Mendes, M.H.S.: A genetic algorithm for multi-component optimization problems: the case of the travelling thief problem. In: Hu, B., López-Ibáñez, M. (eds.) EvoCOP 2017. LNCS, vol. 10197, pp. 18–29. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55453-2_2

CrossRef   Google Scholar  

Xie, F., Potts, C.N., Bektaş, T.: Iterated local search for workforce scheduling and routing problems. JH, vol. 23, no. 6, pp. 471–500, 2017

Conti, G., Dow, A.: The impacts of covid-19 on health visiting services in england: Foi evidence for the first wave (2020)

Castillo-Salazar, A., Landa-Silva, D., Qu, R.: A survey of workforce scheduling and routing (2012)

Castillo-Salazar, J.A., Landa-Silva, D., Qu, R.: A greedy heuristic for workforce scheduling and routing with time-dependent activities constraints (2015)

Camci, F.: The travelling maintainer problem: integration of condition-based maintenance with the travelling salesman problem. JORS 65 (9), 1423–1436 (2014)

Zhang, T., Gruver, W., Smith, M.H.: Team scheduling by genetic search. In: IPMM’99 (Cat. No. 99EX296), vol. 2. IEEE, pp. 839–844 (1999)

Assaf, M., Ndiaye, M.,: Multi travelling salesman problem formulation. In: 4th ICIEA. IEEE 2017 , 292–295 (2017)

Shuai, Y., Yunfeng, S., Kai, Z.: An effective method for solving multiple travelling salesman problem based on nsga-ii. SSCE 7 (2), 108–116 (2019)

Stolk, J., Mann, I., Mohais, A., Michalewicz, Z.: Combining vehicle routing and packing for optimal delivery schedules of water tanks. OR Insight 26 (3), 167–190 (2013)

Chen, L., Langevin, A., Lu, Z.: Integrated scheduling of crane handling and truck transportation in a maritime container terminal. EJOR 225 (1), 142–152 (2013)

CrossRef   MATH   Google Scholar  

Chen, T.-L., Cheng, C.-Y., Chen, Y.-Y., Chan, L.-K.: An efficient hybrid algorithm for integrated order batching, sequencing and routing problem. IJPE 159 , 158–167 (2015)

Moons, S., Ramaekers, K., Caris, A., Arda, Y.: Integrating production scheduling and vehicle routing decisions at the operational decision level: a review and discussion. CIE 104 , 224–245 (2017)

Chu, P.C., Beasley, J.E.: A genetic algorithm for the generalised assignment problem. COR 24 (1), 17–23 (1997)

MathSciNet   MATH   Google Scholar  

Gerhard, R.: The traveling salesman: computational solutions for tsp applications. Lect. Notes Comput. Sci. 840 , 1–223 (1994)

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE TEC 6 (2), 182–197 (2002)

Muhuri, P.K., Ashraf, Z., Lohani, Q.D.: Multiobjective reliability redundancy allocation problem with interval type-2 fuzzy uncertainty. IEEE TFS 26 (3), 1339–1355 (2017)

Hwang, C.-L., Yoon, K.: Methods for multiple attribute decision making. In: Lecture Notes in Economics and Mathematical Systems, vol 186, pp. 58–191 Springer, Berlin, Heidelberg (1981). https://doi.org/10.1007/978-3-642-48318-9_3

Rahim, R., et al.: Topsis method application for decision support system in internal control for selecting best employees. In: JP: Conference Series, vol. 1028, no. 1. IOP Publishing, p. 012052 (2018)

Triantaphyllou, E., Shu, B., Sanchez, S.N., Ray, T.: Multi-criteria decision making: an operations research approach. EEEE 15 (1998), 175–186 (1998)

Luo, G., Wen, X., Li, H., Ming, W., Xie, G.: An effective multi-objective genetic algorithm based on immune principle and external archive for multi-objective integrated process planning and scheduling. IJAMT 91 (9), 3145–3158 (2017)

Geetha, T., Muthukumaran, K.: An observational analysis of genetic operators. IJCA 63 (18), 24–34 (2013)

Legillon, F., Liefooghe, A., Talbi, E.-G.: Cobra: A cooperative coevolutionary algorithm for bi-level optimization. In: IEEE CEC. IEEE 2012 , 1–8 (2012)

Ibrahimov, M.: Evolutionary algorithms for supply chain optimisation. Ph.D. dissertation (2012)

Lin, C.K.Y.: Solving a location, allocation, and capacity planning problem with dynamic demand and response time service level. MPE, vol. (2014)

Ullrich, C.A.: Integrated machine scheduling and vehicle routing with time windows. EJOR 227 (1), 152–165 (2013)

CrossRef   MathSciNet   MATH   Google Scholar  

Nourmohammadi, A., Zandieh, M.: Assembly line balancing by a new multi-objective differential evolution algorithm based on topsis. IJPR 49 (10), 2833–2855 (2011)

Beasley, J.E.: Or-library: distributing test problems by electronic mail. JORS 41 (11), 1069–1072 (1990)

Reinelt, G.: Tsplib95. IWR, Heidelberg 338 , 1–16 (1995)

Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE TEC 3 (4), 257–271 (1999)

Bezerra, L.C.T., López-Ibáñez, M., Stützle, T.: An empirical assessment of the properties of inverted generational distance on multi- and many-objective optimization. In: Trautmann, H. (ed.) EMO 2017. LNCS, vol. 10173, pp. 31–45. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-54157-0_3

Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Da Fonseca, V.G.: Performance assessment of multiobjective optimizers: An analysis and review. IEEE TEC 7 (2), 117–132 (2003)

Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms — a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 292–301. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0056872

Manson, J.A., Chamberlain, T.W., Bourne, R.A.: Mvmoo: Mixed variable multi-objective optimisation. JGO 80 (4), 865–886 (2021)

Download references

Author information

Authors and affiliations.

National Subsea Centre, Dyce, UK

Akinola Ogunsemi, John McCall & Benjamin Lacroix

Robert Gordon University, Aberdeen, UK

David Corsar

BT Applied Research, Ipswich, UK

Mathias Kern & Gilbert Owusu

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Akinola Ogunsemi .

Editor information

Editors and affiliations.

University of Portsmouth, Portsmouth, UK

DFKI: German Research Center for Artificial Intelligence, Oldenburg, Germany

Frederic Stahl

Rights and permissions

Reprints and Permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper.

Ogunsemi, A., McCall, J., Kern, M., Lacroix, B., Corsar, D., Owusu, G. (2022). Job Assignment Problem and Traveling Salesman Problem: A Linked Optimisation Problem. In: Bramer, M., Stahl, F. (eds) Artificial Intelligence XXXIX. SGAI-AI 2022. Lecture Notes in Computer Science(), vol 13652. Springer, Cham. https://doi.org/10.1007/978-3-031-21441-7_2

Download citation

DOI : https://doi.org/10.1007/978-3-031-21441-7_2

Published : 05 December 2022

Publisher Name : Springer, Cham

Print ISBN : 978-3-031-21440-0

Online ISBN : 978-3-031-21441-7

eBook Packages : Computer Science Computer Science (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Find a journal
• Publish with us