Algoritmo para programar tareas en TypeScript. La teoría de grafos finalmente fue útil

En este artículo, quiero hablar sobre un algoritmo que ayuda a responder la antigua pregunta de todos los proyectos:

¿Cuándo se completará el proyecto?

Más formalmente, el problema suena así: "El proyecto consta de tareas que pueden depender unas de otras y también pueden tener los mismos ejecutores. ¿Cuándo se puede completar el proyecto?"

Un poco de historia

Investigación preliminar

, , - . , 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. Usar un día como el intervalo de tiempo más pequeño funciona bien para mis tareas. Pero para algunos, puede ser importante utilizar la programación por horas.

Conclusión

Puedes encontrar el código con pruebas en mi GitHub . Puede descargarse como paquete NPM . Por alguna razón, un tal Dustin lo reescribió en Rust :)

Me pregunto si hay algún error en el algoritmo propuesto. Estaré encantado de discutir esto contigo aquí o en la sección de problemas en GitHub .