如何针对 m 台机器的作业车间问题提出一个蛮力算法？

Question

任务

有n台机器和m个工作。每个作业由 si 个阶段组成。一个阶段由一对 (k,⟩t) 数字来表征，其中 k 是机器的编号，t 是该阶段的持续时间。每个作业的阶段顺序都严格定义。任何阶段都可以随时暂停并稍后从同一点恢复。在任何给定时间，任何作业只能在一台机器上执行，任何机器也只能执行一个作业。目标是创建一个时间表，以最大限度地减少完成所有工作所需的时间。

Note

：我们的目标是准确地解决问题，下面我将展开蛮力的思想。我不是在寻找最快的解决方案；我想将我的想法发展到结论。

想法

蛮力树模型

让我们从蛮力开始。考虑一个树模型，其中一个内部节点代表一个子任务，叶子代表已解决的任务。这棵树是我们的蛮力算法的递归。每个节点存储当前完成该节点对应的子任务所需的时间和该阶段的机器负载状态。当我们向当前子任务中的机器添加作业时，我们将从一个节点移动到下一个级别，从而获得新的时间并加载配置 => 暴力树中的一个新节点。我们可以说，当我们不是将整个作业添加到一台机器上，而是只将其中的一部分添加到机器上时，我们将从一个节点移动到另一个节点，因为根据条件，我们可以中断一个任务，即在完成作业 j1 的第 i 部分之后机器 m，我们可以开始处理另一个工作 j2，它不一定是工作 j1 最后阶段的第 i 个部分。

蛮力树中的分支修剪或切割

在介绍了高度抽象的强力搜索模型之后，有必要提出切割分支的方法，以减少我们树中需要探索的节点数量。这里有一些想法：

• 当我们考虑一个节点时，这意味着我们已经将任务的一部分分配给了一台机器。然后我们可以检查任务的当前部分是否满足该任务中阶段的顺序。由于阶段的顺序是严格定义的，如果我们发现我们把一部分任务分配给机器的时间比我们应该的早，我们就可以切断这个分支。

目前没有其他修剪的想法。在我看来，我们可以通过解决更一般的子问题来得出较低的估计值，但我对此类问题没有任何想法。然后我们可以根据最小化任务中子问题的最小估计值进行修剪。

总结

综上所述，我们得到每个节点将有m个分支到位于最低级别的其他节点。 （为什么是m？因为我们可以打断Jobs，每条边代表把一个Job的一部分分配给一台机器，我们可以打断任意一个job，从所有m台机器中选择一台）对于每个节点，我们存储当前时间的子任务和有关机器当前负载的信息。然后我们再往下一层，类似广度优先搜索，计算子任务，无效则剪枝

问题

我不明白我的模型有多有效，如何实现它，还有哪些其他修剪方法可以设计，最重要的是，如何想出它们？

Answer 1

我有几个建议你可以考虑：

1. 阶段顺序： 如您所述，您可以通过维护分配给作业的阶段顺序来修剪分支。在每个节点，您可以评估分配给机器的作业的当前阶段是否与已经分配给该机器的任何先前阶段一致。如果顺序不一致，那么您可以忽略该分支，因为它不会产生最佳解决方案。
2. 下界和启发式：为了减少额外的分支，可以考虑使用下界或启发式。这些策略提供了关于完成任何剩余任务所需的最短时间的近似值，并告知应调查哪些分支的决策。一种可能的解决方案是采用一种直接的启发式方法，根据机器的现有工作负载和任何尚未完成的任务来预测估计的持续时间。
3. 分支定界： 您可能想要探索分支定界技术，而不是仅仅依靠蛮力方法。该策略将生成所有可能的解决方案（蛮力）与基于下限的优化技术相结合。通过计算完成时间的下限，可以避免探索肯定会产生次优结果的分支。这可以大大减少搜索空间并提高算法的效率。
4. 动态规划