3
$\begingroup$

I have a scheduling problem but rather than having a fixed duration of each task, we have another "concept" that verifies the following property. Let's say task A requires a default 200 hours, then :

i) It could be done in 400 hours if it's done by an employee whose efficiency is 0.5

ii) It could be done in 100 hours if it's done by two employees both with full efficiency (i.e with an efficiency equal to 1)

There will be some constraints like: each hour of the processing of the task, the working hours of employees could not exceed a threshold. For example if a task "default duration" is 200 hours, I cannot affect more than 16 working hours each hour which may correspond to 16 regular employees each hour.

How do we call this problem? Are there any papers that deal with it?

$\endgroup$
4
  • $\begingroup$ If the efficiency differs per task, depending on properties of the task - for example if the employee has worked with the task's client before - it's normally referred to as affinity (see an example in this video). Affinity is often confused with skill requirements, but they're different because skill affects feasibility (hard constraint) and affinity affects productivity (soft constraint). $\endgroup$ Sep 10, 2020 at 12:13
  • $\begingroup$ Is it possible to treat tasks which duration depends on the number of employees assigned to it using Optaplanner? $\endgroup$
    – Antarctica
    Sep 28, 2020 at 14:31
  • $\begingroup$ Yes, but there is some complexity there: do the employees need to work at the same time on that task? Some jobs require at least 2 persons to be able to execute, feasible wise. Either way, the simplest approach, model wise, would be to divide the tasks into multiple smaller tasks - which brings the tuning challenge as to how many smaller tasks... $\endgroup$ Sep 29, 2020 at 9:04
  • $\begingroup$ "Some tasks require more than one person to execute. In such cases, both employees need to be there at the same time, before the work can start." Yes but what if I tell you there is minimum 2 employees but the solver can assign 3 or 4 to make the duration shorter ? (the number of employees work in parallel on the same task). The input is not a quantity measured in "seconds or hours" but in "man-hour". $\endgroup$
    – Antarctica
    Sep 29, 2020 at 11:20

2 Answers 2

3
$\begingroup$

The setting where processing times are variables dependent on the allocated resources, rather than constants, is usually called scheduling with controllable processing times. A very good survey of this problem is:

Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155(13), 1643-1666.

that is available at:

https://www.sciencedirect.com/science/article/pii/S0166218X0700025X

$\endgroup$
1
$\begingroup$

As you mentioned, the problem is, allocating the adequate resources to each task to complete based on the resources efficiency, it sounds like a resource-constrained project schedule and one of its useful variants called mixed-model assembly line balancing. If you are interested to use an MP, you can find a dozen papers by googling if not, some useful heuristic methods can be applied. Some helpful references are:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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