I have job that needs to be done in 14 days. I have 5 workers. One day need exactly 3 workers. Each worker can only work maximum 9 days. Each worker has their day preference, each day for each worker has different cost.
Now, how do I solve this in mathematics term? How do I find the lowest cost possible for the worker assignment?
I don't think this is assignment problem since the Hungarian algorithm is designed so that I can only find 1-to-1 assignment. (In this case, 1 worker for 1 day)
What you need to solve this problem is an IP (Integer Programming) formulation. Your intuition is right, this is very similar to an assignment problem -- we are essentially assigning workers to work on certain days.
Here are the steps to formulate the problem:
Decision variable: (In English) Which worker works on which days?
Let's label the days t (1..14) And the workers w1 to w5.
So,
X_wt = 1 if worker w works on day t
X_wt = 0 otherwise
The constraints are now fairly straight forward to write down. Each day needs exactly 3 workers.
X_1t + X_2t + X_3t + X_4t + X_5t = 3 for each t (1..14)
Each worker can work for a maximum of 9 days:
(sum over t=1..14) X_wt <= 9 for each w (1..5)
And finally, the Objective function:
Let C_wt be the cost of hiring worker w on day t. With a double summation:
Min (sum over w 1..5)(sum over t 1..14) C_wt
And in order to accommodate worker preferences for days,
you can layer on yet another set of costs, say P_wt.
That's the basic formulation. You will then need an IP/LP solver (such as CPLEX or Excel Solver or R's optim library) to get the actual solution.
Hope that helps.
This can be solved as a minimum-cost network-flow problem on a bipartite graph. Each worker represents a source with a supply of 9 units, and each day represents a sink with demand of 3. The arcs between the supply and demand each have capacity 1, and a cost corresponding to their preference to be off on that day. If there is flow along an arc, that means that a particular worker should be working that day.
Although this can't be solved with a Hungarian method, but with several fast algorithms, including network simplex.
Algebraically, the formulation is
minimize sum_w sum_d p_wd x_wd
subject to
\sum_w x_wd = 3 forall d
\sum_d x_wd <= 5 forall w
if p_wd is worker w's preference for day d. This is a totally unimodular constraint matrix, so it does not require a mixed-integer solver.
It can be a bin-packing and tsp problem. Look for capacited vehicle routing problem. It shares many problems but you have exactly 3 workers. In capacited vehicle routing there is x workers. It think you need more information.
