Dans cet article, je veux parler d'un algorithme qui permet de répondre à la question séculaire de tous les projets:
Quand le projet sera-t-il terminé?
Plus formellement, le problème ressemble à ceci: "Le projet se compose de tâches qui peuvent dépendre les unes des autres, et peuvent également avoir les mêmes exécuteurs. Quand le projet peut-il être achevé?"
Un peu de fond
. 3 11 , 2 , 2 . , , , 300 .
.. , , : "?". Omniplan, . , . — - , 100%.
, Omniplan :
- , .
- MacOS
- : $200 $400 Pro .
Omniplan c .:
- Real-time
— - . , Omniplan . .
, , - . , 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) . .
/**
* 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;
};
- . , . , , . , , .)
- , — . -, , . , .
- . , updateStartDate.
- . - .
Je me demande s'il y a des bugs dans l'algorithme proposé. Je serai heureux d'en discuter avec vous ici ou dans la section des problèmes sur GitHub .