2
$\begingroup$

I have a problem at work which is the redistribution of man days over a project period. We have it in an EXCEL-sheet and man days are always shifted etc. For each month you have a monthly sum of man days from different activities from a worker. What the redistribution should do is readjusting the man days for each month for all activities to reach a treshold value which is set. I started to program the thing in EXCEL VBA but now I am stuck because I don't know how to distribute it to get the treshold value for each month. I think it can be solved via matrix calculation because it seems to me it is a linear optimization problem. Could anyone point me in the right direction - especially what kind of calculation is needed to solve this?

Treshold value: 7

The following (manual) algorithm checks if the monthly sum is above or below the treshold value. Then it picks the activity with most man days in column and shifts a day to the next column or takes a days from the next column until treshold value is reached. Then it continues to the next column until all are aligned to treshold value but I am looking for a better or faster way to do it if possible.

Iterations:

           M M M M M M M M M M M Start   A1 3 1 3 1 3 3 3 3 3 3 1         A2 3 3 2 3 1 3 1 2 1 3 1         A3 3 3 1 3 2 2 1 3 3 2 3         SU 9 7 6 7 6 8 5 8 7 8 5              M M M M M M M M M M M  1. Ite  A1 2 2 3 1 3 3 3 3 3 3 1         A2 3 3 2 3 1 3 1 2 1 3 1         A3 3 3 1 3 2 2 1 3 3 2 3         SU 8 8 6 7 6 8 5 8 7 8 5              M M M M M M M M M M M  2. Ite  A1 2 2 3 1 3 3 3 3 3 3 1          A2 2 4 2 3 1 3 1 2 1 3 1          A3 3 3 1 3 2 2 1 3 3 2 3          SU 7 9 6 7 6 8 5 8 7 8 5              M M M M M M M M M M M   3. Ite A1 2 2 3 1 3 3 3 3 3 3 1         A2 2 3 3 3 1 3 1 2 1 3 1         A3 3 3 1 3 2 2 1 3 3 2 3         SU 7 8 7 7 6 8 5 8 7 8 5              M M M M M M M M M M M  4. Ite  A1 2 2 3 1 3 3 3 3 3 3 1         A2 2 3 3 3 1 3 1 2 1 3 1         A3 3 2 2 3 2 2 1 3 3 2 3         SU 7 7 8 7 6 8 5 8 7 8 5              M M M M M M M M M M M  5. Ite  A1 2 2 2 2 3 3 3 3 3 3 1         A2 2 3 3 3 1 3 1 2 1 3 1         A3 3 2 2 3 2 2 1 3 3 2 3         SU 7 7 7 8 6 8 5 8 7 8 5              M M M M M M M M M M M  6. Ite  A1 2 2 2 2 3 3 3 3 3 3 1         A2 2 3 3 2 2 3 1 2 1 3 1         A3 3 2 2 3 2 2 1 3 3 2 3         SU 7 7 7 7 7 8 5 8 7 8 5              M M M M M M M M M M M  7. Ite  A1 2 2 2 2 3 2 4 3 3 3 1         A2 2 3 3 2 2 3 1 2 1 3 1         A3 3 2 2 3 2 2 1 3 3 2 3         SU 7 7 7 7 7 7 6 8 7 8 5              M M M M M M M M M M M  8. Ite  A1 2 2 2 2 3 2 4 3 3 3 1         A2 2 3 3 2 2 3 2 1 1 3 1         A3 3 2 2 3 2 2 1 3 3 2 3         SU 7 7 7 7 7 7 7 7 7 8 5              M M M M M M M M M M M  Result  A1 2 2 2 2 3 2 4 3 3 2 2         A2 2 3 3 2 2 3 2 1 1 3 1         A3 3 2 2 3 2 2 1 3 3 2 3         SU 7 7 7 7 7 7 7 7 7 7 6  
  • 0
    The total man-hours (days actually) for activities can change but not too much but the monthly man days aligned to treshold value are what I am aiming for. I compared the sums of the examples and the sum of man days for each activity is the same for start example and result example but this is a coincidence I think.2012-01-12

3 Answers 3

1

Edit (13 Jan 2012):

Your example can be solved in smaller number of iterations. I will try to code you an algorithm. But, for the time being consider the following where I reach the same solution as your example in 4 iterations:

  • We ignore the column where SU = T. For example, we don't touch M2, M4, M9 in this example.
  • We proceed from left to right (M1 to M11). Everything on the left will have SU = T

