Problem Statement

This is a multi knapsack problem. We have to execute a number of tasks on a fixed number of hosts. Duration of each task and the number hosts on which we want to distribute the tasks is fixed (in this case it is let’s say 3). Individual tasks can not be broken into smaller pieces. We need to distribute tasks into these “3” hosts. The aim is to distribute the tasks in such a way that total time to complete all tasks will be minimum.

One of the Solutions can be

Hence total time taken is 9.

Solution

This problem can be solved by Dynamic Programming but let us try solving it using linear programming.

Linear Programming Solution

I have used Pulp https://coin-or.github.io/pulp/ to solve the problem using python. Here is the link to my full code.

First come up with Linear Programming Equations as shown below.

Ideal expected time for all tasks to be executed on each host is (total_time_to_execute_tasks_sequential/number_of_hosts). The number_of_hosts is 3 in our case.

Objective

Aim is to minimize the time tasks took to run on each host minus the ideal time. Objective is to keep running time on each host close to ideal average time.

(Variables starting with “if_” are of type boolean. They can take value of either 0 or 1)

When I run this code, I get this output:

Conclusion

This problem can be solved by Dynamic Programming but using Linear Programming we can solve problems where even if one or more constraints are not fitting it will try to fit the rest of the constraints.

--

--