Operations Research in R — Assignment Problem

R for Industrial Engineers

Operations Research in R — Assignment Problem

Exploring the “lpSolve” R package

Image by Momentista available at Unsplash

Assignment Problem

The assignment problem is a special case of linear programming problem; it is one of the fundamental combinational optimization problems in the branch of optimization or operations research in mathematics. Its goal consists in assigning m resources (usually workers) to n tasks (usually jobs) one a one to one basis while minimizing assignment costs. As a general rule, all jobs must be performed by exactly one worker and every worker must be assigned exclusively to one job. Any worker can be assigned to perform any job, incurring in some cost that may vary depending on the work-job assignment.

Basic Notation:

• m = number of worker ( i = 1 … m )
• n = number of jobs ( j = 1 … n )
• c i,j = unit cost of assigning worker i to job j
• x i,j = worker i assigned to job j (1 if assigned, 0 otherwise)

Note: m (number of workers) must be equal to n (number of jobs).

Formulation:

LP Assignment Problem — Formulation

LP Assignment Problem — Diagram

The lpSolve package from R contains specific functions for solving linear programming assignment problems. For the following example, let’s consider the following mathematical model to be solved:

LP Assignment Problem — Example

Let’s take a look at the R code!

Solution:

LP Assignment Problem — Solution

Total assignment cost: $27

The table above shows the optimum combination of worker i assigned to the job j while satisfying the constraints. Worker 1 must be assigned to Job 2, Worker 2 to Job 1 and Worker 3 to Job 3, respectively. There is no other possible combination of assignments that will lead to a lower assignment cost.

Concluding Thoughts

The assignment problem represents a special case of linear programming problem used for allocating resources (mostly workforce) in an optimal way; it is a highly useful tool for operation and project managers for optimizing costs. The lpSolve R package allows us to solve LP assignment problems with just very few lines of code. While there are other free optimization software out there (e.g. GAMS, AMPL, TORA, LINDO), having stored an LP assignment problem R code in your personal code library could save you a significant amount of time by not having to write the formulation from scratch, but instead by only having to change the coefficients and signs of the corresponding matrix.

— —

If you found this article useful, feel welcome to download my personal codes on GitHub . You can also email me directly at [email protected] and find me on LinkedIn . Interested in learning more about data analytics, data science and machine learning applications in the engineering field? Explore my previous articles by visiting my Medium profile . Thanks for reading.

- Robert