甘特图中带依赖项的任务排序算法

Question

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

1. 父任务可以依赖于另一个父任务或子任务。
2. 子任务可以依赖于另一个子任务或父任务。
3. 任务可以具有多个依赖项。
4. 依赖任务只有在其统治任务完成后才能开始

​

​

如果将依赖项添加到父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))
   }
})

此方法的问题是，如果在start_date数组的末尾找到依赖项(即，子-c-1依赖于子-a-3)，则不会更新以前任务的任何dependencies s。

我觉得这里可能需要使用递归，但不太确定。希望这一切都有意义-任何帮助都是值得感激的。

Answer 1

据我所知，您正在开发一个自动规划逻辑，类似于dhtmlx甘特的付费版本中的自动调度。

FUI，我在销售这种产品的DHTMLX公司工作，所以我不能深入研究如何开发一个免费的替代方案：)但是我想我可以给你一些一般性的考虑。

1. 我强烈建议不要在自动规划中使用递归。我见过的这种方法的实现很难调试，需要不断的维护。根据我的经验，实现一个直观的算法，将工作与任何可能的甘特结构是相当困难的。
2. 可以肯定的是，在市场上不同的甘特引擎中使用的是将甘特的任务和链接视为有向图的方法：图表，其中任务是顶点，链接是图的边缘。

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

• 你可以检测到依赖项中的循环
• 您将能够以这样的方式排序元素，即只有在处理依赖的任务之后，才能处理依赖的任务- 拓扑排序。
• 在对数据集进行拓扑排序之后，可以将每个任务的开始日期迭代和计算为“predecessor.start_date+ predecessor.duration + task .滞后”，其中保证在前一次迭代中处理“前身”，而不需要任何递归。

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

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

如果你限制了你正在做的事情的范围，例如不允许项目之间的关系，你可以用一种更简单、更直观的方法来解决问题。但对于一个通用的解决方案，我认为我概述的方法是最安全的选择。

如果您正在实现类似于dhtmlxGantt ( scheduling.html )的自动调度，并且您计划在商业上使用它，那么可能值得获得dhtmlxGantt的付费版本，在这种版本中，自动调度是现成的。实现一个可靠的自动调度算法可能需要花费大量的时间和精力，因此获得一个现成的解决方案可能比从头开始开发它花费更少。