当前位置： 文江博客文章教程详情

装配线调度问题 | DP-34

发布于 2024-03-14 20:44:56 字数 20204 浏览 24 评论 0

一个汽车制造厂有两条装配线，每条装配线有 n 个工位。工位用 S i，j表示，其中 i 为 1 或 2，表示工位在其上的装配线，j 表示工位的编号。每个站花费的时间用i，j 表示。每个工作站都专用于某种工作，例如发动机配件，车身配件，喷漆等。因此，汽车底盘必须在出厂前依次经过 n 个站点中的每个站点。两条装配线的并行站执行相同的任务。在经过站点 S i,j 之后，它将继续到达站点 S i,j + 1，除非它决定转移到另一条线路。在同一条线路上继续行驶不会产生任何额外费用，但是从站点 i – 1 处的线路 i 转移到另一条线路上的站点 j 需要花费时间 t i,j 。每条装配线的进入时间 e i 和退出时间 x i 对于两条生产线可能是不同的。给出一种算法，用于计算构建汽车底盘所需的最短时间。

下图清楚地显示了该问题：

可以从问题说明中提取以下信息，以使其更简单：

  • 两条装配线 1 和 2，每条装配线的位置从 1 到 n。
  • 汽车底盘必须按顺序（从两条装配线中的任何一条) 穿过所有站点，从 1 到 n。即，如果它们不在一个移动距离，它就不能从站 i 跳到站 j。
  • 轿厢底盘可以在同一条直线上向前移动一个工位，也可以在另一条直线上对角移动一个工位。从线路 i 移至站点 j 会产生额外的费用 ti,j。在同一行中移动不会产生任何费用。
  • 在第 i 行的第 j 站所花费的时间为 i,j 。
  • S i,j 代表线 i 上的站点 j。

将问题分解为较小的子问题：

如果第(i-1) 个阶乘是已知的，我们可以很容易地找到第 i 个阶乘。我们可以在这里申请类似的基础吗?
如果已知底盘离开站点 S i，j-1的最短时间，则可以通过组合 a i,j 和 t i,j 来快速计算离开站点 S i,j 的最短时间。

  • T1(j) 表示汽车底盘离开装配线 1 上的工位 j 所需的最短时间。
  • T2(j) 表示汽车底盘离开装配线 2 上的工位 j 所需的最短时间。

基本案例：

进入时间 e i 仅在汽车底盘进入汽车制造厂时才显示出来。
离开 1 号线的第一个车站所需的时间由下式给出：

T1(1)= 1 号线的进入时间+在 S 1,1站花费的时间
T1(1)= e 1 + a 1,1

同样，第 2 行离开第一站的时间由下式给出：

T2(1)= e 2 + a 2,1

递归关系：

如果我们看问题陈述，它很快可以归结为以下观察结果：
站点 S 1,j的轿厢底盘可以来自站点 S 1,j-1 或站点 S 2,j-1 。

情况 1：它的前一站是 S 1,j-1
离开车站 S 1,j的最短时间由下式给出：

T1(j)=离开 S 1，j-1站所花费的最短时间+在 S 1，j站所花费的时间
T1(j)= T1(j-1)+ a 1，j

情况 2：它的前一个电台是 S 2,j-1
离开车站 S1 的最短时间 j 为：

T1(j)=离开 S 2,j-1 所需的最短时间+更换装配线所产生的额外费用+在 S 1，j 所花费的时间
T1(j)= T2(j-1)+ t 2，j + a 1，j

最小时间 T1(j) 由在情况＃1 和＃2 中获得的两者中的最小值给出。

T1(j)= min((T1(j-1)+ a 1，j )，(T2(j-1)+ t 2，j + a 1，j ))

同样，到达站点 S2 j 的最短时间由下式给出：

T2(j)= min((T2(j-1)+ a 2，j )，(T1(j-1)+ t 1，j + a 2，j ))

汽车底盘从工厂出来所需的最短总时间为：

Tmin = min(离开车站 S i，n 所需的时间+离开汽车工厂所需的时间)
Tmin = min(T1(n)+ x 1 ，T2(n)+ x 2 )

为什么要动态编程?

上述递归表现出重叠的子问题。有两种到达车站 S 1,j 的方式：

  1. 从 S 1,j-1 站
  2. 从 S 2 站，j-1

因此，要找到离开站点 S 1的最短时间，必须计算离开前两个站点的最短时间（如上递归所述)。

同样，有两种方法可以到达站点 S 2,j ：

  1. 从 S 2 站，j-1
  2. 从 S 1,j-1站