The basic functions are:

  • Find_Odd_Any() will find the first column where SU != T
  • Find_Odd_Greater_Than_T(Mx, T) will return the first column where SU > T
  • Find_Odd_Smaller_Than_T(Mx, T) will return the first column where SU < T
  • Exchange_One_ManDay(Mx, My) will take one man-day from the highest row in Mx and put it in the lowest row in My
 Threshold (T) = 7             M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 Start   A1 3  1  3  1  3  3  3  3  3  3   1         A2 3  3  2  3  1  3  1  2  1  3   1         A3 3  3  1  3  2  2  1  3  3  2   3         SU 9  7  6  7  6  8  5  8  7  8   5 

Iteration 1:

1. Find the first odd column where SU != T.

    Find_Odd_Any():          - Will return M1=9  2. M1 = 9. So we have to reduce and donate 2 man-days into some other column(s) where SU < T. So, now we find the next odd column where SU < T.      for (i = 0; i < absolute(M1[SU] - T); i++): // this loop runs twice     {         Find_Odd_Smaller_Than_T(M2, 7):             * This function will start checking from column M2 and return             the column for which SU < T=7             * Starting from M2 because it is next to M1 and we are             operating on M1             * Will return M3=6 (at loop i=0), M5=6 (at loop i=1)          Exchange_One_ManDay(M1, M3): // at loop i = 0             * This function will take 1 from M1 (from max row A1) and put             it inside M3 (to min row A2) at loop i=0                     Exchange_One_ManDay(M1, M5): // at loop i = 1               * This function will take 1 from M1 (from max row A2) and put             it inside M5 (to min row A2) at loop i=1     }      * By the end of the loop, the distribution will look like the     following:                 M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11     Start   A1 2  1  3  1  3  3  3  3  3  3   1             A2 2  3  2  3  2  3  1  2  1  3   1             A3 3  3  2  3  2  2  1  3  3  2   3             SU 7  7  7  7  7  8  5  8  7  8   5     

Iteration 2:


1. Find the first odd column where SU != T.

    Find_Odd_Any():          * Will return M6=8  2. M6 = 8. So, we have to reduce and donate 1 man-day from M6 into some other column(s) where SU < T. So, now we find the next odd column where SU < T.       for (i = 0; i < absolute(M6[SU] - T); i++): // this loop runs once     {         Find_Odd_Smaller_Than_T(M7, 7):             * This function will start checking from column M7 and return             the column for which SU < T=7             * Starting from M7 because it is next to M6 and we are             operating on M6             * Will return M7=5 (loop i=0)          Exchange_One_ManDay(M6, M7):             * This function will take 1 from M6 (from max row A1) and put             it inside M7 (to min row A2) at loop i=0     }      * By the end of the loop, the distribution will look like the     following:                 M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11     Start   A1 2  1  3  1  3  2  3  3  3  3   1             A2 2  3  2  3  2  3  2  2  1  3   1             A3 3  3  2  3  2  2  1  3  3  2   3             SU 7  7  7  7  7  7  6  8  7  8   5              

Iteration 3:

1. Find the first odd column where SU != T.

    Find_Odd_Any():          * Will return M7=6  2. M7 = 6. So, we have to increase and borrow 1 man-day from some other column(s) where SU > T. So, now we find the next odd column where SU > T.      for (i = 0; i < absolute(M6[SU] - T); i++): // this loop runs once     {         Find_Odd_Greater_Than_T(M8, 7):             * This function will start checking from column M8 and return             the column for which SU > T=7             * Starting from M8 because it is next to M7 and we are             operating on M7             * Will return M8=8 (loop i=0)          Exchange_One_ManDay(M8, M7):             * This function will take 1 from M8 (from max row A1) and put             it inside M7 (to min row A3) at loop i=0     }      * By the end of the loop, the distribution will look like the     following:                 M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11     Start   A1 2  1  3  1  3  2  3  2  3  3   1             A2 2  3  2  3  2  3  2  2  1  3   1             A3 3  3  2  3  2  2  2  3  3  2   3             SU 7  7  7  7  7  7  7  7  7  8   5         

Iteration 4:

