Task planning algorithm in TypeScript: real-life problem solved with graph theory
Tags: typescript, algorithms, taskplanning
Published: 2020-03-31 10:28:09


In this article, I’ll present the algorithm which helps to answer the main question of all project planning efforts:
> # When will it be done?

A more formal representation of this problem sounds like: “Having some tasks which might depend on each other and some folks which can do those tasks when a milestone can be reached?”

![Weekly sprint planning meeting in essence](https://cdn-images-1.medium.com/max/4404/1*KBgI05DqeNusAfdSVWQRUA.jpeg)*Weekly sprint planning meeting in essence*

## A Little Backstory

Since summer 2019 I work as a tech lead. Currently, I’m responsible for 3 different projects with a team of 7 developers, 2 managers, 2 designers, and several departments to cooperate with.

For task tracking, we’re using our internal tool [Yandex Tracker](https://yandex.ru/tracker/) which is mostly like Jira. But it has no tools that’ll help to find the answer for an eternal question: “When?”. That’s why from time to time we manually sync tasks with **Omniplan**. Turned out that it’s the tool that solves almost all project planning problems and moreover it has an **auto-planning feature** so all situations when one assignee has workload over 100% are resolved automatically.

Still, it has some drawbacks:

* Slow and unreliable project sync between team mates based on a local copy syncing

* MacOS only

* Quite hard to sync it with our issue tracker

* Pricey: $200 and $400 for Pro edition

So I’ve decided to try to make my own Omniplan version with blackjack and hookers that would be:

* Web-based

* Simple syncing with our tracker

* With real-time collaboration

The most exciting part was to make **a scheduling engine**. I didn’t understand why only Omniplan has such an essential feature. Now I do.

So this article is about scheduling.

## Developing a scheduling engine

First I’ve done some research. I’ve googled for solving scheduling tasks in general and found a lot of about [Gantt](https://en.wikipedia.org/wiki/Gantt_chart), [PERT](https://en.wikipedia.org/wiki/Program_evaluation_and_review_technique), but haven’t found any practical algorithms.

Then I looked for open-source libraries and found only one: [Bryntum Chronograph](https://github.com/bryntum/chronograph). It seems like something I was looking for all the time. They even have [benchmarks](https://github.com/bryntum/scheduler-performance). But, well, talking honestly I didn’t understand [any of its code](https://github.com/bryntum/chronograph/blob/master/src/chrono/Graph.ts) and almost complete lack of documentation didn’t help either. I thought maybe, what if I could write it from scratch with less code.

So, as usual, I’ve tried to draw the problem.

![Timeline of tasks before scheduling](https://cdn-images-1.medium.com/max/2452/1*kFofS0xLfilw8y7OQ1mCfg.png)*Timeline of tasks before scheduling*

While drawing it I’ve probably got the most important insight: tasks can be represented as a directed graph and edges are not only the explicit dependencies but also *implicit dependencies by the same assignee*.

The following algorithm should lead to such tasks arrangement:

![Timeline of tasks after scheduling](https://cdn-images-1.medium.com/max/2948/1*P6QZut58YL7YrighHWxChw.png)*Timeline of tasks after scheduling*

Let’s consider what a task is:

![Task anatomy](https://cdn-images-1.medium.com/max/2796/1*G9nxvpUvc09hFu4LpI0QQA.png)*Task anatomy*

There are some not so obvious properties of a task:

* **Duration**. The task is being done only during *business* days and the number of *business* days is an *estimation* of a task. So in this example the task starts on 2 March, has an estimation of 6 days, so it will end on 9 March (*not 7 March*), because 7 and 8 March are holidays.

* **Position**. In this model, we assume that tasks with lower positions (same as a higher priority) should be done earlier than a task with higher positions (or lower priority).

* **Progress**. It is a portion of a task that can be represented in percents but in fact, it is a number of days that were spent on a task. For example, if a task is estimated up to 4 days and, then progress is 75%, that 1 day left to task completion.

So TypeScript type is as follows (*ID is just an alias for string*):

{% gist https://gist.github.com/DimitryDushkin/508711318a99240b9b959e3c3fb5393c %}

## The algorithm

In essence, the algorithm should change start and end dates of the tasks in the following way:

1. Tasks should start today if it is possible

1. It should be impossible to start a task today if it has other tasks as prerequisites that are unfinished. In that case, a task should start right after the last prerequisite’s end date.

Pretty simple, huh? 🙈

The main steps of the algorithm are:

1. **Build a graph from tasks. **Make edges taking into account explicit dependencies and implicit dependencies by the same assignee.

{% gist https://gist.github.com/DimitryDushkin/2c50d784fd8529da072dacc083d6b9cc %}

**2. Make a *reverse graph*** to be able to detect sinks (node without outgoing edges), sources (node without ingoing edges) and disconnected nodes (nodes without edges at all). *A reverse graph *is the same as an original directed graph but with inverted edges.

To visit all nodes we need [depth-first search traversal](https://en.wikipedia.org/wiki/Depth-first_search), so I‘ve made a universal DFS helper function as well:

{% gist https://gist.github.com/DimitryDushkin/9270864096298d5e7116a91f8d5a3f29 %}

**3. Visit every node (task) and update a start and end dates.** Visiting should be performed starting from the task with higher priority

If a task is a source (it is not a prerequisite for any other task and task’s assignee has no other task to do before this task) or a task is disconnected node (it has no dependencies and it is not prerequisite for any other tasks) then we start task today.

Otherwise, a task has prerequisites and its start date should be set to the latest end date of its prerequisites tasks.

Also, it is important to correctly **update an end date while setting a start date of a task**. We should take into account actual business days and the progress of a task.

{% gist https://gist.github.com/DimitryDushkin/682f39be5c32a90449888a46ec499d43 %}

## What can be improved

1. **Circular dependency detection.** If cycles are present throw an error because that means that some task A has as prerequisite task B and task B has as prerequisite task A, which is a classic problem of [circular dependency](https://en.wikipedia.org/wiki/Circular_dependency) and the problem should be resolved manually. Tasks A and B do not necessarily have an explicit dependency on each other, there are might some other tasks between them. It is a well-known algorithm I think I’ll add it soon. For my current use case, it is not that important.

1. Probably the most important feature which leads to a more complex solution is introducing **a desirable start date** of a task. I didn’t research it yet, but if someday it will grow to a standalone web-service I think it should be done. Now, this feature can be mitigated by setting proper priorities of tasks.

1. For the enterprise-grade solution, it is important to take into account vacations and public holidays. I think **updateStartDate** function can be quite easily updated to support this functionality.

1. For my case having a **day** as a time quant was okay, but I believe for some people **hour**-based planning might be important. I think implementing an hour-based quant can also introduce some complications to code.

## Conclusion

The code from the article you can find [here](https://github.com/DimitryDushkin/project-tasks-scheduling-engine). You can grab and use it as an [NPM package](https://www.npmjs.com/package/project-tasks-scheduling-engine).

I’m wondering if a presented solution has some flaws. If you spotted some please contact me here or on [issues section in Github](https://github.com/DimitryDushkin/project-tasks-scheduling-engine/issues).