为gantt图表中具有依赖项的任务分类算法

Question

我正在用

1. 父任务可以取决于另一个父母或子任务，
2. 子任务可以取决于另一个孩子或父级任务
3. 可以具有多个依赖性任务，
4. 只有一旦完成任务完成

如果将依赖关系添加到父a下的任务中，则将偏移移动到父c中的所有任务，例如so

这是我的数据的结构如何

const tasks = [
    { id: 'parent-a', text: 'Parent A', duration: null },
    { id: 'child-a-1', text: 'Child 1', parent: 'Parent A', duration: 5 },
    { id: 'child-a-2', text: 'Child 2', parent: 'Parent A', duration: 5 },
    // ...
]

const dependencies = [
    { id: 1, source: 'child-a-1', target: 'child-a-2' },
    { id: 1, source: 'parent-b', target: 'parent-c' },
    // ...
]

计算开始的开始每个任务的日期，遍历每个任务，并根据任务的持续时间动态设置日期。

let startDate = new Date()
tasks.forEach((task, i, array) => {
   const correspondingDependency = dependencies.find(d => d.id === task.id)
   if (correspondingDependency) {
       array[i].start_date = new Date(startDate.setDate(startDate.getDate() + duration))
   }
})

此方法的问题是，如果找到了依赖关系，则不会更新任何 start_date 在依赖项的末尾数组（即Child-C-1取决于Child-A-3），

我觉得我可能需要在这里使用递归，但不确定。希望这一切都有意义 - 任何帮助都将受到赞赏

Answer 1

据我了解，您正在开发一种自动计划逻辑，类似于在DHTMLX gantt的付费版本中可以使用。

Fui，我在销售该产品的DHTMLX工作，所以我无法深入研究如何开发免费的替代方案:)
但是我想我可以给您一些一般的考虑。

1. 我强烈建议不要将递归用于汽车规划。我所见过的这种方法的实现很难进行调试，需要持续维护。根据我的经验，实施将与甘特（Gantt）任何可能结构一起使用的直观算法非常具有挑战性。
2. 当您将甘特特（Gantt）的任务和链接视为指示图时，肯定有效的方法 - 用于市场上可用的不同甘特引擎中：
   https://en.wikipedia.org/wiki/wiki/directed_graph_graph
   任务是顶点的地方，链接是图形的边缘。

一旦能够以图的形式表示数据，其他所有内容都非常简单：

• 您可以检测循环
• 您将能够以某种方式订购元素，以便您只有在处理任务之后才能处理依赖任务 - Topological Sorting
• after you order the dataset topologically, you can iterate and calculate the start date of each task as 'predecessor.start_date + predecessor.duration + link .lag'，其中保证在以前的迭代之一中处理“前身”，而无需任何递归。

具有挑战性的部分是将您的数据结构从Gantt的亲子层次结构转换为有向图的平坦结构。基本上，这意味着您想摆脱数据集中的项目，并转换涉及与其子任务之间关系的项目。

一开始听起来可能很复杂，但是代码将易于理解且易于调试。

如果您限制了所做的工作范围，例如不允许项目之间的关系，则可能会采用更简单，更直观的方法逃脱。但是对于通用解决方案，我认为我概述的方法是最安全的选择。

PS
如果您要实施与DHTMLXGANTT类似的自动调度（
https://docs.dhtmlx.com/gantt/desktop__auto_scheduling.html ) and if您计划在商业上使用它，可能值得获得付费版本的DHTMLXGANTT，其中可以在其中开箱即用。
实施可靠的自动安排算法可能需要大量时间和精力，因此，获得现成的解决方案可能比从头开始开发它便宜。