1. Find the first odd column where SU != T.

    Find_Odd_Any():         - Will return M10=8  2. M10 = 8. So, we have to reduce and donate 1 man-day into some other column(s) where SU < T. So, now we find the next odd column where SU < T.      for (i = 0; i < absolute(M10[SU] - T); i++): // this loop runs once     {         Find_Odd_Smaller_Than_T(M11, 7):             * This function will start checking from column M11 and return             the column for which SU > T=7             * Starting from M11 because it is next to M10 and we are             operating on M10             * Will return M11=5 (loop i=0)          Exchange_One_ManDay(M10, M11):             * This function will take 1 from M10 (from max row A1) and put             it inside M11 (to min row A1) at loop i=0     }      - By the end of the loop, the distribution will look like the     following:                 M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11     Start   A1 2  1  3  1  3  2  3  2  3  2   2             A2 2  3  2  3  2  3  2  2  1  3   1             A3 3  3  2  3  2  2  2  3  3  2   3             SU 7  7  7  7  7  7  7  7  7  7   6            

Python code that Implements above:

#!/usr/bin/env python # -*- coding: utf-8 -*-  def find_odd_any():     su = 0     i = 0      for m in x:         for a in m:             su = su + a          if su != t:             return i         else:             su = 0             i = i + 1      return None   def find_odd_greater(k):     su = 0     i = k      for m in x[k:]:         for a in m:             su = su + a          if su > t:             return i         else:             su = 0             i = i + 1      return None   def find_odd_smaller(k):     su = 0     i = k      for m in x[k:]:         for a in m:             su = su + a          if su < t:             return i         else:             su = 0             i = i + 1      return None  def exchange_one_manday(src_i, dst_i):     src_m = x[src_i]     dst_m = x[dst_i]      # Reduce 1 man-day from source     src_m[src_m.index(max(src_m))] = src_m[src_m.index(max(src_m))] - 1      # Increase 1 man-day in destination     dst_m[dst_m.index(min(dst_m))] = dst_m[dst_m.index(min(dst_m))] + 1   def print_x():     print "[",     for m in x:         su = 0         for a in m:             su = su + a         print su, m, "|",      print "] \n"   t = 7 # threshold x = [     [3,3,3], # 9     [1,3,3], # 7     [3,2,1], # 6     [1,3,3], # 7     [3,1,2], # 6     [3,3,2], # 8     [3,1,1], # 5     [3,2,3], # 8     [3,1,3], # 7     [3,3,2], # 8     [1,1,3]  # 5 ]  print "start =>", print_x()  su = 0 i = 0 c = 0  while find_odd_any() is not None and (i+2) < len(x):      i = find_odd_any()     m = x[i]      for a in m: # find SU for the current M         su = su + a      if su != t:         d = abs(su - t) # absolute displacement from T          for j in range(0, d):             if su > t: # current M's SU is greater than T                 odd = find_odd_smaller(i+1)                 if odd is not None:                     print "gotta exchange=", i,x[i], "with", odd,x[odd]                     exchange_one_manday(i, odd)              if su < t: # current M's SU is smaller than T                 odd = find_odd_greater(i+1)                 if odd is not None:                     print "gotta exchange=", i,x[i], "with", odd,x[odd]                     exchange_one_manday(odd, i)       su = 0     c  = c + 1      print "round", c,"=>",     print_x()     #raw_input() 

If you run the code above with python file.py, the output should be:

 start => [ 9 [3, 3, 3] | 7 [1, 3, 3] | 6 [3, 2, 1] | 7 [1, 3, 3] | 6 [3, 1, 2] | 8 [3, 3, 2] | 5 [3, 1, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]   gotta exchange= 0 [3, 3, 3] with 2 [3, 2, 1] gotta exchange= 0 [2, 3, 3] with 4 [3, 1, 2] round 1 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 8 [3, 3, 2] | 5 [3, 1, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]   gotta exchange= 5 [3, 3, 2] with 6 [3, 1, 1] round 2 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 6 [3, 2, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]   gotta exchange= 6 [3, 2, 1] with 7 [3, 2, 3] round 3 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 7 [3, 2, 2] | 7 [2, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]   gotta exchange= 9 [3, 3, 2] with 10 [1, 1, 3] round 4 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 7 [3, 2, 2] | 7 [2, 2, 3] | 7 [3, 1, 3] | 7 [2, 3, 2] | 6 [2, 1, 3] | ] 
  • 0
    Very elega$n$t coded by the way. Thanks again.2012-01-13