请注意，已经计算出离开车站 S 1,j-1和 S 2,j-1的最短时间。
因此，我们需要两个表来存储为装配线中的每个工位计算的部分结果。表格将以自下而上的方式填充。

笔记：在这篇文章中，使用了 离开 一词来代替 到达，以避免混淆。由于汽车底盘必须在每个站点上花费固定的时间，因此“离开”这个词比较合适。

执行：

C++

// A C++ program to find minimum possible
// time by the car chassis to complete
#include 
using namespace std;
#define NUM_LINE 2
#define NUM_STATION 4
 
// Utility function to find a minimum of two numbers
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int carAssembly(int a[][NUM_STATION],
                int t[][NUM_STATION],
                int *e, int *x)
{
    int T1[NUM_STATION], T2[NUM_STATION], i;
 
    // time taken to leave first station in line 1
    T1[0] = e[0] + a[0][0];
     
    // time taken to leave first station in line 2
    T2[0] = e[1] + a[1][0];
 
    // Fill tables T1[] and T2[] using the
    // above given recursive relations
    for (i = 1; i < NUM_STATION; ++i)
    {
        T1[i] = min(T1[i - 1] + a[0][i],
                    T2[i - 1] + t[1][i] + a[0][i]);
        T2[i] = min(T2[i - 1] + a[1][i],
                    T1[i - 1] + t[0][i] + a[1][i]);
    }
 
    // Consider exit times and retutn minimum
    return min(T1[NUM_STATION - 1] + x[0],
               T2[NUM_STATION - 1] + x[1]);
}
 
// Driver Code
int main()
{
    int a[][NUM_STATION] = {{4, 5, 3, 2},
                            {2, 10, 1, 4}};
    int t[][NUM_STATION] = {{0, 7, 4, 5},
                            {0, 9, 2, 8}};
    int e[] = {10, 12}, x[] = {18, 7};
 
    cout << carAssembly(a, t, e, x);
 
    return 0;
}
 
// This is code is contributed by rathbhupendra

C

// A C program to find minimum possible time by the car chassis to complete
#include 
#define NUM_LINE 2
#define NUM_STATION 4
 
// Utility function to find minimum of two numbers
int min(int a, int b) { return a < b ? a : b; }
 
int carAssembly(int a[][NUM_STATION], int t[][NUM_STATION], int *e, int *x)
{
    int T1[NUM_STATION], T2[NUM_STATION], i;
 
    T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 1
    T2[0] = e[1] + a[1][0]; // time taken to leave first station in line 2
 
    // Fill tables T1[] and T2[] using the above given recursive relations
    for (i = 1; i < NUM_STATION; ++i)
    {
        T1[i] = min(T1[i-1] + a[0][i], T2[i-1] + t[1][i] + a[0][i]);
        T2[i] = min(T2[i-1] + a[1][i], T1[i-1] + t[0][i] + a[1][i]);
    }
 
    // Consider exit times and retutn minimum
    return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]);
}
 
int main()
{
    int a[][NUM_STATION] = {{4, 5, 3, 2},
                {2, 10, 1, 4}};
    int t[][NUM_STATION] = {{0, 7, 4, 5},
                {0, 9, 2, 8}};
    int e[] = {10, 12}, x[] = {18, 7};
 
    printf("%d", carAssembly(a, t, e, x));
 
    return 0;
}

Java

// A java program to find minimum possible
// time by the car chassis to complete
import java.io.*;
 
class GFG
{
    static int NUM_LINE = 2;
    static int NUM_STATION = 4;
     
    // Utility function to find minimum of two numbers
    static int min(int a, int b)
    {
        return a < b ? a : b;
         
    }
     
    static int carAssembly(int a[][], int t[][], int e[], int x[])
    {
        int T1[]= new int [NUM_STATION];
        int T2[] =new int[NUM_STATION] ;
        int i;
     
        // time taken to leave first station in line 1
        T1[0] = e[0] + a[0][0];
         
        // time taken to leave first station in line 2
        T2[0] = e[1] + a[1][0];
     
        // Fill tables T1[] and T2[] using
        // the above given recursive relations
        for (i = 1; i < NUM_STATION; ++i)
        {
            T1[i] = min(T1[i - 1] + a[0][i],
                    T2[i - 1] + t[1][i] + a[0][i]);
            T2[i] = min(T2[i - 1] + a[1][i],
                    T1[i - 1] + t[0][i] + a[1][i]);
        }
     
        // Consider exit times and retutn minimum
        return min(T1[NUM_STATION-1] + x[0],
                    T2[NUM_STATION-1] + x[1]);
    }
     
     
    // Driver code
    public static void main (String[] args)
    {
        int a[][] = {{4, 5, 3, 2},
                    {2, 10, 1, 4}};
        int t[][] = {{0, 7, 4, 5},
                    {0, 9, 2, 8}};
        int e[] = {10, 12}, x[] = {18, 7};
     
        System.out.println(carAssembly(a, t, e, x));   
     
    }
}
// This code is contributed by vt_m

