Algoritma untuk menjadwalkan tugas di TypeScript. Teori grafik akhirnya berguna

Pada artikel ini, saya ingin berbicara tentang algoritma yang membantu menjawab pertanyaan kuno dari semua proyek:

Kapan proyek akan selesai?

Secara lebih formal, masalahnya terdengar seperti ini: "Proyek terdiri dari tugas-tugas yang mungkin bergantung satu sama lain, dan mungkin juga memiliki pelaksana yang sama. Kapan proyek dapat diselesaikan?"

Sedikit latar belakang

, , - . , 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. . - .

GitHub. NPM-. - Rust :)

Saya ingin tahu apakah ada bug dalam algoritma yang diusulkan. Saya akan dengan senang hati mendiskusikan hal ini dengan Anda di sini atau di bagian masalah di GitHub .