2 years ago
#45587
imc
Allocating resources optimally in a scheduling problem
I have a process that involves around 1000 tasks. Each task has a duration (the time it takes from when the process starts to when it is finished, in days), and a set of predecessor steps that must occur before the task can be started. The entire process originates from one task (this is the only task that does not have a predecessor). The table below gives an example of the data structure.
Task | Duration | Predecessors |
---|---|---|
Task 1 | 1d | |
Task 2 | 2d | Task 1 |
Task 3 | 1d | Task 2 |
Task 4 | 3d | Task 1, Task2 |
If we start at day 0, then Task 1 is done on that day, Task 2 starts on day 1 (0+1), Task 3 starts on day 3 (0+1+2), and Task 4 also starts on day 3.
I solved the problem of finding the correct order for the tasks by modelling the problem as a directed network with the tasks as the nodes. Edges are drawn from predecessors to their successors and the edge weight is given by the duration of the predecessor task.
The starting day for each task is then the longest path to the first task (critical path) and the duration for the entire process is from the first task to the finish day of the last task.
What I would like to do now is find those tasks that will bring the biggest reduction in the overall duration of the process if their duration were reduced. Let's say I have an investment that I make to the process (e.g. by hiring more workers) of 10 days. How do I distribute this investment optimally across the tasks in the process to bring the maximum reduction to the duration of the entire process?
algorithm
scheduled-tasks
networkx
graph-theory
0 Answers
Your Answer