0
$\begingroup$

Say we have a finite number of activities $\{A_i\}_{i=1}^n$ that each take $\{d_i\}_{i=1}^n$ units of time to complete with $d_i>0$ for all $i$. Some activities are dependent on others, ex. $A_5$ cannot be started until $A_1$ and $A_4$ are finished etc. Then from basic results in project scheduling we can calculate the minimum amount of time needed to complete the project if an arbitrary number of activities can be in progress concurrently (while respecting dependencies). We can also calculate the early time and a late time for each activity, which is the earliest and latest an activity can be started without delaying the whole project.

If we have an unlimited supply of workers (each of which can work on at most one activity at a time, must complete an activity from start to finish and has the skills to work on any activity) but we want to minimise the number of workers we use, is there an algorithm that is known to solve this problem? I'm not that familiar with project scheduling, operations research, computer science in general, or wherever I should be looking to answer this question.

I have a greedy algorithm that attempts this, and I attempted to prove that it found an optimal solution, but in writing the proof I lost faith that it was guaranteed to find the optimal solution. I can share this attempted proof if required but I'm not convinced it's relevant. The algorithm is as follows.

  1. Choose the unassigned activity that has the earliest late time. Assign this to the worker that is free earliest. Assign this activity to be started as early as possible while respecting both dependencies and the late time of the activity. If this is not possible, introduce another worker and assign this activity to the new worker, again starting as early as possible while respecting dependencies and late time.
  2. Repeat step 1 until all activities have been assigned.

This algorithm makes sense to me in that it makes intuitive decisions at each step. However I'm not convinced that it is best because of the following scenario. Say we're a couple of steps into the algorithm, with two workers so far. Worker 1 is free after time 12, worker 2 after time 10. Activity $A_3$ has early/late time 10/12, and duration 5. Activity $A_4$ has early/late time 10/14, and duration 7. My algorithm assigns $A_3$ to worker 2, then $A_4$ to worker 1, as early as possible. Then my workers are busy until times 19 and 15. If I assigned activities $A_3$ and $A_4$ in reverse then they would both be busy until times 17, which could be better in the long run. This is a sketchy example because I think if you try and make it with valid dependencies it's impossible to make it fit exactly but it gives me the feeling a proper counter-example might exist.

For what it's worth, I've looked online for optimal algorithms, but while the sources I find talk about versions of these problems being NP-hard [1], they're looking at much more complicated versions of project scheduling problems as I am. Namely I have no limits on resources, and am instead trying to minimise over the number of workers required.

As a second problem, I have a very similar algorithm in the case of a fixed number of workers where we are trying to complete the project as quickly as possible. Any pointers on literature in that direction would also be appreciated.

[1] https://www.researchgate.net/publication/308570442_Optimization_Algorithms_in_Project_Scheduling

$\endgroup$

1 Answer 1

2
$\begingroup$

Clearly the minimum number of workers is less than or equal to $n$, because having $n$ workers lets you assign the $i$th worker to the $i$th task and that's a perfectly valid solution.

So then the problem is roughly equivalent to asking "for each $k \lt n$, is there an assignment of tasks to $k$ workers that meets the constraints?", which is in general going to be NP-hard - it's functionally a job-shop scheduling problem.

$\endgroup$
1
  • $\begingroup$ That wiki page was exactly what I was looking, thank you so much. $\endgroup$ Jul 26, 2021 at 10:33

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.