0

That's a cute problem. I surmise there are more restrictions to it like every activity should not fall far behind the schedule, etc.

I would try the primitive greedy algorithm first. Below I assume that all you care about is that each activity is done more or less on schedule but you don't mind any distribution within one particular day (that is true if all your men can do all jobs and your initial schedule is just the schedule of customer requests you accepted, say).

Start with computing the current schedule for each activity so that $B_j(n)$ is the total number of man hours spent by the month $n$ inclusive on the activity $j$ in the non-spread schedule. The spread schedule will be constructed from left to right. Put $A_j(0)=0$. Let $n$ be the current month to process. Look at $S(n)=\sum_j a_j(n)$ where $a_j(n)$ is the number of hours initially planned for the activity $j$ in the month $n$. If $S(n)=S$, do nothing. If $S(n)>S$, move some hours forward (say, one by one). The order of moving is that you look at $A_j(n-1)+a_j(n)-B_j(n)$ and take the index $j$ corresponding to the largest of those numbers (least backlog). Then, if $a_j(n)>0$ decrease $a_j(n)$ by $1$ and increase $a_j(n+1)$ by $1$. Else, use the second least backlog index, etc. Then recalculate the backlogs and choose the least backlog index again and so on until you get $S(n)=S$. If $S(n), you should start bringing hours from the next columns in a similar manner except now, the largest backlog has prority and when you exhaust the position in the next column, you can use the next after the next, etc. Do it until you reach $S$. After you finish with scheduling column $n$, put $A_j(n)=A_j(n-1)+a_j(n)$ and repeat for the next month.

I have no idea how to encode that in Excel but if you want, I can write a code for you in some decent programming language. Just a bit later :).

OK, I wrote in Asymptote. It is pretty close to C but I had trouble with the C compiler on the computer I used. That hasn't been optimized in any way and the hours are moved one by one, which may be a bit slow if they are many. However, it seems to work. Play with it and tell me what you think :)

int [][]a; // work hours for each month and activity int []A,B; //backlog data. int M=15,N=7; //15 months, 7 activities int K=7; //parameter for random initialization  int S=30; // the monthly total  //initializing the schedule randomly  //(you'll have to fill it with some real data to see if it works for you)  for(int j=0;jS) //overworking scenario { jj=-1; //impossible index u=10*M*S; //some huge stupid number exceeding all the accepted workload for the year //if the accepted work is greater, you cannot make even 10% of it  for(int k=0;k0)) {u=B[k];jj=k;} //finding the minimal backlog you can shift } --a[jj][n];++a[jj][n+1]; //moving one unit forward ++B[jj]; --SS; //increasing the backlog and decreasing the load }   jj=1;  while ((SS-1)) //underworking scenario that is fixable { jj=-1; //impossible index u=-M*S; //some huge stupid number exceeding all you can do in a year  int v,vv;  for(int k=0;k0) flag=true; --vv; //finding the first non-zero place to take a unit from if((B[k]>u)&&flag) {u=B[k];jj=k;v=vv;} //finding the maximal backlog you can diminish } if(jj>-1) { ++a[jj][n];--a[jj][v]; //moving one unit forward --B[jj]; ++SS; //decreasing the backlog and increasing the load } }  for(int j=0;j
  • 0
    I will try this.2012-01-13
0

Your problem is underconstrained. From what you have said, a solution could just be something like

           M M M M M M M M M M M Result  A1 7 0 0 7 0 0 7 0 0 7 0         A2 0 7 0 0 7 0 0 7 0 0 7         A3 0 0 7 0 0 7 0 0 7 0 0         SU 7 7 7 7 7 7 7 7 7 7 7 

or

           M M M M M M M M M M M Result  A1 2 2 2 2 2 2 2 2 2 2 2         A2 2 2 2 2 2 2 2 2 2 2 2         A3 3 3 3 3 3 3 3 3 3 3 3         SU 7 7 7 7 7 7 7 7 7 7 7 

Once you explain whether these are not acceptable solutions, and why, we can begin formalizing the problem so it is less underconstrained.

  • 0
    The priority lies on the man days not the activities. You want to use all man days.2012-01-13