Task Scheduling Optimization with dependency and worker constraint

Question

We are confronted with a Task scheduling Problem

Specs

• We have N workers available, and a list of tasks to do.
• Each task-->Ti needs Di (i.e. worker*days) to finish (Demand), and can only hold no more than Ci workers to work on it simultaneously (Capacity).
• And some tasks can only start after other task(s) are done (Dependency).
• The target is to achieve total minimal duration by allocating workers to those sequences.

Example

• Number of workers: 10
• Taks List: [A, B, C]
• Demand: [100 50 10] - unit: workerday （Task A need 100 workerday to finish, B needs 50 workerday, and C need 10 workerday）
• Capacity: [10 10 2] - unit: worker (Task A can only 10 workers to work on it at the same time, B can only hold 10, and C can only hold 2)
• Dependency: {A: null, B: null, C: B} - A and B can start at any time, C can only start after B is done

Possible approaches to the example problem:

• First assign B 10 workers, and it will take 50/10 = 5 days to finish. Then at day 5, we assign 2 workers to C, and 8 workers to A, it will take max(10/2 = 5, 100/8 = 12.5) = 12.5 days to finish. Then the total duration is 5 + 12.5 = 17.5 days.

• First assign A 10 workers, and it takes 100/10 = 10 days to finish. Then at day 10, we assign 10 workers to B, which takes 50/10 = 5 days to finish. Then at day 15, we assign 2 workers to C, which takes 10/2 = 5 days to finish. The total duration is 10+5+5 = 20 days.

So the first practice is better, since 17.5 < 20. But there are still many more possible allocation practices to the example problem, and we are not even sure about what is the best practice to get the minimal total duration for it.

What we want is an algorithm:

• Input: Nworker, Demand, Capacity, Dependency

• output: worker allocation practice with the minimal total duration.

Possible Allocation Strategies we've considered when allocating for the tasks without dependency:

• First finish the tasks dependent by others as soon as possible (say, finish B as soon as possible in the example)
• Allocate workers to tasks with maximam demand (say, first allocate all workers to A in the example)

But none of the two proves to be the optimal strategy.

Any idea or suggestion would be appreciated. Thanks !

Answer 1

This sounds like Job Shop Scheduling with dependencies, which is NP-complete (or NP-hard). So scaling out and delivering an optimal solution in reasonable time is probably impossible.

I've got good results on similar cases (Task assigning and Dependend Job Scheduling) by doing first a Construction Heuristic (pretty much one of those 2 allocation strategies you got there) and then doing a Local Search (usually Late Acceptance or Tabu Search) to get to near optimal results.