CODEWITHSUNDEEP
mathematical-optimizationlinear-programming
user1491884
user1491884

Reputation: 649

Assignment allocation (linear programming) lookalike

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)

Upvotes: 3

Views: 1427

Answers (3)

David Nehme
David Nehme

Reputation: 21572

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.

Upvotes: 1

Ram Narasimhan
Ram Narasimhan

Reputation: 22496

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.

Upvotes: 1

Cybercartel
Cybercartel

Reputation: 12592

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.

Upvotes: 0

Related Questions