Algorithm for scheduling tasks in TypeScript. Graph theory finally came in handy

In this article, I want to talk about an algorithm that helps answer the age-old question of all projects:

When will the project be completed?

More formally, the problem sounds like this: "The project consists of tasks that may depend on each other, and may also have the same executors. When can the project be completed?"

A little background

Preliminary research

, , - . , 100%.

, .

, PERT, .

open-source : Bryntum Chronograph. , , ! . , , , . , .

, .

, : , — , . - , .

:

, :

:

• . . — . 2 , 6 9 . , 7 , .. 7 8 — .
• . , , , .
• . . , . , 4 , 75%, 1 .

Typescript :

export type Task = {
  id: ID;   // ID — alias for string
  title: string;
  start: Date;
  end: Date;
  duration: number;
  position: number;  // 
  progress: number;
  resourceId: ID;
  dependencies?: ID[];
};

:

1. , .
2. , , , . , .

:

1) . .

/**
* Graph respects explicit dependencies
 * and implicit by resources (via positions)
 */
export const makeGraphFromTasks = (tasks: Task[]): Graph => {
  const graph: Graph = new Map();
  const resources = new Map<ID, Task[]>();

  // add edges for deps by resourceId and explicit dependencies
  for (const t of tasks) {
    const tasksForResource = resources.get(t.resourceId) ?? [];
    tasksForResource.push(t);
    resources.set(t.resourceId, tasksForResource);

    graph.set(t.id, new Set(t.dependencies ?? []));
  }

  for (const tasksForResource of resources.values()) {
    // sort by position
    tasksForResource.sort((a, b) => a.position - b.position);

    // add to graph such edges so first node has second as dependency
    let prevTask: Task | undefined;
    for (const task of tasksForResource) {
      if (prevTask) {
        graph.get(prevTask.id)?.add(task.id);
      }
      prevTask = task;
    }
  }

  return graph;
};

2) () . ( ), ( ) ( ).

. - .

export const makeReverseGraph = (graph: Graph): Graph => {
  const reverseGraph: Graph = new Map();

  for (const [id, parentId] of dfs(graph, { withParentId: true })) {
    const prerequesitions = reverseGraph.get(id) ?? new Set();
    if (parentId) {
      prerequesitions.add(parentId);
    }
    reverseGraph.set(id, prerequesitions);
  }

  return reverseGraph;
};

/**
 * Iterate over every node.
 * If withParentId = true, than it is possible to visit same not more then once
 * @yields {[string, string?]} [nodeId, parentNodeId?]
 */
export function* dfs(
  graph: Graph,
  options: { withParentId: boolean } = { withParentId: false }
): Generator<readonly [string, string?], void, void> {
  const visited = new Set<ID>();

  // DFS interative
  // iterate over all nodes in case of disconnected graph
  for (const node of graph.keys()) {
    if (visited.has(node)) {
      continue;
    }

    const stack: ID[] = [node];
    while (stack.length > 0) {
      const currentNode = stack.pop();
      assertIsDefined(currentNode);

      yield [currentNode];

      visited.add(currentNode);

      const dependencies = graph.get(currentNode);
      if (!dependencies) {
        continue;
      }
      for (const dependencyId of dependencies) {
        if (options.withParentId) {
          // possible to yield same nodeId multiple times (needed for making reverse graph)
          yield [dependencyId, currentNode];
        }

        if (visited.has(dependencyId)) {
          continue;
        }

        stack.push(dependencyId);
      }
    }
  }
}

export const makeReverseGraph = (graph: Graph): Graph => {
  const reverseGraph: Graph = new Map();

  for (const [id, parentId] of dfs(graph, { withParentId: true })) {
    const prerequisites = reverseGraph.get(id) ?? new Set();
    if (parentId) {
      prerequisites.add(parentId);
    }
    reverseGraph.set(id, prerequisites);
  }

  return reverseGraph;
};

