甘特图中具有依赖关系的任务的排序算法

Question

我正在使用 dhtmlx-gantt 构建包含父任务和子任务的甘特图。

父任务可以依赖于另一个父任务或子任务
一个子任务可以依赖于另一个子任务或父任务
任务可以有多个依赖关系
依赖任务只有在其支配任务完成后才能开始

如果将父 A 下的任务添加到父 C 的依赖项，这会将班次的开始日期移动到父 C 中的所有任务，就像这样

这是我的数据结构

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))
   }
})

此方法的问题在于，如果在 dependencies 数组的末尾发现依赖项（即 child-c-1依赖 child-a-3)

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

Answer 1

据我了解，您正在开发一个自动计划逻辑，类似于 dhtmlx 甘特图付费版本中提供的 Auto Scheduling。

FUI，我在销售该产品的 DHTMLX 工作，所以我无法深入探讨如何开发免费替代品:) 但我想我可以给你一些一般性的考虑。

我强烈反对使用递归进行自动规划。我所见过的这种方法的实现很难调试并且需要不断维护。根据我的经验，实现一种适用于任何可能的甘特图结构的直观算法非常具有挑战性。
当您将甘特图的任务和链接视为有向图时，绝对有效的方法 - 并且在市场上可用的不同甘特图引擎中使用 - 是这样的方法： https://en.wikipedia.org/wiki/Directed_graph 其中任务是顶点，链接是图的边。

一旦您能够以图表的形式表示您的数据，其他一切就非常简单了：

你可以检测到loops in your dependencies
您将能够以这样的方式对元素进行排序，即您始终仅在处理依赖任务之后才处理依赖任务 - Topological Sorting
对数据集进行拓扑排序后，可以迭代并计算每个任务的开始日期为'predecessor.start_date + predecessor.duration + link.lag'，其中'predecessor'保证在之前的迭代之一中处理，而不需要任何递归。

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

一开始听起来可能很复杂，但代码会很容易理解和调试。

如果您限制了您正在做的事情的范围，例如禁止项目之间的关系，您可能会采用更简单、更直观的方法。但是对于 general-purpose 解决方案，我认为我概述的方法是最安全的选择。

P.S。如果您正在实施类似于 dhtmlxGantt ( https://docs.dhtmlx.com/gantt/desktop__auto_scheduling.html )，如果您打算将其用于商业用途，那么购买 dhtmlxGantt 的付费版本可能是值得的，其中 auto-scheduling 开箱即用。实施可靠的 auto-scheduling 算法可能需要花费大量时间和精力，因此获得现成的解决方案可能比从头开始开发更便宜。

甘特图中具有依赖关系的任务的排序算法

Sorting Algorithm for Tasks with Dependencies in a Gantt Chart

javascript

dhtml

gantt-chart