Python 3

# Python program to find minimum possible
# time by the car chassis to complete
 
def carAssembly (a, t, e, x):
     
    NUM_STATION = len(a[0])
    T1 = [0 for i in range(NUM_STATION)]
    T2 = [0 for i in range(NUM_STATION)]
     
    T1[0] = e[0] + a[0][0] # time taken to leave
                           # first station in line 1
    T2[0] = e[1] + a[1][0] # time taken to leave
                           # first station in line 2
 
    # Fill tables T1[] and T2[] using
    # above given recursive relations
    for i in range(1, NUM_STATION):
        T1[i] = min(T1[i-1] + a[0][i],
                    T2[i-1] + t[1][i] + a[0][i])
        T2[i] = min(T2[i-1] + a[1][i],
                    T1[i-1] + t[0][i] + a[1][i] )
 
    # consider exit times and return minimum
    return min(T1[NUM_STATION - 1] + x[0],
               T2[NUM_STATION - 1] + x[1])
 
a = [[4, 5, 3, 2],
     [2, 10, 1, 4]]
t = [[0, 7, 4, 5],
     [0, 9, 2, 8]]
e = [10, 12]
x = [18, 7]
 
print(carAssembly(a, t, e, x))
 
# This code is contributed by Soumen Ghosh

C#

// A C# program to find minimum possible
// time by the car chassis to complete
using System;
 
class GFG {
     
    static int NUM_STATION = 4;
     
    // Utility function to find minimum
    // of two numbers
    static int min(int a, int b)
    {
        return a < b ? a : b;
         
    }
     
    static int carAssembly(int [,]a, int [,]t,
                             int []e, int []x)
    {
        int []T1= new int [NUM_STATION];
        int []T2 =new int[NUM_STATION] ;
        int i;
     
        // time taken to leave first station
        // in line 1
        T1[0] = e[0] + a[0,0];
         
        // time taken to leave first station
        // in line 2
        T2[0] = e[1] + a[1,0];
     
        // Fill tables T1[] and T2[] using
        // the above given recursive relations
        for (i = 1; i < NUM_STATION; ++i)
        {
            T1[i] = min(T1[i - 1] + a[0,i],
                  T2[i - 1] + t[1,i] + a[0,i]);
            T2[i] = min(T2[i - 1] + a[1,i],
                  T1[i - 1] + t[0,i] + a[1,i]);
        }
     
        // Consider exit times and retutn
        // minimum
        return min(T1[NUM_STATION-1] + x[0],
                    T2[NUM_STATION-1] + x[1]);
    }
     
    // Driver code
    public static void Main ()
    {
        int [,]a = { {4, 5, 3, 2},
                     {2, 10, 1, 4} };
                      
        int [,]t = { {0, 7, 4, 5},
                     {0, 9, 2, 8} };
                      
        int []e = {10, 12};
        int []x = {18, 7};
     
        Console.Write(carAssembly(a, t, e, x));
     
    }
}
 
// This code is contributed by nitin mittal.

C++

// A space optimized solution for
// assembly line scheduling
#include 
using namespace std;
 
int carAssembly(int a[][4],
                int t[][4],
                int *e, int *x)
{
    int first, second, i;
 
    // Time taken to leave first
    // station in line 1
    first = e[0] + a[0][0];
     
    // Time taken to leave first
    // station in line 2
    second = e[1] + a[1][0];
 
    // Fill tables T1[] and T2[] using the
    // above given recursive relations
    for(i = 1; i < 4; ++i)
    {
        int up =  min(first + a[0][i],
                     second + t[1][i] +
                              a[0][i]);
        int down = min(second + a[1][i],
                        first + t[0][i] +
                                a[1][i]);
        first = up;
        second = down;
    }
 
    // Consider exit times and
    // return minimum
    return min(first + x[0],
              second + x[1]);
}
 
// Driver Code
int main()
{
    int a[][4] = { { 4, 5, 3, 2 },
                   { 2, 10, 1, 4 } };
    int t[][4] = { { 0, 7, 4, 5 },
                   { 0, 9, 2, 8 } };
    int e[] = { 10, 12 }, x[] = { 18, 7 };
 
    cout << carAssembly(a, t, e, x);
 
    return 0;
}
 
