Question

14. Extra credit problem You are a project manager, and your company is hired to do n different jobs. Jobs have durations t t in hours), can be done independently and all have the same deadline in 10 working days. Each job cannot be split between 2 or more people. You need to hire people to do the jobs; every hired person can work 8 hours per day. In order to save money your company wants to hire as few people as possible, but just enough to complete all jobs. You have been given a task to hire people and assign jobs to them. Represent this problem as an algorithmic problem. What is this algorithmic problem? Is it possible to solve it in a polynomial time? What algorithms for this problem do you know?

Answer 1

The task is to find minimum number m such that assigning n jobs among m person such that sum of duration of jobs assign to each person should not exceed 80 hours because we have 10 days deadline and each person can work for 8 hours.

So the algorithmic problem is to partition the set S of n jobs duration, into m disjoint subsets such that sum of elements in each subset should not exceed value 80 and union of these subsets should be equal to set S, also the number of subsets m should be minimized.

So this problem can be break down into decision problem which checks whether set S of n jobs can be partitioned into m disjoint subsets such that sum of elements in each subsets is at most 80. This problem belongs to class of integer linear programming and there is no polynomial time algorithm to solve this problem.

For this type of problem, if we want exact solution then we can use brute force approach, where for a particular value of m, we will check for all possible way of partitioning n tasks into m subsets and see if they can meet the requirement. Then we try to minimize m. But this approach will take exponential time.

Please comment for any clarification.