Generalized Assignment Problem using Excel Solver

1.   Introduction:

1.1.        Generalized Assignment Problem

In  Generalized Assignment Problem for optimization is daily life problem in which we have n number of tasks/assignments and m number of machines/labor available to perform that tasks. Each machine/labor have some cost for performing specific task. There could be time constraints for each worker to do specific job and some profit by ith machine for jth task. This problem can be a maximize problem (maximize the profit) or minimization constrained optimization problem (minimize the cost).

1.2.        Problem Statement:

Here, we have minimization constrained optimization problem in which each worker i have total available time Ti and a worker i require tij time for a task j. The cost of ith worker is Cij for jth task. No worker can have more than k tasks assigned. If possible, each worker in the subset W should have p percent of their available time free and each worker in W must not have only one task assigned. The set L of large tasks should be uniformly distributed among all workers. The set D of novice workers should not be assigned more than h tasks.

1.3. Excel Solver:

Solver ™ is a tool in Microsoft Excel for solving constrained optimization problems i.e. maximize or minimize an objective function subject to available constraints.

In Excel it is not by default included so, before using this tool we have to add this into Excel. Following are few steps for adding into excel.

  1. Click Options and a window will pop up.
  2. Go to FILE menu in top left corner of Excel (for MS Office 2007, click office button on top left corner and click Excel option)
  3. Select ad-ins (in bottom select Excel ad ins). Another window will pop up. (As shown in following figure 1)
  4. Check Solver and click OK. Solver will be installed in your Excel.
  5. This will visible/available to use in DATA menu and top right coroner of it.

2.   Problem Formulation:

Objective Function:

Minimize:

\sum_{i=1}^{n} \sum_{j=1}^{m} x_{ij}C_{ij}

where, i is worker number and j is task number and x_{ij} = i^{th} worker doing j_{th} task is binary (either zero or one). i.e. either i^{th} worker is doing j^{th} task or not.

Subject to:

\sum_{j=1}^{m} x_{nj} t_{nj} \leqslant Tn

for each, n=1,2,3,...

  • One task one worker

\sum_{i=1}^{n} x_{in} = 1

Condition for novice workers:

\sum_{j=1}^{15} x_{1j} \leqslant 3

\sum_{j=1}^{15} x_{3j} \leqslant 3

For rest of workers

\sum_{j=1}^{15} x_{nj} \leqslant 5

n=2,4,5

Condition for W set workers

\sum_{j=1}^{15} x_{1j} \geqslant 1

\sum_{j=1}^{15} x_{3j} \geqslant 1

For Large task set L

x_{i3}+x_{i5}+x_{i13}+x_{i14}+x_{i15}=1

for i=1,2,3,4,5

With addition to these there is condition that workers of group W must be 15% free time available from total time. So, total time available for them must be

New time = old time =(old time \times 0.15)

3. Problem Solving using Excel Solver

As we have Problem in formula form and we know the objective functions and Constraints. Now we are going to implement it in Excel solver according to available data and in formula (variables) form.

3.1.        Data Entry

We are going to enter the date (available data of ith worker for jth task) in excel in form of tables. Data for cost of each worker is available and time used is available and total time is given and conditions for W and D sets are also given. First we put all the available data into Excel to use it for solving our Optimization problem.

  • Table for Cost

As we have 5 workers and 15 tasks and each worker have specific cost for doing specific task. So, there will be a table of 15x5 for cost of each worker. This is shown in following figure 2.

  • Time Required to each worker

There is also condition that worker i requires tij time for doing task j. So, there will also be a table of 15x5 (according to given problem) for time required to each worker for doing specific job. This is shown in figure below. (figure 3)

3.2.        Defining Variables:

We are required to find that which task is done by which worker. So, as a whole we have 15 tasks and 5 workers so there will be 75 variables. This will be placed in a table. This table is what we are going to find actually. If the value of element in this table is one (1) which means that ith worker is doing jth task and if value is zero (0) which means that ith worker is NOT doing jth task. So, as our objective function is to minimize the cost. So when xij is zero, which means we are not considering that cost and if it is one means that cost is adding. (figure 4)

3.3.      Objective Function:

