装配线调度

问题陈述

这是可以使用动态规划方法解决的流行问题之一。装配线是工业用来以更少的人力和更快的速度制造产品的机制。在装配线上，原材料被放置在线上，经过几个步骤后，对原材料进行一些操作。

在这个问题中，我们有两条装配线，每条线有 **N** 个站点。N 个站点具有喷漆、塑形等功能。两条线在工作方面是相同的，除了所用的时间。

e1 和 e2 分别是进入装配线 1 和装配线 2 所需的进入时间。

此外，x1 和 x2 分别是对应生产线的退出时间。

如果我们处于任何一个特定的站点，我们将加上该特定站点的运行时间，然后移动到下一个站点。我们有下一个站点的两个选项，要么我们可以去同一生产线的下一个站点，要么我们可以去另一生产线的下一个站点。如果我们选择去另一生产线的下一个站点，我们将需要加上从装配线移动的转换时间。

最后，我们需要计算从装配线退出产品所需的最小时间。

例如

我们有两条装配线，假设我们决定选择突出显示的路径。所花费的时间为

8+12+5+4+3+2+10+12+8+9+2 = 75 单位。

我们必须选择花费时间最少的路径。

方法 1

我们将使用递归方法来解决这个问题。因为在每个站点，我们都有两种可能性，要么我们可以去同一生产线的下一个站点，要么去另一生产线的下一个站点。

Java 代码

输出

说明

在上面的代码中，我们有两个二维数组。一个数组用于两条生产线每个站点的运行时间，另一个二维数组用于转换时间。

我们可以从生产线 1 或生产线 2 开始。我们有两个选择，所以我们取两者选项的最小值并开始递归调用。

在每个站点，我们进行了两次递归调用，并返回两个结果的最小值。对于基本情况，如果我们处于最后一个站点，我们将加上该站点的运行时间和该生产线的退出时间并返回该值。

由于在每个连续的步骤中，我们都有两个递归选择，所以

时间复杂度：O(2ⁿ)，其中 n 是站点的数量。

空间复杂度：O(n) 用于递归。

方法 2

由于存在重叠的递归调用，我们将使用动态规划方法来解决此问题。我们将为此问题使用制表方法，并且我们将从表的底部向上移动以获得结果。

Java 代码

输出

时间复杂度：O(nx2)

空间复杂度：O(nx2)

我们可以将时间复杂度降低到常数，因为在表中，我们只需要下一迭代的两个条目，这些条目已经解决了。

方法 3

Java 代码

输出

说明

在上面的代码中，我们只使用了四个变量而不是数组，这与站点的数量无关，因此它是常数时间。

时间复杂度：(nx2)

空间复杂度：O(1)