// This code is contributed by chitrasingla2001

Java

// A space optimized solution for assembly line scheduling
public class AssemblyLine {
    public static void main(String[] args) {
        int a[][] = {{4, 5, 3, 2},
                {2, 10, 1, 4}};
        int t[][] = {{0, 7, 4, 5},
                {0, 9, 2, 8}};
        int e[] = {10, 12}, x[] = {18, 7};
  
        System.out.println(carAssembleTime(a, t, e, x));
    }
  
    public static int carAssembleTime(int a[][], int t[][],
                                       int e[], int x[]) {
        int n = a[0].length;
         
        // time taken to leave first station in line 1 
        int first = e[0] + a[0][0];
 
        // time taken to leave first station in line 2
        int second = e[1] + a[1][0];
          
        for (int i = 1; i < n; i++) {
            int up = Math.min(first + a[0][i],
                    second + t[1][i] + a[0][i]),
                    down = Math.min(second + a[1][i],
                            first + t[0][i] + a[1][i]);
            first = up;
            second = down;
        }
  
        first += x[0];
        second += x[1];
  
        return Math.min(first, second);
    }
}

Python 3

# A space optimized solution for assembly
# line scheduling in Python3
def carAssembleTime(a, t, e, x):
     
    n = len(a[0])
 
    # Time taken to leave first station
    # in line 1
    first = e[0] + a[0][0]
 
    # Time taken to leave first station
    # in line 2
    second = e[1] + a[1][0]
 
    for i in range(1, n):
        up = min(first + a[0][i],
                 second + t[1][i] + a[0][i])
        down = min(second + a[1][i],
                   first + t[0][i] + a[1][i])
             
        first, second = up, down
 
    first += x[0]
    second += x[1]
 
    return min(first, second)
 
# Driver Code
a = [ [ 4, 5, 3, 2 ], [ 2, 10, 1, 4 ] ]
t = [ [ 0, 7, 4, 5 ], [ 0, 9, 2, 8 ] ]
e = [ 10, 12 ]
x = [ 18, 7 ]
     
print(carAssembleTime(a, t, e, x))
 
# This code is contributed by Prateek Gupta

C#

// A space optimized solution for
// assembly line scheduling
using System;
 
class GFG{
     
static int carAssembleTime(int[,] a, int[,] t,
                           int[] e, int[] x)
{
    int n = a.GetLength(1);
     
    // Time taken to leave first station in line 1 
    int first = e[0] + a[0, 0];
 
    // Time taken to leave first station in line 2
    int second = e[1] + a[1, 0];
       
    for(int i = 1; i < n; i++)
    {
        int up = Math.Min(first + a[0, i],
               second + t[1, i] + a[0, i]),
            down = Math.Min(second + a[1, i],
                   first + t[0, i] + a[1, i]);
       
        first = up;
        second = down;
    }
 
    first += x[0];
    second += x[1];
 
    return Math.Min(first, second);
}
 
// Driver Code
static void Main()
{
    int[,] a = { { 4, 5, 3, 2 },
                 { 2, 10, 1, 4 } };
    int[,] t = { { 0, 7, 4, 5 },
                 { 0, 9, 2, 8 } };
    int[] e = { 10, 12 }, x = { 18, 7 };
     
    Console.WriteLine(carAssembleTime(a, t, e, x));
}
}
 
// This code is contributed by divyeshrabadiya07

输出：

35

粗线显示了给定输入值时，汽车底盘覆盖的路径。我们只需要辅助数组中的最后两个值。因此，我们可以使用两个变量来代替创建两个数组。

C++

// A space optimized solution for
// assembly line scheduling
#include 
using namespace std;
 
int carAssembly(int a[][4],
                int t[][4],
                int *e, int *x)
{
    int first, second, i;
 
    // Time taken to leave first
    // station in line 1
    first = e[0] + a[0][0];
     
    // Time taken to leave first
    // station in line 2
    second = e[1] + a[1][0];
 
    // Fill tables T1[] and T2[] using the
    // above given recursive relations
    for(i = 1; i < 4; ++i)
    {
        int up =  min(first + a[0][i],
                     second + t[1][i] +
                              a[0][i]);
        int down = min(second + a[1][i],
                        first + t[0][i] +
                                a[1][i]);
        first = up;
        second = down;
    }
 
    // Consider exit times and
    // return minimum
    return min(first + x[0],
              second + x[1]);
}
 
