Algorithmus zum Planen von Aufgaben in TypeScript. Die Graphentheorie hat sich endlich als nützlich erwiesen

In diesem Artikel möchte ich über einen Algorithmus sprechen, der bei der Beantwortung der uralten Frage aller Projekte hilft:

Wann wird das Projekt abgeschlossen sein?

Formal klingt das Problem folgendermaßen: "Das Projekt besteht aus Aufgaben, die voneinander abhängen können und möglicherweise auch dieselben Ausführenden haben. Wann kann das Projekt abgeschlossen werden?"

Ein kleiner Hintergrund

Vorläufige Nachforschung

, , - . , 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. Die Verwendung eines Tages als kleinste Zeitscheibe eignet sich gut für meine Aufgaben. Für einige ist es jedoch möglicherweise wichtig, die Stundenplanung zu verwenden.

Fazit

Sie finden den Code mit Tests auf meinem GitHub . Kann als NPM-Paket heruntergeladen werden . Aus irgendeinem Grund hat ein bestimmter Dustin es in Rust umgeschrieben :)

Ich frage mich, ob der vorgeschlagene Algorithmus Fehler enthält. Gerne diskutiere ich dies hier oder im Themenbereich auf GitHub mit Ihnen .