2
$\begingroup$

I want to know if there is any already defined problem that could give me a hint on how should I approach the following task.

There are N tasks that should be accomplished, each task requires different amount of time to complete. On the other hand we have X persons to take care of the tasks but their speed of execution may vary per task. One restriction here is that each person should be designated to a single task. The goal here is to meet the demand of the tasks but also total duration should be kept as low as possible.

An easy way to proceed is to set a weight on meet the demand and also reduce the time of execution.(e.g 0.7 for demand and 0.3 for duration). I need to get the optimal weights.

Example:

Demand: total number of tasks: 1000

3 different tasks with the following distribution of demand T1: 20%, T2: 40%, T3: 40%

How should I formulate the problem so as weights can get into the game?

$\endgroup$
  • $\begingroup$ Does $N=X$, or do you mean that each person should be designated to a single task at a time? $\endgroup$ – RobPratt Sep 24 at 15:01
  • $\begingroup$ Well the second statement, want to test the case that tasks outnumber people $\endgroup$ – Psyndrom Ventura Sep 24 at 18:01
  • $\begingroup$ @PsyndromVentura, For that the problem to be feasible, definitely, before assigning the tasks to each person you will need to ensure that you have enough persons to meet demands if, it is your main goal. Also, if you are interested to know the schedule of each person, took a look to resource-constrained project models. $\endgroup$ – A.Omidi Sep 24 at 20:17
6
$\begingroup$

If "total duration" means sum of durations, this is called the generalized assignment problem.

If "total duration" means maximum of durations, this is called the bottleneck generalized assignment problem. You might also find something useful by searching for makespan minimization.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.