// Driver Code
int main()
{
    int a[][4] = { { 4, 5, 3, 2 },
                   { 2, 10, 1, 4 } };
    int t[][4] = { { 0, 7, 4, 5 },
                   { 0, 9, 2, 8 } };
    int e[] = { 10, 12 }, x[] = { 18, 7 };
 
    cout << carAssembly(a, t, e, x);
 
    return 0;
}
 
// This code is contributed by chitrasingla2001

Java

// A space optimized solution for assembly line scheduling
public class AssemblyLine {
    public static void main(String[] args) {
        int a[][] = {{4, 5, 3, 2},
                {2, 10, 1, 4}};
        int t[][] = {{0, 7, 4, 5},
                {0, 9, 2, 8}};
        int e[] = {10, 12}, x[] = {18, 7};
  
        System.out.println(carAssembleTime(a, t, e, x));
    }
  
    public static int carAssembleTime(int a[][], int t[][],
                                       int e[], int x[]) {
        int n = a[0].length;
         
        // time taken to leave first station in line 1 
        int first = e[0] + a[0][0];
 
        // time taken to leave first station in line 2
        int second = e[1] + a[1][0];
          
        for (int i = 1; i < n; i++) {
            int up = Math.min(first + a[0][i],
                    second + t[1][i] + a[0][i]),
                    down = Math.min(second + a[1][i],
                            first + t[0][i] + a[1][i]);
            first = up;
            second = down;
        }
  
        first += x[0];
        second += x[1];
  
        return Math.min(first, second);
    }
}

Python3

# A space optimized solution for assembly
# line scheduling in Python3
def carAssembleTime(a, t, e, x):
     
    n = len(a[0])
 
    # Time taken to leave first station
    # in line 1
    first = e[0] + a[0][0]
 
    # Time taken to leave first station
    # in line 2
    second = e[1] + a[1][0]
 
    for i in range(1, n):
        up = min(first + a[0][i],
                 second + t[1][i] + a[0][i])
        down = min(second + a[1][i],
                   first + t[0][i] + a[1][i])
             
        first, second = up, down
 
    first += x[0]
    second += x[1]
 
    return min(first, second)
 
# Driver Code
a = [ [ 4, 5, 3, 2 ], [ 2, 10, 1, 4 ] ]
t = [ [ 0, 7, 4, 5 ], [ 0, 9, 2, 8 ] ]
e = [ 10, 12 ]
x = [ 18, 7 ]
     
print(carAssembleTime(a, t, e, x))
 
# This code is contributed by Prateek Gupta

C＃

// A space optimized solution for
// assembly line scheduling
using System;
 
class GFG{
     
static int carAssembleTime(int[,] a, int[,] t,
                           int[] e, int[] x)
{
    int n = a.GetLength(1);
     
    // Time taken to leave first station in line 1 
    int first = e[0] + a[0, 0];
 
    // Time taken to leave first station in line 2
    int second = e[1] + a[1, 0];
       
    for(int i = 1; i < n; i++)
    {
        int up = Math.Min(first + a[0, i],
               second + t[1, i] + a[0, i]),
            down = Math.Min(second + a[1, i],
                   first + t[0, i] + a[1, i]);
       
        first = up;
        second = down;
    }
 
    first += x[0];
    second += x[1];
 
    return Math.Min(first, second);
}
 
// Driver Code
static void Main()
{
    int[,] a = { { 4, 5, 3, 2 },
                 { 2, 10, 1, 4 } };
    int[,] t = { { 0, 7, 4, 5 },
                 { 0, 9, 2, 8 } };
    int[] e = { 10, 12 }, x = { 18, 7 };
     
    Console.WriteLine(carAssembleTime(a, t, e, x));
}
}
 
// This code is contributed by divyeshrabadiya07

输出：

35

锻炼：扩展上述算法以在工厂中打印汽车底盘覆盖的路径。

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群
更多

你可能也喜欢

创建 Docker Swarm 集群

重建 CentOS 或 RHEL 上被损坏的 RPM 数据库

修复 passwd:Authentication token manipulation error 的步骤

Maven 中 optional 关键字

分布式缓存管理平台 XXL-CACHE

分享那些优雅简约的 404 页面设计

Sass 操作符介绍

模块化 CSS 更要避免选择器嵌套

上一篇：

下一篇：

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。
列表为空，暂无数据

关于作者

夏尔

暂无简介

0 文章
0 评论
22 人气
发私信
更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

淡笑忘祈一世凡恋

文章 0 评论 0

我们的影子

文章 0 评论 0

素年丶

文章 0 评论 0

南笙

文章 0 评论 0

18215568913

文章 0 评论 0

qq_xk7Ean

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文