下一个→ ←上一页

装配线调度

问题陈述

这是一个可以用动态规划方法解决的流行问题。流水线是工业用较少的人力和更快的速度来生产产品的机械。在流水线上，原料被放到生产线上，经过几个步骤，对原料进行一些操作。

在这个问题中，我们有两条装配线，每条线都有N电台。N站有他们的功能，如绘画，形状制作等。这两条线除了所用的时间外，就功而言是相同的。

由于进入时间分别需要进入流水线1和流水线2，因此有e1和e2。

也有x1和x2作为各自线路的退出时间。

如果我们在任何一站，我们会加上该站的时间，然后我们会移动到下一站。下一站我们有两种选择，要么我们去同一线路的下一站，要么我们去另一条线路的下一站。如果我们选择去另一条生产线的下一站，我们将不得不增加从装配线转移的过渡时间。

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

例如:

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

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

我们必须选择一条时间最短的路。

Method1

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

Java代码:

            class HelloWorld {public static void main(String[] args) {int e1=10;int e2 = 12;int x1 = 18;int x2 = 7;int [] [] t ={{4、5、3、2},{2 10 1 4}};int [] [] trans ={{7、4、5},{9 2 - 8}};int result1 = e1 + getMinTime编写此表达式(t,反式,x1, x2, 0, 0);int result2 = e2 + getMinTime (t,反式,x1, x2, 1 0);System.out.println (Math.min (result1,编写此表达式result2));} public static int getMinTime(int[][] t,int[][] trans,int x1,int x2,int line,int station){if(station==t[0].length-1){返回t[line][station]+(line==0?x1:x2); } int path1=getMinTime(t,trans,x1,x2,line,station+1); int path2=trans[line][station]+getMinTime(t,trans,x1,x2,1-line,station+1); return t[line][station]+Math.min(path1,path2); } }
           

输出:

解释

在上面的代码中，我们有两个2d数组。一个数组表示两条线路上每个站的时间，另一个2d数组表示过渡时间。

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

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

因为在每一个连续的步骤中，我们有两个递归选择

时间复杂度:O(2ⁿ)，其中n为车站数。

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

Method2

由于存在重叠的递归调用，我们将使用动态编程方法来解决这个问题。我们将使用制表的方法来解决这个问题，我们将从下到上在表格中得到结果。

Java代码:

            class HelloWorld {public static void main(String[] args) {int e1=8;int e2 = 6;int x1 = 12;int x2 = 2;int n = 6;/ /数字电台int [] [] t ={{12、5、7、6、12 4},{2 7日,11日,3日,15日9}};int [] [] trans ={{2、4、6、10、8},{1、3、5、9日7}};Int [][] dp=new Int [2][n];dp [0] (n - 1) = t [0] (n - 1) + x1;dp [1] (n - 1) = t [1] (n - 1) + x2; for(int i=n-2;i>=0;i--){ dp[0][i]=t[0][i]; dp[0][i]+=Math.min(dp[0][i+1],trans[0][i]+dp[1][i+1]); dp[1][i]=t[1][i]; dp[1][i]+=Math.min(dp[1][i+1],trans[1][i]+dp[0][i+1]); } int ans=Math.min(e1+dp[0][0],e2+dp[1][0]); System.out.println(ans); } }
           

输出:

时间复杂度: O (nx2)

空间复杂度: O (nx2)

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

Method3

Java代码:

            class HelloWorld {public static void main(String[] args) {int e1=8;int e2 = 6;int x1 = 12;int x2 = 2;int n = 6;/ /数字电台int [] [] t ={{12、5、7、6、12 4},{2 7日,11日,3日,15日9}};int [] [] trans ={{2、4、6、10、8},{1、3、5、9日7}};Int [][] dp=new Int [2][n];int prev1 = t [0] (n - 1) + x1;int prev2 = t [1] (n - 1) + x2; for(int i=n-2;i>=0;i--){ int curr1=t[0][i]; curr1+=Math.min(prev1,trans[0][i]+prev2); int curr2=t[1][i]; curr2+=Math.min(prev2,trans[1][i]+prev1); prev1=curr1; prev2=curr2; } int ans=Math.min(e1+prev1,e2+prev2); System.out.println(ans); } }
           

输出: