Is there an algorithm for project scheduling that is known to be optimal, i.e. minimises #workers needed to complete the project in minimum time

algorithmscomputer scienceoperations research

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.

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.
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

Best Answer

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.

Related Solutions

[Math] Greedy Algorithm Proof

We have a set of jobs $J_i = (a_i, b_i)$ where all the $a_i,b_i \ge 0$. We want to find the permutation $\pi$ which minimises $$\max_j \left\{ b_{\pi(j)} + \sum_{k \le j}a_{\pi(k)} \right\}$$

Suppose we have proven that for all job sets $X$ of size no greater than $n$ the permutation which sorts the jobs by descending $b_i$ breaking ties by descending $a_i$ is an optimal solution (bearing in mind that there may be more than one optimal solution). (Call this ordering doubly-reverse-lexicographical because it sorts in descending order starting from the right).

Consider a job set $Y$ of size $n+1$ whose "worst" job is $J_{n+1}$, and suppose that there is no optimal solution in which this job comes first. Of the optimal solutions select one which puts $J_{n+1}$ as early as possible, in position $j^* = \pi^{-1}(n+1) > 0$. Now, which $j$ maximises the expression above (i.e. which job finishes last)?

Given that $b_{\pi(j^*)}$ is maximal by construction and the sum is non-decreasing the maximising $j$ must be $\ge j^*$. Also, if the maximising $j > j^*$ we can move $J_{n+1}$ to the start without affecting the optimality, so by contradiction that's impossible. We're forced to conclude that $J_{n+1}$ is the job which finishes last.

Now consider what happens if we swap it with the job before it. Call that job $J_p$ for previous. $J_p$'s finishing time increases from $b_p + \sum_{k < j^*}a_{\pi(k)}$ to $b_p + \sum_{k \le j^*}a_{\pi(k)} \le b_{n+1} + \sum_{k \le j^*}a_{\pi(k)}$ and $J_{n+1}$'s finishing time decreases from $b_{n+1} + \sum_{k \le j^*}a_{\pi(k)}$ to $b_{n+1} + \sum_{k \le j^* \wedge k \ne j^*-1}a_{\pi(k)}$ so we have a contradiction with this being an optimal solution which puts $J_{n+1}$ as early as possible.

We've now proven that there is an optimal solution for $Y$ in which $J_{n+1}$ comes first. Either some of these optimal solutions allow for the rest of the jobs to be ordered non-optimally because the worst job is so bad that it doesn't matter – in which case putting them in an optimal ordering will give an optimal ordering – or the rest of the jobs must be optimally ordered to get an optimal ordering. In either case we can apply our strong inductive presupposition to say that there is an optimal ordering which is doubly-reverse-lexicographical.

The base case of only one job is trivial.

[Math] Project scheduling using linear programming

Here's how I've tackled this part of a problem. Define a job as the following type of object (using electrical as an example):

{title: 'electrical', duration: 2, precedents: [3, 5]}

Then create the precedent constraints by looping through each job and precedent. (Pesudo code)

for j in jobs:
  for p in precedents:
     add_constraint(start_time_of_j >= start_time_of_p + duration_of_p)

Then create a start_time and an end_time variable, and setting them before and after all jobs. (This effectively makes start_time the minimum of all start_times and end_time the maximum of all start_times plus their respective durations.)

for j in jobs:
  add_constraint(start_time <= start_time_of_j)
  add_constraint(end_time >= start_time_of_j + duration_of_j)

Lastly, set your objective function to minimize total time.

set_objective(minimize, end_time - start_time)

I found it helped to add the following constraint too

add_constraint(start_time == 0)

Best Answer

Related Solutions

[Math] Greedy Algorithm Proof

[Math] Project scheduling using linear programming

Related Question