Our objective function is to minimize the cost. As described in problem formulation that the sum of all the products of selected xij must be minimum. So we have table of cost of each xij and we can sum all the products of xij. When a worker is not working, its cost will not be considered. So, write a formula in excel such that:

= SUMPRODUCT(I3:M17, B3:F17)

Where, I3:M17 is table of cost of workers

B3:F17 is table of variables of xij

This is equivalent to above described objective function in MS Excel.

3.4.      Conditions:

3.4.1. Binary variables

As discussed above that either a worker i is working task j or not. Which means that the variables in table for xij is binary.

3.4.2. One task by one worker

It was stated in given problem that one task will be assigned to only one worker. To handle this condition we placed a check such that sum of task j for all workers i.e. in figure 4, the right most column has the formula that

=sum (I3:M3)               (For all rows)

This will allow us to put condition in excel solver. (Will be discussed in following sections)

3.4.3. Total time Available

There is condition for each worker that he could work for a specific total time. His time must not be exceeded.

As a worker can do more than one task depending upon time available so, we have to place a check here for this condition to use it as constraint in excel solver. So, the sum of all the time required for ith worker at jth task he is doing, must be less than or equal to ith worker total time available.

=SUMPRODUCT(Q3:Q17, I3:I17)

Where,             Q3:Q17 is time for 1st worker for tasks

I3:i17 is variable in which 1st worker is performing task

Similarly, this will be placed for all workers.

3.4.4. L Group tasks:

There is L group of tasks which are large tasks and must be uniformly distributed to each worker i.e. if one task is assigned to ith worker, other task from this group must not be assigned to that worker. Formula for handling this condition is described above. In excel it is handled in same way. The sum of large tasks for a worker must be equal to one. So, in a box an excel formula is placed such that;

=SUM(I5,I7,I15,I16,I17)

Which means that among 3rd, 5rh, 13th, 14th and 15th tasks’ sum. And in condition box of excel solver it will be said that this sum must be equal to 1. Similarly for all other workers.

3.5. Excel Solver:

Now, putting these conditions into excel solver. Go to DATA in menu bar and find for Solver. Click it and a window for solver parameter will appear. (Figure 6)

Generalized Assignment Problem using Excel Solver

 

  1. Set objective is for objective function to be maximize or minimize. Select the box in which objective function was defined (in which formula was put).
  1. By changing variable cells is for variables to be determined. In our problem these are the xij for ith worker and jth task. We will provide whole table here.
  1. Subject to constraints will contain all the constraints and the conditions for solving the optimization problem. To add constraints, click Add in right side of this window.
  • Next given condition is that one task will be done by only one worker. So, as we place formula in excel of all the workers’ sum for jth task. Here we put condition that this sum must be equal to zero.
  • First condition is that variables will be binary i.e. either the worker is doing jth task or not.
  • Now, we have specific time available for each worker. Here 3rd constraint is to handle that sum of all the time for ith worker performing multiple tasks must be less than or equal to total time available and written in row Q19 to U19.
  • Now, chose the method you want to solve your problem with. Here we will chose simplex LP method. Also don’t forget to check the box saying that all the variables are non-negative.

Click on solve button in bottom and wait for solution to appear in objective function.

Now, add other constraints as given in problem in solver.

3.5.1. Constraints:

 

Further constraints are (in ascending order of above figure).

  1. Worker 1 of group W must be assigned more than one tasks
  2. Novice worker 1 should not assign more than 3 tasks
  3. All other workers must be assigned less than or equal to 5 tasks.
  4. Novice worker 3 should not assign more than 3 tasks
  5. All variables must be either 0 or 1.
  6. Large tasks should be uniformly assigned to each worker.
  7. Worker 1 of group W must be assigned more than one tasks
  8. Each task must be assigned to one worker only.
  9. Total time of ith worker for jth task must be less than total time available for ith worker.
  10. Check the non-negative variable box so that it consider all the variables to be positive.

3.5.2. Final Results.

Finally, after all these conditions and constraints the optimized results will be follow.

Final Optimized Results of Generalized Assignment Problem using Excel Solver
Final Optimized Results of Problem using Excel Solver

 

For any query and assistance feel free to contact us and like facebook page for more updates. 🙂

Asad Ullah

I am MSc Electrical Scholar under a fellowship program. Working with Modeling and Simulation software related to my field are my activities in leisure.

What do you think?