关于并行装配线调度的帮助/建议(动态规划)

Question

我正在处理的问题类似于动态programming.The的装配线调度问题，与传统的问题不同，我们现在有预定义的站点，现在我只有信息，哪些任务应该运行，哪些任务可能是多个任务。

我必须找出应该把哪一行放在哪一行上，这样才能最大限度地减少production.So所花费的总时间--显然，如果任务位于单行上，那么它们是以串行方式执行的，因此速度更慢。

所以我有以下问题

1. 如何创建基于时间的级别/行，因为我没有一个序列的所有任务？我只知道哪个任务出现在哪个(一个或多个)任务之前。基于时间的级别是必要的，因为我必须最小化时间(当任务并行执行时会发生这种情况)。
2. 如何确定任务的最优顺序，以使时间最小化？由于有几个任务在等待单个任务，所以我也必须尽量减少这一次。
3. 就像最初的问题一样，不同线路之间的沟通也要付出代价。我必须确定这个通信成本是否值得将任务转移到一个单独的行(从它的通信任务)。

tl;dr:装配线调度(动态规划)的并行版本，其中所有的生产线都可以同时繁忙，而我没有任何站号/订单。我只知道在哪项任务之前应该执行哪些任务。

我必须决定哪些任务应该放在同一条线上，哪些任务要放在不同的线路上(给定任务在不同线路上的通信时间)，以尽量减少生产时间。

Answer 1

如果你愿意接受一个好的答案，你可以把它当作一个组合优化问题。在内存中创建一棵可能的解决方案树。树中的第一个分支是将下一个或多个任务分配给可用的装配线。根据任务进入系统时建立的依赖链，您始终知道“下一步”任务。如果"next“任务是多个任务中的一个，您可能希望将较大的任务作为优先级。

树的下一个深度的节点包括分配下一个任务的可能性(它被分配给哪一行)。

由于这会导致大量的可能性，随着树的迅速增长，您需要定期修剪树。如果有任何任务是没有意义的，您不应该将这些分配添加到树中。

当树变得太大时，在内存使用方面，或者在任意深度时，将树修剪成一片叶子:计算每一片叶子的成本(效率)，取最好的一片，然后扔掉其他的。从这片叶子开始，计算一组新的分支，等等。