/**
 * Iterate over every node.
 * If withParentId = true, than it is possible to visit same not more then once
 * @yields {[string, string?]} [nodeId, parentNodeId?]
 */
export function* dfs(
  graph: Graph,
  options: { withParentId: boolean } = { withParentId: false }
): Generator<readonly [string, string?], void, void> {
  const visited = new Set<ID>();

  // DFS interative
  // iterate over all nodes in case of disconnected graph
  for (const node of graph.keys()) {
    if (visited.has(node)) {
      continue;
    }

    const stack: ID[] = [node];
    while (stack.length > 0) {
      const currentNode = stack.pop();
      assertIsDefined(currentNode);

      yield [currentNode];

      visited.add(currentNode);

      const dependencies = graph.get(currentNode);
      if (!dependencies) {
        continue;
      }
      for (const dependencyId of dependencies) {
        if (options.withParentId) {
          // possible to yield same nodeId multiple times (needed for making reverse graph)
          yield [dependencyId, currentNode];
        }

        if (visited.has(dependencyId)) {
          continue;
        }

        stack.push(dependencyId);
      }
    }
  }
}

3) () . .

— ( , ) — ( ), .

.

, . .

-. : , .

export const scheduleTasks = (tasks: Task[], today?: Date) => {
  const graph = makeGraphFromTasks(tasks);
  const tasksById = tasks.reduce((map, task) => {
    map[task.id] = task;
    return map;
  }, {} as { [id: string]: Task });

  // @TODO: 0. Detect cycles, if present throw error

  // 1. Make reverse graph, to detect sinks and sources
  const reverseGraph = makeReverseGraph(graph);

  // 2. If node is source, t.start = max(today, t.start)
  // Repeat until dates remains unchanged, max graph.size times.
  // Similar to optimization in Bellman-Ford algorithm
  // @see https://en.wikipedia.org/wiki/Bellman–Ford_algorithm#Improvements
  for (let i = 0; i <= graph.size; i++) {
    let datesChanged = false;

    for (const [id] of dfs(graph)) {
      const t = tasksById[id];

      const isSource = reverseGraph.get(id)?.size === 0;
      const isSink = graph.get(id)?.size === 0;
      const isDisconnected = isSource && isSink;

      if (isSource || isDisconnected) {
        datesChanged = updateStartDate(t, today ?? new Date());
      } else {
        const prerequesionsEndDates = Array.from(
          reverseGraph.get(id) ?? []
        ).map((id) => tasksById[id].end);
        datesChanged = updateStartDate(
          t,
          addBusinessDays(max(prerequesionsEndDates), 1)
        );
      }
    }

    if (datesChanged === false) {
      break;
    }
  }

  return tasks;
};

/**
 * Update task dates, according to startDate change
 * @returns false if date didn't change, true if it changed
 */
export const updateStartDate = (task: Task, startDate: Date) => {
  const correctedStartDate = shiftToFirstNextBusinessDay(startDate);
  const daysSpent = Math.floor(task.duration * task.progress);
  const newStartDate = subBusinessDays(correctedStartDate, daysSpent);

  if (isEqual(task.start, newStartDate)) {
    return false;
  }

  task.start = subBusinessDays(correctedStartDate, daysSpent);
  // -1 because every task is minimum 1 day long,
  // say it starts and ends on same date, so it has 1 day duration
  task.end = addBusinessDays(task.start, task.duration - 1);

  return true;
};

1. . , . , , . , , .)
2. , — . -, , . , .
3. . , updateStartDate.
4. Using one day as the smallest time slice works well for my tasks. But for some it might be important to use hourly scheduling.

Conclusion

You can find the code with tests on my GitHub . Can be downloaded as NPM package . For some reason, a certain Dustin rewrote it in Rust :)

I wonder if there are any bugs in the proposed algorithm. I will be happy to discuss this with you here or in the issues section on GitHub .